C++14(g++5.4) 解法, 执行用时: 46ms, 内存消耗: 2024K, 提交时间: 2020-05-15 10:35:34

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char str[1001000];
int n;
int k;
int maxsg;
int sg(int i){
    int ans = i & (-i);
    return min(ans,maxsg);
}
int main()
{
 
    cin>>n>>k;
    cin>>str;
    maxsg=1;
    while(k>1){
        k/=2;
        maxsg*=2;
    }
    int sgsum = 0;
    for(int i=0;i<n;i++){
        if(str[i]=='1')
            sgsum ^= sg(i+1);
    }
    if(sgsum)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 13ms, 内存消耗: 1400K, 提交时间: 2022-11-08 15:09:05

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, k, m = 1;
char s[N];
int getSG(int x) {
    return min(x & -x, m);
}
int main() {
    scanf("%d%d%s", &n, &k, s + 1);
    while (m * 2 < k) m <<= 1;
    int ans = 0;
    for (int i = 1; i <= n; i++) if (s[i] == '1') ans ^= getSG(i);
    puts(ans ? "Yes" : "No");
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 1372K, 提交时间: 2020-07-02 20:48:45

#include<bits/stdc++.h>
using namespace std;

char R[1000005];
int main()
{
	int i,j=0,n,k,m=1;
	scanf("%d%d%s",&n,&k,R+1);
	while((m<<1)<=k)m<<=1;
	for(i=1;i<=n;i++)if(R[i]=='1')j^=min(i&(-i),m);
	if(j)printf("Yes\n");
	else printf("No\n");
    return 0;
}