Nim
经典的博弈论
大致意思：地上有 n 堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。问是否存在先手必胜的策略。
乍一看手玩一下，发现很复杂，于是考虑把游戏状态形式化地表示出来便于观察。
设先手为a，后手为b。先手必胜其实就是后手必败，那么我们只需考虑什么时候后手会赢。
考虑在最优策略下游戏的结局是一定的，所以其实后手会赢就是后手必胜。
我们把所有石子的当前数目记录下来设为一个状态，例如我现在有三堆石子，分别是5,3,6个，则5,3,6就是当前状态，如果我从第三堆拿一个，就变成了5,3,5个，我们就称5,3,5是5,3,6的后继状态。
你考虑如果一个状态没有后继则是必败的。而一个状态的所有后继都必胜，那么这个状态必败（注意这里一步以后玩家变了，所以对手必败那我必胜），如果一个状态有一个后继必败，那么这个状态就是必胜的。所以其实构成了一张图，我们称之为博弈图。
一般情况下，博弈图会是DAG，在博弈图上建边跑topo可以判断。然而有没有更简便的方式呢？
直接上结论吧：
如果所有石子的异或和为0则必败，否则必胜。
这是怎么回事呢？
我们证明一下：
显然对于这个结论，只需要证明上面我们说过的三条性质。对于第一条性质，如果一个状态没有后继，那么这个状态一定是全0的，异或起来也都是0。第二条，所有后继都必胜，说明异或和都不为0，那么一定有一位是不一样的。我现在这个状态是我后继状态某一堆石子加一，那么一定会存在一种操作可以使得我当前状态全0变成后继状态。
形式化地说：
对于某个局面 \((a1,a2,...,an)\) ，若 \(a_1 \oplus a_2 \ \oplus...\oplus \ a_n \ !=0\) ，一定存在某个合法的移动，将 \(a_i\) 改变成 \(a_i'\) 后满足\(a_1\oplus a_2\oplus ...\oplus \ a_i' \ \oplus...\oplus a_n=0\)。不妨设 \(a_1 \oplus a_2 \ \oplus ...\oplus a_n=k\) ，则一定存在某个 \(a_i\) ，它的二进制表示在 \(k\) 的最高位上是1。这时 \(a_i \oplus k<a_i\) 一定成立（减去了k）。则我们可以将 \(a_i\) 改变成 \(a_i'=a_i\oplus k\)，此时\(a_1\oplus a_2\oplus...\oplus \ a_i' \ \oplus...\oplus \ a_n=a_1\oplus a_2 \ \oplus...\oplus \ a_n\oplus \ k=0\)。
第三条差不多同理。
证毕。
所以我们现在再来看异或的作用，异或不为0，就是保留一个k，保留一个位数，保留一个数，可以取出，可以向下一步转移，对于必胜和必败都可以做出相应转换，因此可以到达末状态，这是至关重要的。
模板:
P2197 【模板】Nim 游戏
#include<bits/stdc++.h>
using namespace std;
int T,n,num[10005],temp;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&num[i]);
temp=0;
for(int i=1;i<=n;++i) temp^=num[i];
if(temp) printf("Yes\n");
else printf("No\n");
}
return 0;
}
P4279 [SHOI2008] 小约翰的游戏
反Nim，注意特判一下全为1的情况。
#include<bits/stdc++.h>
using namespace std;
int T,n,num[55],temp,flag;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
flag=0;
for(int i=1;i<=n;++i){
scanf("%d",&num[i]);
if(num[i]!=1) flag=1;
}
if(!flag){
if(n&1) printf("Brother\n");
else printf("John\n");
}
else{
temp=0;
for(int i=1;i<=n;++i) temp^=num[i];
if(temp) printf("John\n");
else printf("Brother\n");
}
}
return 0;
}
有向图游戏
有向图游戏是一个经典的博弈游戏——实际上，大部分的公平组合游戏都可以转换为有向图游戏。
在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。——OI-WIKI
这一部分直接看OI-WIKI吧，讲得很清楚 有向图游戏与SG定理