题解：CF2146D2 Max Sum OR (Hard Version)

沉石鱼惊旋 · 2025-09-25 14:49:46 · 题解

考虑这样一个构造：从最高位开始，如果最高位都一样就跳过，否则就代表，一定会存在 (011\dots111)_2 和 (100\dots000)_2 这两个数，把他俩或起来就取到最值了，然后显然 (011\dots111)_2-1=(011\dots110)_2 和 (100\dots000)_2+1=(100\dots001)_2，这两个也是可以配对的。

维护 l=(011\dots111)_2,r=(100\dots000)_2，每次 [l,r] 往外扩展到 [l-1,r+1]，然后把这几个位置填好。

最后会剩一点，他们的最高位是多少不重要，我们只需要递归做这个子问题即可。

cpp 提交记录：https://codeforces.com/contest/2146/submission/339811097

py 提交记录：https://codeforces.com/contest/2146/submission/339811142