CF2146D Max Sum OR

· · 题解

很好的题，但是没有场切。

首先发现这是一个位运算的题目。对于一个数学类的题目，我们有几个通用方法，一个是一定的性质的寻找，另一个就是手玩样例/自己的数据来获得启发。特别的，位运算的题目往往要通过考虑数位解决问题。这个题目就是一句这样的思想做出来的。

D1:

首先发现这个答案是 \sum a_i | b_i，所以我们考虑一定的转化，可以转化成 a_i + b_i - (a_i \operatorname{and} b_i)，但是这个并没有任何作用。所有我们考虑找一些性质，发现如果两个数没有任何的数位重合，或者说互补，比如 1001 和 110，这样的数字组合起来一定是最优秀的，因为就算他们和其他的组合，这两个数的贡献也一定不会大于这两个组合。

现在还是不会做，由于是位运算的题目，我们开始找一些和位相关的性质。我们发现，对于位数最多的一些数 x \ge 2^t，他们如果可以和 2^t 的数配对，就一定不会和这一层的配对。由于我们的区间是 [0,r]，所以任意时刻最高层的数量都是小于等于下面的。所以我们考虑对于每一层分别考虑，然后计算每一层的贡献，再转化成更小的子问题。但是这样我们是不会输出方案的。

我们考虑看样例。通过样例我们发现 D1 中所有的答案都是取到了 sum \times 2。这其实我们考虑所有互补的数。可以证明，这样互补的数是一对一对存在的，所以我们可以对于每一个数都计算一下互补的数。然后记录答案即可。

提交记录 - CF2146D1

时间复杂度：O(n \log n)

这个题的思想：位运算题具有的位的性质 + 手玩样例。

为什么想出来了：正确方式分析了位运算的性质并且对样例进行了手玩。

D2

其实我们刚才说的那个减少问题规模的思想已经是接近正解了，但是还是不是。

由于是区间，尝试差分，但是并无效果。

我们收到 D1 的启发，不妨再次看看样例。我们发现答案并不是简单的 sum \times 2 了，所以我们进一步分析。

其实是这样：我们还是按位进行考虑，我们发现对于我们刚才特定的 2^t 来说，上面的数多和下面的数多的情况是不一样的，但是都是可以减小问题规模的，还是那个问题，我们无法正确的输出构造数组。

玩一下样例，发现一个事情：0111111 和 1000000 在一个 -1 一个 +1 的情况下还是互补的。这个性质很重要，也很漂亮。我愿意称之为 "二进制的对称性"。有了这个性质，我们就可以在 2^t 和 2^t - 1 这几位开始配对，每次 +1, -1。考虑这样操作的复杂度。如果 l,r 最高位相同，那么我们不用考虑，直接加上即可，否则我们可以进行刚才说的操作。本质上我们还是在考虑每一位，但是这次我们正好可以消除很多数字，而不是转化成更小的。

时间复杂度：O(n \log n)

提交记录 - CF2146D2

这个题的思想：对位运算性质的考察。二进制数的 "对称性" 使得每一次或都是可以通过 +1-1 得到最优的，按位进行考虑即可。

为什么没想出来：因为没有手玩样例。

营养点：

还是败在了手玩样例上。