题解 P2197 【nim游戏】
y2823774827y
2018-08-09 09:53:12
看了很多dalao写的，感觉都比较难看懂 ~~太弱了~~
用比较通俗的方式讲一下吧：
题目本意是给出n堆石子，轮流在其中一堆去任意个，谁不能去谁就输。
思路：证明所有石子异或和为0则先手必输
证明：
1. 反正最终情况就是每堆都为0，先手必输，所以我们考虑怎么把情况转换到这里。
1. 如果异或和的最高位为i，则有一堆石子第i为为1（不然怎么会有i位）
1. 设A1就为那堆石子，其他堆石子异或和设为x，总异或和设为k，则 A1 xor x=k，把A1变成A1 xor k，那么后手面对的则是（A1 xor k）xor x=0，
举个例子:11001 xor 11100=101，则有（11001 xor 101）xor 11100=0
1. 如果现在的异或和已经为0了（不为最终情况），那么怎么转换异或和都不能为0
1. 好，我们根据3 4点得出：如果先手异或和不为0，可以一步让后手的情况为异或和为0；如果先手异或和为0，那么后手异或和就不为0
1. 终于开始进行游戏了，如果现在先手面对的情况异或和不为0，则一直让后手异或和为0，最后面对最终情况，后手输，则先手赢；如果先手面对的情况异或和为0，后手则赢
ps：理解最重要
```cpp
#include<cstdio>
using namespace std;
int t,n;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int ans=0;
for(int i=1; i<=n; ++i){
int shu;
scanf("%d",&shu);
ans^=shu;
}
if(!ans) printf("No\n");
else printf("Yes\n");
}
}
```