Nim游戏
给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字，其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤10^5
1≤每堆石子数≤10^9
输入样例：
2
2 3
输出样例：
Yes
必胜状态：先手进行某一个操作，留给后手的是一个必败状态时，对于先手来说是一个必胜状态，即先手可以走到某一个必败状态
必败状态： 先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态，即先手走不到任意一个必败状态
结论：a1^a2^a3^a4^...an!=0 先手必胜
a1^a2^a3^a4^...an==0先手必败
异或运算三个性质：
①任何数和 0做异或运算，结果仍然是原来的数
②任何数和其自身做异或运算，结果是 0
③异或运算满足交换律和结合律
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int res=0;int n;cin>>n;while(n--){int x;cin>>x;res^=x;}if(res!=0) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}台阶-Nim游戏
现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i级台阶上有 ai 个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤10^5
1≤ai≤10^9
输入样例：
3
2 1 3
输出样例：
Yes因为第一阶拿到地面要拿一次，第二阶那两次，第三阶那三次…所以可以看成第二阶有两堆石子，第三阶有三堆....因为偶数阶石子为偶数堆，所以异或为0，奇数阶异或后就是原本石子数目，所以可以把原本所有奇数阶的石子进行异或，得到的 就是答案 （是把第i阶（等同于经典nim问题中的第i堆）的石子理解为有i堆，每一堆的数量都是原本第i阶的石子数；）
偶数台阶需要拿偶数次才能到地面，就相当于是把偶数个相同数量的石子堆拿完的策略。正好可以转化成前面一道题的“偶数个石子堆异或在一起，并且这些石子数量相同”，结果必然是0，因此可以不考虑。
最后的状态肯定是所有台阶上的石子都为0 异或结果为0 那么就先手想办法让台阶上的石子异或结果为0 留给后手 让后手一直处于0太 必输的状态
那么去思考 这些台阶上的所有数异或都可以么
当后手改变了偶数的石子 其实相当于没有改变 那先手完全可以 后手在偶数石子中拿了多少 在它的下一层奇数层中在拿出来多少 运往下一层偶数层 使得奇数层数不改变
所有改变偶数就对结果没有任影响 故也可以想到偶数台阶的石子不起作用
奇数台阶的石子起到作用-->就转换到经典Nim游戏
#include<iostream>
using namespace std;
int main()
{int n;cin>>n;int res=0;//只处理奇数个台阶之间相互异或for(int i=1;i<=n;i++){int x;cin>>x;if(i%2!=0) res^=x;}if(res) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}集合-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
输出样例：
Yes1.Mex运算:
设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
mes(S)=min{x};
例如:S={0,1,2,4},那么mes(S)=3;
2.SG函数
在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1,y2,····yk,定义SG(x)的后记节点y1,y2,····
yk的SG函数值构成的集合在执行mex运算的结果,即:
SG(x)=mex({SG(y1),SG(y2)····SG(yk)})
特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即 SG(G)=SG(s).
3.有向图游戏的和
设G1，G2,····,Gm是m个有向图游戏.定义有向图游戏G,他的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步.G被称为有向图游戏G1,G2,·····,Gm的和.
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数的异或和,即:
SG(G)=SG(G1)xorSG(G2)xor···xor SG(Gm)
