$Luogu$ $P5514$ $[MtOI2019]$ 永夜的报应

链接

背景

(disangan233) ，迷途之家 (2019) 联赛 ((MtOI2019)) (T1) ， (Luogu) (P5514)

题意

给定 (n) 个 (int) 范围内的整数，将其中每个数分至某一组后，使得各组内数异或和之和最小的异或和之和。

解法

假设所有数的异或和在 (2^t) 位为 (0) ，那么分到一组对答案没有贡献。
假设所有数的异或和在 (2^t) 位为 (1) ，那么显然无论如何分组， (2^t) 位对答案的总贡献都不会为 (0) （因为当前位有奇数个 (1) ），即 (1) 是答案下界。
因此，将所有数分为一组即为最优答案，输出所有数的异或和即可，时间复杂度 (O(n)) 。
(8.24) (17：43) (update) ：根据 (@Air\_Castle) 的思路，异或的本质是不进位的加法，而直接相加是要进位的，故异或次数越多越好。而所有数的异或和就是异或次数最多的结果。

(trick)

(1.) 位运算题目大力按位讨论即可。

代码

$View$ $Code$

//省略头文件
using namespace std;
inline int read()
{
	int ret=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		ret=(ret<<1)+(ret<<3)+ch-'0';
		ch=getchar();
	}
	return ret*f;
}
int n,ans;
int main()
{
	n=read();
	while(n--)
		ans^=read();
	printf("%d
",ans);
	return 0;
}