#6060. 「2017 山东一轮集训 Day1」Set

异或和一般都会想到01trie 或者线性基.

发现是在任意位置选取集合元素.

那么容易想到用线性基做.

考虑令s 等于所有数的异或和.

那么x1 ^ x2 = s

考虑怎么取得max(x1 + x2)且min(x1)

把s化为2进制.

对于s的某一位x,如果该位为0且有某一个数当前位为1,

则说明有偶数个数当前位为1,即可以把集合中s1s2分配进奇数个此位为1的数

那么此时的x1 x2都取到了最大值.

如果s的某一位x,如果该位为1.

则可以把所有当前位为1的都放入s2,

此时x1 不变,x2取到了最大...

最后求出x2的值,用s^x2即可求出x1

c++代码如下:

 

9 + 5 =