做题小计 魔法手杖

· · 个人记录

This

我先说说一开始的想法。

根据经典套路，答案要求最小的东西最大，那么这种异或的题就从最高位开始考虑。

考虑最高位是否能为 1 。这是一个经典套路，分类讨论 x 最高位是什么。

如果 x 最高位取 0 ，保证这一位是 1 ，需要保证第一位是 0 的所有数都改为加法。显然的，如果第一位是 0 不改为加，那么这一位肯定会有一位 0 ，不符合。

如果 x 最高位取 1 ，保证第一位是 1 的数全都改为加法，这也是很显然的。

然后就开始口胡我的错误猜想了，如果取 1 ，那么其实很明显，加直接进位了，这一位就不用管了。

如果取 0 就很麻烦，不知道怎么搞，要保证以后进位到当前位，直接给我 cpu 赣烧了，一开始是想找到第一位为 1 的数，然后这些位都取 1 就能进位了。这异或可以直接扔到 Trie 上乱搞。

折腾很久后，才默默点开题解……

其实忽略了一个很重要的性质：对于改为加的部分，只需要管理最小那个就可以了！

这样子我们就完美的保存的两个状态：加和异或。每次分讨就简单许多，每次操作保证最小的加上 x 再加上当前操作的最优值要大于得到目前的答案，这一步就保证了刚才进位之难， 很容易判断能不能走左右子树了。

当前操作对于全是加的部分，要得到最大值，很明显就是后面全取 1 就行。虽然不知道这样对后面合不合法，但是这样能得到这一位满足是 1 ，后面怎么样都没有关系。

对于无论 x 怎么取都取不到 1 的部分，最优这一位就是啥都不干，都是异或，0 就问 0 部分， 1 就问 1 部分，可以保证另一半一定是大于当前的。

最后要么就询问完所有位，要么就走到空子树。

走到空子树意味着所有东西都已经处理好了，只需要管当前操作最小值就好了。很明显，对于只有加没有异或的部分，直接返回最优的即可。

直接左右子树递归就行了。