蓝桥杯练习 尼姆堆 题解

题目：
有3堆硬币，分别是3,4,5
二人轮流取硬币。
每人每次只能从某一堆上取任意数量。
不能弃权。
取到最后一枚硬币的为赢家。
求先取硬币一方有无必胜的招法。

思路：
这个题有固定的解法，用二进制模2的加法/异或。
具体意思是：将所有堆的数目进行模2加法/异或，如果加起来全为0，那么将要抓堆的这个人就必输了；如果不全为0，那么这个人通过计算抓堆的数量就会让对方输。
举例来说：一共4堆：2,5,12,14
二进制对应：
0010
0101
1100
1110
——
0101
对每个堆的数目进行异或后结果不为0，所以将要抓堆的这个人不会输，那么他如何让对方输呢？
就是在他抓取一次后给对方留的堆的数目异或起来为0，由0101->0000，将左起第2位和第4位变0，分析造成位结果为1的原因，把某一堆堆数量的对应位取反就可以了（0->1or1->0）
由异或运算性质，0异或任何数，其结果=任何数，1异或任何数，其结果=把该数取反。
这个异或运算的结果恰好就是我们想要达到的效果。所以我们可以将所有数异或运算后的结果再与某堆数目进行异或，得到的结果就是该堆剩下的数目。

Code：

#include <iostream>
#include <cstdlib>

using namespace std;

void f(int *a, int len){
    int sum = 0;
    for(int i = 0; i < len; ++i){
        sum ^= a[i];
    }
    cout<<"sum = "<<sum<<endl;      //按位异或后的结果 

    if(sum == 0){
        cout<<"lost"<<endl;
        return ;
    }
    for(int i = 0; i < len; ++i){
        int x = sum ^ a[i];         //x:在取了第i堆后剩下的 
        if(x < a[i]){
            cout<<a[i]<<"->"<<x<<endl;//原先第i堆的个数->取后剩下的个数 
        }
    }
}

int main(){
    int a[] = {2,5,12,14};
    f(a, 4);                                       
    return 0;
}