hdoj1850——关于nim博弈

nim和:a^b^c=0时为必败态(奇异局势)
有m堆石子,若先手可胜,则先手第一次取有几种方案
1。首先一点,因为是第一次取,取得时候可以保证有m堆(这是废话。。),因此最多有m种取石子方案(也就是说最多的情况下,每堆石子取一些石子可以构成一种方案)
为什么不可能一堆石子取出x个达到必败态,取出y个也达到必败态呢?(x!=y)
这个问题其实很好回答。假设3堆石子分别为11,12,14,那么
11d=(1011)b
12d=(1100)b
14d=(1110)b
因为只能取不能加,所以只能把1改成0(即把数变小),可见,如果我们从第一堆取石子使达到必败态,那么就需要改动含有奇数个1的列,也就是第1列和第4列,变成
2d=(0010)b
12d=(1100)b
14d=(1110)b
即第一堆取出11-2=9个石子,显然有奇数个1的列都要改,所以如果某一堆石子取出x个石子后可以达到必败态,则x唯一
2。a^a=0,0^a=a
上述公式应当是学计算机的同学都十分熟悉的,这是基本功(否则就只能算计算机爱好者了。。)
那么很容易得出a^b^c=(a^b^c^d)^d;意即一个数被异或在sum内,那么只要sum再异或一次该数,效果相当于该数从sum中踢了出去(表达不好,自己理解==!。。。)
3。(a^b)^(a^b)=0(就是上面公式a^a=0),假设3堆石子a,b,c。c>(a^b),那么显然如果从c堆取出x个石子使之达到必败态,只需要把c变为a^b。这样得:x=c-a^b。
综合以上几点,文章开始的问题也就解出来了。。
下面是代码

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int m;
	scanf("%d",&m);
	while(m!=0)
	{
		int i,a[102],sum=0;
		for(i=1;i<=m;i++)
		{
			scanf("%d",&a[i]);
			sum=sum^a[i];
		}
		if(sum==0)
			printf("0\n");
		else
		{
			int ans=0;
			for(i=1;i<=m;i++)
				if(a[i]>(sum^a[i]))
					ans++;
			printf("%d\n",ans);
		
		
		}
		scanf("%d",&m);
	}

//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>