自动搬运

查看原文

来自洛谷，原作者为

	blm_xxc 十年OI一场空，不开long long见祖宗

搬运于2025-08-24 23:15:27，当前版本为作者最后更新于2025-05-05 20:20:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

容易证明，每次操作总会选择 $m\gets x-m$ ，而不会选择花费 $k$ 的代价保持 $m$ 不变，因为最后要进行异或运算时，只关注每个 $a$ 在每一位上出现 $1$ 的次数的奇偶性，而不是次数(即不是次数越多越好)，所以对于 $m$ 的每一位 $1$，只需要使用一次即可。

所以，本题的 $k$ 是没有用的！！！

可以看作先将预处理出 $a$ 的异或和 $sum$，再将 $sum$ 与 $m$ 进行或运算。

但这么做并没有得到满分，why？

注意到，当每一个 $a$ 在某一位上均为 $1$ 时，此时该位出现 $1$ 的次数无法改变(因为进行与运算只会使 $1$ 的个数越来越多，而无法减少)，所以当这一位的异或和为 $0$ 时，无法通过和 $m$ 的与运算将其变为 $1$。

所以，我们要判断是否存在某些位，所有 $a$ 在这些位上均为 $1$。

此时，只需要增加一个变量 $p$ ，将其初始化为 $2^{31}-1$，每次输入时与 $a$ 进行与运算，即可判断在哪些位上所有 $a$ 均为 $1$。

最后，如何通过 $sum$，$m$ 和 $p$ 得出最后的答案 $ans$？

注意到，当某一位上 $sum$ 为 $1$ 时，$ans$ 在这一位上一定为 $1$；若 $sum$ 为0，则只有 $m$ 在这一位上为 $1$，p 在这一位上为 $0$ 时，$ans$ 才为$1$，由此可得：

• $ans=sum|((m \oplus p)\&m)$

有了这个，本题就迎刃而解。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int T,n,m,k,ans,p;
inline int read(){
	int p=1,k=0;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') p=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		k=k*10+c-'0';
		c=getchar();
	}
	return p*k;
}
int main(){
	T=read();
	while(T--){
		n=read(),m=read(),k=read(),ans=0,p=2147483647;
		for(int i=0;i<n;++i){
			int a;
			a=read();
			ans^=a;
			p&=a;
		}
		ans=ans|((m^p)&m);
		printf("%d\n",ans);
	}
	return 0;
}

加入快读以后可以跑到 100~200ms 哦！awa