1.巴什博弈

巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。
首先考虑必输的局，即(n=m+1)时，无论我们拿多少个，对方都可以一次拿完，所以双方的最优策略就是将m+1的情况留给对手，而整个游戏过程我们都可以看成是k个（m+1）的情况的总和。

结论：

如果n%(m+1)==0 先手必败
n%(m+1)!=0 为先手必胜

2.威佐夫博弈

威佐夫博弈：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。
证明过程没看懂QAQ

结论：

若两堆物品的初始值为（x，y），
且x< y ，则另z=y-x；
记w=（int）(5^0.5−1)/2∗z;//黄金分割
若w=x，则先手必败，否则先手必胜。

3.尼姆博弈

尼姆博弈：从三堆石子中拿石子，每次任选一堆拿任意数目（≥1）的石子，最后取光者胜利。
证明看不懂QAQ

结论：

若所有堆的数量都为1。则根据奇偶来判断谁胜。
其他情况，将所有数据异或起来，若等于0，则为奇异态（必胜态）。

例题：

Little John is playing very funny game with his younger brother. There is one big box filled with M&Ms of different colors. At first John has to eat several M&Ms of the same color. Then his opponent has to make a turn. And so on. Please note that each player has to eat at least one M&M during his turn. If John (or his brother) will eat the last M&M from the box he will be considered as a looser and he will have to buy a new candy box.

Both of players are using optimal game strategy. John starts first always. You will be given information about M&Ms and your task is to determine a winner of such a beautiful game.

Input
The first line of input will contain a single integer T – the number of test cases. Next T pairs of lines will describe tests in a following format. The first line of each test will contain an integer N – the amount of different M&M colors in a box. Next line will contain N integers Ai, separated by spaces – amount of M&Ms of i-th color.

Constraints:
1 <= T <= 474,
1 <= N <= 47,
1 <= Ai <= 4747

Output
Output T lines each of them containing information about game winner. Print “John” if John will win the game or “Brother” in other case.

Sample Input

Sample Output

John
Brother

AC代码：

#include<iostream>
#include<algorithm>
using namespace std;
int a[50];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        sort(a,a+n);
        if(a[n-1]==1)
        {
            if(n%2==0)
            cout<<"John\n";
            else
            cout<<"Brother\n";
        }
        else
        {
            int ans=0;
            ans=a[0]^a[1];
            for(int i=2;i<n;i++)
            {
                ans^=a[i];
            }
            if(ans==0)
            cout<<"Brother\n";
            else
            cout<<"John\n";
        }
    }
    return 0;
}

4.斐波那契博弈（点击进入例题）

斐波那契博弈：

有一堆个数为n的石子，游戏双方轮流取石子
先手不能在第一次把所有的石子取完；
之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）
证明

结论：当石子个数为斐波那契数的时候，先手必败。

int Fib_Game(int n)
{
    f[1]=1;
    f[2]=1;
    for(int i=3;i<=50;i++)
    {
        f[i]=f[i-1]+f[i-2];
        if(f[i]==n)
        return 1;
        if(f[i]>n)
        break;
    }
    return 0;
}

5.环形博弈

环形博弈：

n个石子围成一个环
每次取一个或者取相邻的2个
当且仅当n<=2时，先手能获胜

6.SG函数与SG定理

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
再定义SG函数：SG(x)=mex{ SG(y) | y是x的后继 }。