一、尼姆博奕（Nimm Game）：

       有N堆石头,每堆石头数目在1到100之间，最多有10堆.两人分别取走石头.取石头的规则是：每次只能从1堆中取,每次取走至少1个。取过后还可以把这堆的石头任意分配到其它石子数不为0的堆上，当然也可以不分配。问给定这些石头堆的情况，两人轮流取，谁取走最后一个石子谁胜利，问是先取的胜利还是后取的胜利.双方最优策略。

     POJ - 2234

必败局面：也叫奇异局势。无论做出何出操作，最终结果都是输的局面。必败局面经过2次操作后，可以达到另一个必败局面。
必胜局面：经过1次操作后可以达到必败局面。
即当前局面不是必败局面就是必胜局面，而必胜局面可以一步转变成必败局面。
最终状态：
（1）最后剩下一堆石子；（必胜局面）
（2）剩下两堆，每堆一个；（必败局面）
（3）当石子剩下两堆，其中一堆只剩下1颗，另一堆剩下多于n颗石子时，当前取的人只需将多于1颗的那一堆取出n-1颗，则局面变为刚才提到的必败局面。（必胜局面）
判断当前局势是否为必胜（必败）局势：
1）把所有堆的石子数目用二进制数表示出来，当全部这些数按位异或结果为0时当前局面为必败局面，否则为必胜局面；
2）在必胜局面下，因为所有数按位异或的结果是大于零的，那么通过一次取，将这个（大于其它所有数按位异或的结果的）数下降到其它所有数按位异或的结果，这时局面就变为必败局面了。

例：

      45 ^ 45 = 0，所以先手必输；

      3 ^ 6  ^ 9 不为0，所以先手必赢。

    把所有的数异或，结果为0时先手必败，否则先手必胜。

代码：

#include<stdio.h>
int main()
{
	int a[22];
	int m,n,i;
	while(~scanf("%d",&m))
	{
		for(i=1;i<=m;i++)
			scanf("%d",&a[i]);
		n = a[1];
		for(i=2;i<=m;i++)
		{
			n^=a[i];
		}
		if(n!=0)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
 } 

二、A New Stone Game（Nim变形）

     有任意堆石子，两个选手A和B，他们每次可以移动任意一堆中的石子，移动后也可以放在其他石子不为0的堆中，总是A先，问胜负。

    POJ - 1740

1） 只有一堆时，先手必赢。

（2）有两堆时，只有两堆相同的时候先手会输。若两堆不同，先手可以造成两堆相同的局面从而不输。

（3）有三堆时，先手可以先拿走一堆，制造两堆相同的情况。

            ……

    由此发现，将n堆石子排序，当堆数为偶数并且是成对出现的，则先手必输。因为先手并不能取光所有的，而后手只要模仿先手的行为就能一直有石子可取。

继续推理发现，只有在上述情况下先手必输。

    只需判断出堆数为偶数并且成对出现的情况即可。

代码：

#include<stdio.h>
int main()
{
	int n,i,j,t;
	int a[110];
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(i=1;i<n;i++)
			for(j=i+1;j<=n;j++)
			{
				if(a[i]>a[j])
				{
					t=a[i];
					a[i]=a[j];
					a[j]=t;
				}
			}
		if(n%2==1)
		{
			printf("1\n");
		}
		else
		{
			for(i=1;i<=n;i=i+2)
			{
				if(a[i]!=a[i+1])
				{
					printf("1\n");
					break;
				}
			}
			if(i>n)
				printf("0\n");
		}
	 } 
	 return 0;
}

三、威佐夫博奕（Wythoff Game）：

    有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

  HDU - 1527

   首先我们用一个二维的状态（a,b）来记录剩下的石子数。a表示第一堆剩下的石子数，b表示第二堆剩下的石子数（a,b顺序与结果无关），A,B 两个人取石子，总是A先取。

   那么如果某个人遇到了这样的状态(0,0)那么也就是说这个人输了。那么接下来的几个失败态为(1,2),(3,5),(4,7),(6,10),(8,13)……并称这些必败状态为“奇异局势”，也可以叫做失败态，鬼知道为啥叫奇异局势。

   我们用a[i]表示失败态中的第一个,b[i]表示失败态中的第二个.(i从1开始).

  那么我们可以看到b[i] = a[i]+i;（i >= 0）,a[i]是前面的失败态中没有出现过的最小的整数。

  那么，得到公式如下：

     m = (int) [ (sqrt(5) + 1.0)/2.0 * k]

     a , b 分别为两堆得石子数，如果a<b,交换a、b的值。

     k = b-a ；

    如果 m == a ，先手必败，否则先手必胜。

（1）每个自然数都包含在且只包含在一个奇异局势中。

（2）对任意的奇异局势，任何合法的操作都会使其成为非奇异局势，也就是奇异局势的所有后继状态均为非奇异局势。

（3）任何非奇异局势都可以通过某种合法操作得到奇异局势，即奇异局势的所有后继状态中存在奇异局势。

  碰到轮流取石子，可以从一堆取，也可以从两堆取同样的个数时，就套上面的公式就行了。

代码：

#include<stdio.h>
#include<math.h>
int main()
{
	int a,b,i,k,t,q;
	double p=(1+sqrt(5.0))/2.0;
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		if(a>b)
		{
			t=a;
			a=b;
			b=t;
		}
		k=b-a;
		q=int(k*p);
		if(q==a)
			printf("0\n");
		else
		{
			printf("1\n");
		}
			
	}
	return 0;
}

四、巴什博弈

      一堆只有n个物品，两人轮流从堆中取，最少一个，最多m个，最后取光者胜。

     如果n=m+1。后手胜。取胜法则n=(m+1)*r+s。其中r为任意自然数，s<=m。若s不为0则先手胜，因为先手总会给后手留下(m+1)倍数个。

五、 斐波那契博弈：

    有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜。

  HDU - 2516

   当且仅当n不是斐波那契数时，先手必胜。（n为总物品数）

代码：

#include<stdio.h>
int main()
{
	long long f[55];
	int i,n,flag;
	f[0]=f[1]=1;
	for(i=2;i<55;i++)
		f[i]=f[i-1]+f[i-2];
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		flag=0;
		for(i=0;i<55;i++)
		if(n==f[i])
		{
			printf("Second win\n");
			flag=1;
			break;
		}
		if(flag==0)
		printf("First win\n");	
	}
	return 0;
}