题解 P2197 【nim游戏】

· · 题解

看了很多dalao写的，感觉都比较难看懂 太弱了

用比较通俗的方式讲一下吧： 题目本意是给出n堆石子，轮流在其中一堆去任意个，谁不能去谁就输。

思路：证明所有石子异或和为0则先手必输

证明：

  1. 反正最终情况就是每堆都为0，先手必输，所以我们考虑怎么把情况转换到这里。

  2. 如果异或和的最高位为i，则有一堆石子第i为为1（不然怎么会有i位）

  3. 设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

  4. 如果现在的异或和已经为0了（不为最终情况），那么怎么转换异或和都不能为0

  5. 好，我们根据3 4点得出：如果先手异或和不为0，可以一步让后手的情况为异或和为0；如果先手异或和为0，那么后手异或和就不为0

  6. 终于开始进行游戏了，如果现在先手面对的情况异或和不为0，则一直让后手异或和为0，最后面对最终情况，后手输，则先手赢；如果先手面对的情况异或和为0，后手则赢

ps：理解最重要

#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");
    }
}