自动搬运

查看原文

来自洛谷，原作者为

	宁_缺 毕竟几人真得鹿，不知终日梦为鱼。

搬运于2025-08-24 21:58:44，当前版本为作者最后更新于2020-02-18 18:38:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

貌似题解区的某几位dalao太巨了，寥寥几笔就写完了题解，然而我觉得那几篇实在太简略了些，于是便写了这篇题解

$\color{black}\text{原题链接}$

相信你们都做过nim游戏的模板，知道先手的必胜/败条件

那么，本题中，先手要胜利，则必须让后手无论拿掉哪几堆都弄不出异或和为0的情况。显然，这要用到线性基。

在插入线性基时，如果没成功插入，即最后x=0，那么意味着会出现异或和为0的情况，这时就要把x取走。显然，聪明的先手一定必胜，所以这题输出-1是不可能得分的了，我们只用考虑如何让取走的数量最小。

这时我们就要用到贪心思想：从大到小来试，能插入就插入，不能则取走。

那为啥这样结果最小呢？

粗略的证明一下，因为异或是不进位加法，那么，如果不是从大到小，假设a^b^…=x(a≤b≤...≤x)，由于中途没有进位，因此，a^b^…≤a+b+...,所以显然取走x比取走那几堆更优。

如果并不是a≤b≤...≤x呢？排个序呗。

于是就大致的说明了为毛要这样贪心了。

但显然这样是不严谨的。因此想看严谨的证明还请去看Jaihk662大佬的文章。

代码如下：

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define LL long long
int n,a[101],d[31];LL ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	std::sort(a+1,a+n+1);
	for(int x=a[n];n;--n,x=a[n]){
		for(int j=30;j>=0;--j)
			if((x>>j)&1)
				if(d[j])x^=d[j];
				else{d[j]=x;break;}
		if(!x)ans+=a[n];
	}
	return printf("%lld\n",ans)*0;
}

谢君曾共霜雪 不辞生死长约