Task: ABC141F

题意：给定 $n$ 个非负整数 $x_i$，将它们分成两组。记其中一组异或和为 $a$，另一组异或和为 $b$，求 $a+b$ 的最大值。

考虑线性基。

记 $sum = \sum x_i$，求出 $a$ 的最大值，答案即为 $a+(sum \oplus a)$，其中 $\oplus$ 为异或运算。

机智的 AtCoder 把它卡掉了。但是机智的我想到，真正的最优解应该和 $a+(sum \oplus a)$ 相差不远。所以我们考虑更改 $a$ 中的最多一个数。

正式地，计算出 $\max\{(a \oplus x_i) + (sum \oplus a \oplus x_i)\}$。

机智的 AtCoder 又把它卡掉了。但是机智的我又想到，能卡掉它的数据绝大概率是手搓的，$n$ 不会很大。于是我拼上了 $O(n2^n)$ 暴力。

它过了。

AC Code

抽象。