自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:42:00，当前版本为作者最后更新于2022-10-27 21:52:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 原题链接

• 听说考前写题解能rp++?

首先我们考虑平局的情况，一个比较自然的想法就是所有数异或和为零就平局，而这个结论确实也是对的，下面简单证明一下：

• 必要性：因为Alice和Bob最后会打成平局，自然有 $a = b$，所以无论如何 $a \ xor \ b = 0$ 都成立，必要性得证。

• 充分性：因为所有数异或和为零，那么将所有数任意划分为两个非空集合，这两个集合内部的元素的异或和都应该相等，那自然无论Alice和Bob怎么选数，都会形成平局，充分性得证。

那么我们就可以首先将平局的情况判断掉，下面的情况Alice不胜则负。

因为进行的是异或运算，很容易想到贪心地从高到低一位一位地考虑。假设当然在考虑第 $i$ 位，有 $x$ 个数当前这一位为 $1$ 。那么就有以下三种情况：

1. $x=1$ : 我们发现，因为我们是贪心地从高位到低位考虑，那能考虑到当前位的前提就是更高位分不出胜负，那么既然只有一个数这一位是 $1$ ，那么Alice只需要先选择这个数，那当前位一定是Alice获胜，更低位不影响胜负，则Alice必胜。

2. $x$ 为偶数：利用前面证明充分性时的技巧，我们发现因为一共有偶数个数这一位为 $1$ ，而一个偶数只能拆分成两个奇偶性相同的非负整数，那么无论对所有数怎样划分，当前这一位一定是平局。

3. $x \neq 1$ 且 $x$ 为奇数：同理，一个奇数只能拆分成两个奇偶性不同的非负整数，那么当前这一位一定能分出胜负。考虑谁能获胜，显然是拿到奇数个这一位为 $1$ 的数的人，如果所有数这一位都为 $1$ ，显然先手胜，但因为有这一位为 $0$ 的数，那拿这些数显然能使先后手顺序交换，所以可得结论：若 $n-x$ 为偶数则先手最终还是先手，Alice胜，否则Bob胜。

下附代码：

#include<bits/stdc++.h>
using namespace std;
const int M=21;
int T,n,cnt[M];
int main()
{
	scanf("%d",&T);
	while(T--)
	{		
		memset(cnt,0,sizeof cnt);
		scanf("%d",&n);
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			sum^=x;
			for(int j=0;j<M;j++)	cnt[j]+=(x>>j)&1;
		}
		if(!sum)	puts("0");
		else
		{
			for(int i=20;i>=0;i--)
			{
				if(!(cnt[i]&1))	continue;
				else if(cnt[i]==1)	puts("1");
				else if((n-cnt[i])&1)	puts("-1");
				else puts("1");
				break;
			}
		}
	}
	return 0;
}

• 完结撒花~