尼姆博弈（Nim Game）

简述

有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人的时候所有石子堆都已经被拿空了，则判负（因为他此时没有任何合法的移动）

分析

这游戏看上去有些复杂，我们先从简单情况开始研究，如果轮到你时，只剩下一堆石子，那么此时必胜策略肯定是把这堆石子全部拿完，然后对手没有石子拿就输了；如果剩下两堆不相等的石子，必胜策略是通过取多的一堆石子将两堆石子变得相等，之后对手如果在某一堆拿若干颗，你就在另一堆拿同样多的数量，直至胜利；但是如果还剩三堆，应该怎么分析呢？假设有三堆石子（a，b，c），我们前面说到，如果只有两堆石子，并且石子数量满足（n，n），谁先手谁就输。其实我们可以把三堆石子问题转换成两堆，只要满足状态（0，n，n）并且此时是对方先手，那我方按照两堆石子的取法，就能获胜。对于这种（0，n，n）的局势，我们称为奇异局势。对任何奇异局势（a，b，c）都有a^b^c=0（^表示异或），如果我们面对非奇异局势，要如何变为奇异局势呢？假设a<b<c，我们只要将c变为a^b即可。道理很简单，因为a^b^(a^b)=0。要将c变为a^b也很简单，只要从c中减去c-a^b即可

例（14，21，39），14^21=27，39-27=12，所以从39中拿走12个，即可变成奇异局势（14，21.27）

例题

    1.HDU1849 Rabbit and Grass

思路：将输入的值存在数组中，然后连续求异或（0对任意数异或都得任意数本身）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m;
    int a[1001];
    while(cin>>m&&m)
    {
        int res = 0;
        memset(a,0,sizeof(a));
        for(int i = 0;i < m;i++)
        {
            cin>>a[i];
            res ^= a[i];
        }
        if(res == 0)
            cout<<"Grass Win!"<<endl;
        else
            cout<<"Rabbit Win!"<<endl;
    }
    return 0;
}

参考文章：https://hrbust-acm-team.gitbooks.io/acm-book/content/game_theory/nimbo_yi.html