常见的几个博弈

第一种：巴什博弈

游戏玩法: 有一堆物品共n个,两人轮流取物，一次最少取一个最多取m个。取走最后一个的胜。

思路：当n<=m时显然先手胜。
n=m+1时无论先手怎么取后手都能取完,所以此时的状态为平衡态。谁面临这个状态必输。
已知n%(m+1)!=0时先手显然可以取走n%(m+1)的余数让对手变为平衡态。
至此，规律已经出来了：
N%(m+1)==0 后手胜,否则先手胜。

试题传送门：
HDU-Brave_Game

第二种：威佐夫博弈

两堆物品,两人轮流取,一次可从一堆取至少 1个至多全部，或从两堆取相同数，取最后一个的人获胜。

思路：第i个必败态的bi=ai+i。
且第i个必败态的ai为前面为出现的最小自然数。
根据beatty序列可证明：

试题传送门：Matches Game

第三种：尼姆博弈

给任意堆物品,每堆物品数任意个,双方轮流取，一次只能从一堆中最少取一个，最多取全部,取走最后一个物品人获胜。

用括号(k1,k2,k3……kn)表示每堆的数目
当为一堆是(k) 可知k=0为必败态，
K>0为必胜态。
两堆：(k1,k2) k1=k2=0为必败态
K1,k2其中一个为0,另一个非0为必胜态。
K1,k2都非0，1.(1,1) 可知为必败态。
2.(1,2)可以通过先手拿一个转化为（1，1）必败态，所以(1,2)为必胜态。
同理可知(2,2)必败态,(k,k)为必败态。
只要后手拿先手之前拿的另一堆相同的数目始终保持两堆相同,直到先手方拿光一堆,此时状态为(K,0)所以后手必胜。
所以(k,k)为必败态。
三堆(k1,k2,k3)如果存在两堆相同，
则先手可以通过拿令一堆使后手处于必败态,所以此时(k,k,k3)为必胜态。
K3=k也是必胜态。
2：当k1,k2,k3都不相同。可以猜想谁先把状态变为必败态，谁就赢。
---------------------------------------------------------------------------------------至此可以猜想规律与异或和有关。
因为两个数相同异或和为0
而两个数相同正好为必败态。
三个相同异或和为该数本身不是0.
可以知道将所有堆物品数进行异或和
若结果为0则为必败态，后手胜。
否则先手胜。

试题传送门：取石子游戏

第四种：奇偶性博弈

首先证明：只要有石子就一定能取。
首先只有一堆石子肯定能取。
假设有两堆石子,且两堆石子数之和大于0,若这两堆石子不能再取，则说明 A2<=A1, A1<0, 则推出 A1+A2<0,与假设矛盾，所以两堆石子肯定能取。依次类推。N堆石子，只要有石子，就肯能取。所以答案只与石子总数的奇偶性有关。石子数为奇数肯定先手赢。反之后手赢。下面上代码。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,ans=0,x;  
    cin>>n;
    while(n--)
        cin>>x,ans=(ans+x)%2;//对2取模奇数永远为1，偶数永远为0 防止爆int 
    puts(ans?"Alice":"Bob");
    return 0;
}

本题也是奇偶性博弈，因为从左上角开始走，所以只剩n^2-1个格子。由于双方都是采取最优策略。所以不可能出现一个人把另一个人围住的情况(另一个人会在之前掉头走别的路)所以最后整个地图肯定会被走完。所以题目转化为谁能走最后一格谁就赢。由于可走的格子有 n^2-1个,所以当 n^2-1为奇数先手赢，反之后手赢。
即 n^2 为偶数先手赢，反之后手赢。
即 n为偶数先手赢，反之后手赢。（奇数*奇数=奇数，偶数 *偶数=偶数）下面上代码。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n&&n)
        puts(n&1?"Bob":"Alice");
    return 0;
}

例题3：

题目传送门P3150
本题也是奇偶性博弈。看题目数据范围 m有1e9之大，显然是找规律。让我们来简单找找规律。
m=1 必败态
m=2 只能分成 1，1 所以是必胜态
m=3 只能分成 1，2 由于2是必胜态所以 3是必败态。
m=4 能分成1，3或2，2 显然分成1，3 后手必败。所以 m=4是必胜态。
依次类推： m=5,必败，m=6必胜。
到这里我们已经发现了规律那就是奇数为必败态，偶数为必胜态，根据这个猜想直接下结论就OK。下面是代码。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        puts(n&1?"zs wins":"pb wins");
    }
    return 0;
}