题目描述
//个人理解
include [HTML_REMOVED]
using namespace std;
int f[105];
int n;
int sg(int x){
if(f[x] != -1) return f[x];
set<int> S;
for(int i=0; i<x; i++){
for(int j=0; j<=i; j++){
//为什么插入sg(i) ^ sg(j)?
//我的理解是异或后的状态无非两种,0或非0,只要非0,那么就是一种获胜状态
//只要这种状态异或上其他的所有状态仍然是获胜状态,也即非0状态,即可获胜
//这里的sg,我的理解是专门构建的一种能走到的最小状态(只要非0,即可获胜)
S.insert(sg(i) ^ sg(j));
}
}
for(int i=0; ; i++){
if(!S.count(i)) return f[x] = i;
}
}
int main() {
cin >> n;
memset(f, -1, sizeof f);
int res = 0;
//如果所有x的sg(x)异或值不是0,说明有方法按死对方,按倒0即可,因为改变一下状态就可以是0
//此时永远保持这种状态,对方是0,取值后必不为0,我方再取值保证对方异或值为0,最后一定按死对方
//sg(x)表示的是x能走到的最小的一个状态,只要不是0即可获胜
for(int i=1; i<=n; i++){
int x;
cin >> x;
res ^= sg(x);
}
if(res) printf("Yes\n");
else printf("No");
return 0;
}
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla