AcWing 891. Nim游戏
给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数n。
第二行包含n个数字，其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜，则输出“Yes”。
否则，输出“No”。
数据范围
1≤n≤105,
1≤每堆石子数≤109
输入样例：
2
2 3
输出样例：
Yes
Code:
先手必胜状态：某种操作后剩下的状态是必败状态。
先手必败状态：任何操作都走不到一个必败状态。
a1 ^ a2 ^ ……^ an = 0， 先手必败
a1 ^ a2 ^ ……^ an ≠ 0， 先手必胜
#include <iostream>
#include <algorithm>
using namespace std;int main()
{
int n, res = 0;cin >> n;while(n --){
int x;cin >> x;res ^= x;}if(res) puts("Yes");else puts("No");return 0;
}
AcWing 892. 台阶-Nim游戏
现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第i级台阶上有ai个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数n。
第二行包含n个整数，其中第i个整数表示第i级台阶上的石子数ai。
输出格式
如果先手方必胜，则输出“Yes”。
否则，输出“No”。
数据范围
1≤n≤105,
1≤ai≤109
输入样例：
3
2 1 3
输出样例：
Yes
Code:
奇数级台阶上的石子异或不等于0，则先手必胜；反之，先手必败。
#include <iostream>
#include <algorithm>
using namespace std;int main()
{
int n, res = 0;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;
}
AcWing 893. 集合-Nim游戏
给定n堆石子以及一个由k个不同正整数构成的数字集合S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数k，表示数字集合S中数字的个数。
第二行包含k个整数，其中第i个整数表示数字集合S中的第i个数si。
第三行包含整数n。
第四行包含n个整数，其中第i个整数表示第i堆石子的数量hi。
输出格式
如果先手方必胜，则输出“Yes”。
否则，输出“No”。
数据范围
1≤n,k≤100,
1≤si,hi≤10000
输入样例：
2
2 5
3
2 4 7
输出样例：
Yes
集合-Nim游戏思路：
mex(S)表示不包含集合内数的最小非负整数。
SG(G) 为x的后续节点y1、y2、……yk的SG函数构成的集合再执行mex运算。
即SG(x) = mex{SG(y1), SG(y2), ……,SG(yk)}
SG函数的性质：
①SG(k）有k个后继节点，分别为0 ~ k - 1.
②非0可以走向0, 0只能走向非0.
③多个独立局面的SG值等于SG(G1)^ SG(G2)^ ……^SG(Gn).
对于一个图G，如果SG(G) ≠ 0，则先手必胜，反之必败
对于n个图，如果 SG(G1)^ SG(G2)^ ……^SG(Gn) ≠ 0,则先手必胜，反之必败
Code:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
using namespace std;const int N = 110, M = 10010;
int n, m;
int s[N], f[M];int sg(int x)
{
if(f[x] != -1) return f[x];unordered_set<int> S;for(int i = 0; i < m; i ++)if(x >= s[i]) S.insert(sg(x - s[i]));for(int i = 0; ; i ++)if(!S.count(i)) return f[x] = i;
}
int main()
{
cin >> m;for(int i = 0; i < m; i ++) cin >> s[i];memset(f, -1, sizeof f);cin >> n;int res = 0;while(n --){
int x;cin >> x;res ^= sg(x);}if(res) puts("Yes");else puts("No");return 0;
}
AcWing 894. 拆分-Nim游戏
给定n堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数n。
第二行包含n个整数，其中第i个整数表示第i堆石子的数量ai。
输出格式
如果先手方必胜，则输出“Yes”。
否则，输出“No”。
数据范围
1≤n,ai≤100
输入样例：
2
2 3
输出样例：
Yes
Code:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
using namespace std;const int N = 110;
int n;
int f[N];int sg(int x)
{
if(f[x] != -1) return f[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)) return f[x] = i;
}int main()
{
memset(f, -1, sizeof f);cin >> n;int res = 0;while(n --){
int x;cin >> x;res ^= sg(x);}if(res) puts("Yes");else puts("No");return 0;
}