#include <iostream> #include <cstdio> using namespace std; /* 先手必胜状态:先手操作完,可以走到某一个必败状态 先手必败状态:先手操作完,走不到任何一个必败状态 先手必败状态:a1 ^ a2 ^ a3 ^ ... ^an = 0 先手必胜状态:a1 ^ a2 ^ a3 ^ ... ^an ≠ 0 */ int main(){ int n; scanf("%d", &n); int res = 0; for(int i = 0; i < n; i++) { int x; scanf("%d", &x); res ^= x; } if(res == 0) puts("No"); else puts("Yes"); }
#include <iostream> using namespace std; int main() { int res = 0; int n; cin >> n; for(int i = 1 ; i <= n ; i++) { int x; cin >> x; if(i % 2) res ^= x; } if(res) puts("Yes"); else puts("No"); return 0; }
#include<bits/stdc++.h> using namespace std; int s[10010],f[10010]; int n,k; int sg(int x) { //记忆化搜索,如果f[x]已经被计算过,则直接返回 if(f[x]!=-1) return f[x]; //用一个哈希表来存每一个局面能到的所有情况,便于求mex set<int>S; for(int i=0;i<k;i++) { int sum=s[i]; //如果可以减去s[i],则添加到S中 if(x>=sum) S.insert(sg(x-sum)); } //求mex(),即找到最小并不在原集合中的数 for(int i=0;;i++) { if(!S.count(i)) return f[x]=i; } } int main() { int i,j; memset(f,-1,sizeof(f)); cin>>k; for(i=0;i<k;i++) cin>>s[i]; cin>>n; int res=0; for(i=0;i<n;i++) { int x; cin>>x; res^=sg(x); } if(res!=0) puts("Yes"); else puts("No"); return 0; }
#include<bits/stdc++.h> using namespace std; int s[110],f[110]; int n; int sg(int x) { if(f[x]!=-1) return f[x]; set<int>S; for(int i=0;i<x;i++) { //规定j不大于i,避免重复 for(int j=0;j<=i;j++) { //相当于一个局面拆分成了两个局面,由SG函数理论,多个独立局面的SG值 //等于这些局面SG值的异或和 S.insert(sg(i)^sg(j)); } } for(int i=0;;i++) { if(!S.count(i)) return f[x]=i; } } int main() { int i,j; memset(f,-1,sizeof f); cin>>n; int res=0; for(i=0;i<n;i++) { int x; cin>>x; res^=sg(x); } if(res!=0) puts("Yes"); else puts("No"); return 0; }
原文:https://www.cnblogs.com/xiaofengzai/p/14413853.html