取火柴游戏，洛谷之提高历练地，博弈论（3-6）

正题

      第四题：取火柴游戏

      这道题有点烦，如果结合二进制会更好懂一些。

      我们结合样例来理解：3 6 9

      

很明显，我们把它抑或起来可以发现，抑或值为1100（2）。

又因为：A[1]^A[2]^A[3]==k 且 k^k==0

所以 A[1]^A[2]^A[3]^k==0

我们的目的就是将这个东西变为0.

明显的，我们只要使A[1],A[2],A[3]中的其中一个变为A[i]^k就可以使抑或起来变为0.

有什么用？？？

因为y抑或起来变为0表示在每一位上，要不就有偶数个一，要不就全是0.

      如果k不为0，我们可以把它取为0的状态，这时我们就掌握了主动权，只要电脑取了某个位上的一个1，我们就可以在另外一个位上取到另外一个1.最后一步必定在我们手中。。

#include<cstdio>
#include<cstdlib>
#include<cstring>

int n;
long long s[500010];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&s[i]);
	long long k=0;
	for(int i=1;i<=n;i++)
		k^=s[i];
	if(k==0) 
	{
		printf("lose");
		return 0;
	}
	int x=0;
	for(int i=1;i<=n;i++)
		if((s[i]^k)<s[i]) {x=i;break;}
	printf("%lld %d\n",s[x]-(s[x]^k),x);
	s[x]=s[x]^k;
	for(int i=1;i<=n;i++)
		printf("%lld ",s[i]);
	return 0;
}