题解 | #汉堡猫猫#

题解 | #汉堡猫猫#

讲一个和官方题解不太一样的做法。

一开始套路地想到从高位到低位贪心，即尽可能让高位为 ，如果能使得某一位为 ，在确保这一位为 的情况下继续向低位贪心。但这是不太好做的，因为在处理低位时，很难保证高位为 。

观察样例发现，如果序列中恰有奇数个奇数，那么答案为 ，也就是可以让答案的所有位都是 。因为我们可以让奇数都变成 ，偶数都变成 ，这样异或和就是 。

如果奇数的个数是偶数呢？由于最低位不能被修改，所以答案的最低位只能是 。那么我们可以把所有数的最低位删掉，递归处理下一位。一般地，如果对于所有 ，序列中恰有偶数个元素的第 位是 ，而有奇数个元素的第 位是 ，那么答案的第 位只能是 ，而我们可以把那些第 位是 的元素操作成

其它元素操作成

于是答案的第 位是 ，而 位是 。

还需要考虑一种情况：序列中第 为是 的元素数量为偶数，但可以调整为奇数。这需要存在某个元素的第 位和第 位不同。

最后特判一下序列全是 的情况即可。

代码