我正在努力解决这个问题 Codeforces 276D .最初我使用了一种蛮力方法，对于大输入显然失败了(当输入为 10000000000 20000000000 时开始)。在教程 Fcdkbear(竞赛的 turtor)中讨论了状态为 d[p][fl1][fr1][fl2][fr2] 的 dp 解决方案。
在教程中进一步
我们需要知道，我们可以将哪些位放入第 p 个位置的数字 а 的二进制表示中。如果以下条件为真，我们可以放置 0:L 的第 p 位等于 0，或者 L 的第 p 位等于 1，并且变量 fl1 表明 a 的当前值严格大于 L。类似地，如果以下条件为真，我们可以放置 1:R 的第 p 位等于 1，或者 R 的第 p 位等于 0 并且变量 fr1 表明 a 的当前值严格小于 R。类似地，我们可以获得，我们可以将哪些位放入第 p 个位置的数字 b 的二进制表示中。
这让我头疼，因为当 L 的第 i 位为 0 时，我们怎么能在第 i 位中放置一个 0。如果 L 和 R 都在同一个桶中(第 2^i 个边界，如 16 和 24)，我们最终会将 0 放在第 4 个，而如果 a = 20，我们可以放置 1，因为 R 的第 i 位是0 和 > R。我想知道检查是否 > L 有什么用。
本质上我不明白
- 有哪些状态
- 我们如何复现
我知道这可能有点矫枉过正，但有人可以用描述性的方式解释一下吗，因为社论太短，无法解释任何内容。
我已经看过了 here但建议的解决方案与社论中给出的解决方案不同。我也知道这可以通过二进制搜索来解决，但我只关心 DP 解决方案
最佳答案
如果我答对了:开始从左 (MSB) 到右 (LSB) 比较 l 和 r 的位。只要这些位相等，就没有选择的自由，相同的位必须出现在 a 和 b 中。第一个不同的位在 r 中必须是 1，在 l 中必须是 0。它们也必须出现在 a (0) 和 b(1) 中。从这里您可以最大化 XOR 结果。只需对 b 使用零，对 a 使用一个。给出 a+1==b 并且异或结果是 a+b，它总是 2^n-1。
关于algorithm - 数字范围的最大异或，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30821694/