首页 > 代码库 > 【POJ2975】Nim 博弈

【POJ2975】Nim 博弈

转载请注明出处:http://blog.csdn.net/vmurder/article/details/42610939

其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。


题意:多组数据。

问先手有多少种取法使自己必胜。


题解:

首先Nim游戏的异或思想就不说了。

然后我们发现对于某个数,如果其它数的异或和比它小,那么先手拿掉这个数的一部分就可以使所有数异或为0,

先求出所有数异或和,然后再枚举每个数,异或一下就相当于其它所有数的异或和了,

然后可以进行判断出解。


长姿势:

^的优先级竟然比< 小233……

以后但凡涉及位运算都要怒写()啊!


代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1050
using namespace std;
int a[N],n;
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k,ans,ret;
	while(scanf("%d",&n),n)
	{
		for(ret=ans=0,i=1;i<=n;i++)scanf("%d",&a[i]),ans^=a[i];
		for(i=1;i<=n;i++)
		{
			if((ans^a[i])<a[i])ret++;
		}
		printf("%d\n",ret);
	}
	return 0;
}


【POJ2975】Nim 博弈