博弈
一、巴什博奕
1.定义
巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，最多取m个。最后取光者得胜。
例：两人取n张牌，每次最少取1张，最多取m张,取到最后一张的赢。输入n和m，输出谁必胜
#include <iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
if(n%(1+m)==0)
cout<<"Second";
else
cout<<"First";
}
2.组合游戏
1.有两个玩家 2.游戏的操作状态是一个有限的集合 3.游戏双方轮流操作 4.双方每次操作都必须符合游戏规则 5.一方无法进行操作是游戏结束 6.不管怎么操作，经过有限步游戏结束
3.必败点与必胜点
必败点P：前一个选手取胜的位置，即谁先走到这个位置谁赢。 必胜点N：后一个选手取胜的位置，即谁先走到这个位置谁输。
属性： 1.终点必定是必败点（P点）。因为在终点时，已经没办法走了，那么就是从前一个位置进入这个位置的人获胜。 2.对于必败点（P点），能一步进入这个点的必定是必胜点，而必败点无论怎么走，也只能进入必败点。 3.对于必胜点（N点），可以进入必败点，也可以进入必胜点。也就是说，必胜点可以由必胜点进入，也可以由必败点进入。
即：
1.所有终结点是必败点（P点）； 2.从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）； 3.无论如何操作， 从必败点（P点）都只能进入必胜点（N点）.
步骤： 1.将所有终结位置标记为必败点（P点） 2.将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点） 3.如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） 4.如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。
例：有m*n棋盘，从(1,m)开始，可以向左、下、左下走，谁先走到(n,m)谁赢 输入m，n，输出谁赢
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int m,n;
while(~scanf("%d,%d",&m,&n))
if(m%2==1&&n%2==1)
cout<<"First";
else
cout<<"Second";
}
二、威佐夫博弈
1.定义
威佐夫博弈（Wythoff’s game）：有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（a[k]，b[k]）（a[k] ≤ b[k] ,k=0，1，2，…,n)（表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。注：k表示奇异局势的序号， 第一个奇异局势k=0。 可以看出,a[0]=b[0]=0,a[k]是未在前面出现过的最小自然数,而 b[k]= a[k] + k。
#include <iostream>
#include <cmath>
using namespace std;
int main(int argc, char const *argv[])
{
int n,m;
cin>>n>>m;
int a=max(n,m),b=min(n,m);
if(int((a-b)*(sqrt(5)+1)/2)==b)
cout<<"B";
else
cout<<"A";
return 0;
}
输出策略：
#include <iostream>
#include <cmath>
using namespace std;
int main(int argc, char const *argv[])
{
int n,m;
cin>>n>>m;
int a=max(n,m),b=min(n,m);
if(int((a-b)*(sqrt(5)+1)/2)==b)
cout<<"0"<<endl;
else
{
cout<<"1"<<endl;
for(int i=1;i<=a;i++)
if(int((a-b)*(sqrt(5)+1)/2)==b-i)
cout<<b-i<<" "<<a-i<<endl;
for(int i=1;i<=a;i++)
if(int(abs(a-b-i)*(sqrt(5)+1)/2)==min(a-i,b))
cout<<min(a-i,b)<<" "<<max(a-i,b)<<endl;
else
if(int((a-b+i)*(sqrt(5)+1)/2)==b-i)
cout<<b-i<<" "<<a<<endl;
}
return 0;
}
三、尼姆博奕
1.基础：异或运算
定义：异或（xor）是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为：
a⊕b = (¬a ∧ b) ∨ (a ∧¬b)
如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。 异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。
例：输入11个数，其中只有1个数出现了奇数次，输出那个数
#include <iostream>
using namespace std;
int main()
{
int num,result=0;
for(int i=1;i<=11;i++)
{
cin>>num;
result^=num;
}
cout<<result;
}
2.尼姆博奕
定义：有三堆及以上各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
我们以三堆为例。
它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论自己如何拿，接下来对手都可以将其变为（0，n，n）的情形。 计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号⊕表示这种运算，先看（1，2，3）的按位模2加的结果： 1 =二进制01 2 =二进制10 3 =二进制11 ⊕ ——————— 0 =二进制00 （注意不进位） 对于奇异局势（0，n，n）也一样，结果也是0。 任何奇异局势（a，b，c）都有a⊕b⊕c =0。 注意到异或运算的交换律和结合律，及a⊕a=0，: a⊕b⊕(a⊕b)=(a⊕a)⊕(b⊕b)=0⊕0=0。 所以从一个非奇异局势向一个奇异局势转换的方式可以是： 1）使 a = c⊕b 2）使 b = a⊕c 3）使 c = a⊕b
#include <iostream>
using namespace std;
#define MAX 10000
int main()
{
int n,pile[MAX],result=0,num;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>pile[i];
result^=pile[i];
}
if(result==0)
cout<<"Second Win"<<endl;
else
{
cout<<"First Win"<<endl;
for(int i=1;i<=n;i++)
{
int n=result^pile[i];
if(n<=pile[i])
{
cout<<pile[i]-result<<" ";
num=i+1;
break;
}
else
cout<<pile[i]<<" ";
}
for(num;num<=n;num++)
cout<<pile[num]<<" ";
}
}
