1.必胜态后继至少存在一个必败态
2.必败态后继均为必胜态

Nim游戏

思路

2 3，先手必赢，先拿 1，然后变成 2 2，不管后手怎么拿，先手同样操作，后手一定先遇到 0 0
a1 ^ a2 ^ a3 … ^ an = 0，先手必败，否则先手必胜

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;int main(){cin>>n;for(int i = 1; i <= n; i++) cin>>a[i];int res = a[1];for(int i = 2; i <= n; i++) res ^= a[i];if(res == 0) cout<<"No";else cout<<"Yes";return 0;
}// 求先手必胜第一次怎么拿
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;int main(){cin>>n;for(int i = 1; i <= n; i++) cin>>a[i];int res = a[1];for(int i = 2; i <= n; i++) res ^= a[i];if(res == 0) cout<<"lose";else{for(int i = 1; i <= n; i++){if((a[i] ^ res) >= a[i]) continue;printf("第%d堆 拿%d个\n", i, (a[i] - (a[i] ^ res)));a[i] = a[i] ^ res;break;}}for(int i = 1; i <= n; i++) printf("%d ", a[i]);return 0;
}

台阶-Nim游戏

思路

如果拿偶数的台阶，你拿多少下去，我就拿多少下去，所以只需要看奇数台阶
如果奇数位 a1 ^ a3 ^ a5 ^ … ^ an = 0，先手必败

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n;int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);int res = a[1];for(int i = 3; i <= n; i += 2){res ^= a[i];}if(res) printf("Yes\n");else printf("No\n");return 0;
}

集合-Nim游戏

思路

如果 SG(x1) ^ SG(x2) ^ SG(x3) ^ … ^ SG(xn) = 0，先手必败

能到 0 那就是 1，能到 1 那就是 0，同时能到 1 和 0，那就是 2

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 110, M = 1e4 + 10;
int a[N], b[M];
int n, m;int sg(int x){if(b[x] != -1) return b[x];unordered_set<int> s;for(int i = 0; i < n; i++){int t = a[i];if(x >= t) s.insert(sg(x - t));}for(int i = 0; ; i++){if(!s.count(i)){b[x] = i;return b[x];}}
}int main(){memset(b, -1, sizeof(b));scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &a[i]);scanf("%d", &m);int res = 0, x;for(int i = 0; i < m; i++){scanf("%d", &x);res ^= sg(x);}if(res) printf("Yes\n");else printf("No\n");return 0;
}

拆分-Nim游戏

思路

一个数分成两个数，再异或

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 110;
int b[N];
int n;int sg(int x){if(b[x] != -1) return b[x];unordered_set<int> s;for(int i = 0; i < x; i++){for(int j = 0; j <= i; j++){s.insert(sg(i) ^ sg(j));}}for(int i = 0; ; i++){if(!s.count(i)){b[x] = i;return b[x];}}
}int main(){memset(b, -1, sizeof(b));scanf("%d", &n);int res = 0, x;for(int i = 0; i < n; i++){scanf("%d", &x);res ^= sg(x);}if(res) printf("Yes\n");else printf("No\n");return 0;
}