给定 n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字，其中第 i个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤10^5,
1≤每堆石子数≤10^9
输入样例：
1. 2 2. 2 3
输出样例：
Yes
思路：
必败态：此状态的玩家，不论怎么操作都会输
必胜态：此状态的玩家，总是可以通过一定的操作，使得下一次对手拿到的状态为必败态度。
在此题目中 假定a1 a2....an都为0，则他们异或为0，此时为必败态，因为拿到这个状态的人无法操作。
反之如果异或值不是0，则可通过一定操作使得异或值为0。
证明非0态可以转化为0态（即必胜态可以留给对手必败态）：
假定a1^a2^....an = x, x的二进制表示中最高一位1在第k位上
则a1~an中必有一个数ai，ai的第k位是1，得出结论ai ^ x < ai
我们再从ai中取得（ai - (ai ^ x)）数目的石子
则ai中的石子数目为 ai - (ai - (ai ^ x)) = ai ^ x
所以现在式子变成a1^a2^...^ai^x^...^an
因为a1^....an = x
所以现在式子简化为x ^ x = 0
局面已经是必败态了
局面已经是必败态了
#include <iostream> using namespace std; int main(){ int n,x; cin>>n; int res=0; while(n--){ cin>>x; res^=x; } if(res)cout<<"Yes"; else cout<<"No"; }
台阶Nim
现在，有一个 n级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 级台阶上的石子数 ai。
输出格式
如果先手方必胜，则输出 Yes。
否则，输出 No。
数据范围
1≤n≤10^5
1≤ai≤10^9
输入样例：
1. 3 2. 2 1 3
输出样例：
Yes
这里将输入的每个ai异或换成输入的每个奇数异或就行。
#include <iostream> using namespace std; int main(){ int n,x; cin>>n; int res=0; for(int i=1;i<=n;i++){ cin>>x; if(i%2)res^=x; } if(res)cout<<"Yes"; else cout<<"No"; }
