“博弈论”这个算法我久仰大名，一年前就已经有所耳闻，只是我一直不会，今天简单学习了博弈论初步。
博弈论一般来讲，问题的形式就是两个人进行某种博弈，这两个人都绝顶聪明，都希望自己能赢，因此会采取最优策略，博弈论一般不会出现平局的情况。
局面：游戏当前的状况
必败局面：操作到这个局面的人一定会失败，只能由必胜局面转移而来。
必胜局面：操作到这个局面的人一定会胜利，只能由必败局面转移而来。
Nim博弈是最基础的博弈论问题之一 。
问题描述：有两名玩家\(A\)和\(B\)在一起玩一个游戏，一共有\(N\)堆石子，每一堆石子有\(a[i]\)个，两人轮流取石子，每次可以从任意一堆取走任意多的石子，但不能不取，当轮到某一个人取石子的时候，如果他不能再进行操作（也就是石子被取完了），他就输了，游戏结束。给定石子的堆数和每一堆的个数，两个人都希望采取最优解，问是否存在先手必胜的情况。
分析：问题的答案是，求每一堆石子的异或和，如果为\(0\),先手必败，如果不为\(0\),先手必胜。
证明：
设第\(i\)堆石子有\(a[i]\)个，那么必败的局面就是所有石子都被取完，此时\(a[1]\)^\(a[2]\)^\(....\)^\(a[n]=0\)。
I.如果当前处于某个局面，本局面\(a[1]\)^\(a[2]\)^\(...\)^\(a[n]=x!=0\)（也就是必胜局面），那么我们运用异或的性质，在等式两边同时异或一个\(x\)，可以得到：
\(a[1]\)^\(a[2]\)^\(...\)^\(a[n]\)^\(x=x\)^\(x=0\)，也就是说，
我们可以在\(a[i]\)中找到一个数与\(x\)异或，最终使局面转为\(a[1]\)^\(a[2]\)^\(...\)^\(a[n]=0\)，这个数可以随意寻找，只要满足\(x^a[i]<=a[i]\)，那么我们就可以从某堆石子中取出\(a[i]-x\)^\(a[i]\)个石子，从而
使接下来的局面异或和等于\(0\)。我们将异或和不为\(0\)的状态称为必胜局面，第一是因为当前选手可以继续操作，第二是因为考虑最优解，就要把局面转为必败局面。
II.如果当前处于某个局面，本局面\(a[1]\)^\(a[2]\)^\(...\)^\(a[n]=0\)（也就是必败局面），那么我们当前选手无论怎样取，都会转为异或和不为\(0\)的局面，也就是必胜局面，举例，如果当前某一项\(a[i]\)被我们
变成了\(a[j]\)，由于\(a[i]!=a[j]\)，在满足\(a[1]\)^\(...\)^\(a[i]\)^\(...a[n]=0\)的情况下就不能再满足\(a[1]\)^\(...\)^\(a[j]\)^\(...a[n]=0\)，情况从必败局面转为必胜局面，由II情况重新进入I情况。
综上所述，最初状态如果是必胜局面，那么处于这个局面的人必胜，否则必败。
这就是基础的\(Nim\)博弈。
#include<cstdio>
using namespace std;
int n,a[500005],maxn;
int main()
{
int ans=0,add;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans^=a[i];
if(!ans){printf("lose\n");return 0;}
for(int i=1;i<=n;i++)
{
if((ans^a[i])<=a[i])
{
printf("%d %d\n",a[i]-(ans^a[i]),i);
for(int j=1;j<=n;j++)
{
if(j==i){printf("%d ",ans^a[i]);continue;}
printf("%d ",a[j]);
}
break;
}
}
return 0;
} \(Bash\)博弈是另一类比较著名的博弈。
问题描述：两名玩家在一起玩游戏，一共有\(N\)个石子，每一次每个人可以取\(M+1\)个石子，问先手是否必胜？
分析：当\(N%(M+1)==0\)时，先手必败，否则必胜。
证明：
I.如果当前余下的石子数是\(M+1\)的倍数，假设当前选手取\(x\)个，另一个选手就可以在下一轮取走\(M+1-x\)个，余下的石子仍然是\(M+1\)的倍数，因此在这种情况下循环往复，直到最后游戏结束，面临\(M+1\)这种
情况的选手必败，因此这就是必败局面。
II.如果当前余下的石子数不是\(M+1\)的倍数，设余下的石子数\(n=k*(M+1)+r\)，因此当前选手总能取走\(r\)个，让余下的石子变成\(M+1\)的倍数，局面转入必败局面，因此，这就是必胜局面。
综上所述，当\(N%(M+1)==0\)的时候，先手必败，否则先手必胜。
证毕.
原文：https://www.cnblogs.com/valentino/p/11854431.html