Little Girl and Maximum XOR - 题解

比赛与标签

比赛: Codeforces Round 169 (Div. 2) 标签: bitmasks, dp, greedy, implementation, math 难度: *1700

题目大意喵~

一位可爱的小女孩给了我们两个整数 l 和 r，她想知道在 l 和 r（包括边界）这个区间里，任选两个整数 a 和 b（可以 a < b 或者 a = b），它们进行按位异或（XOR, ^）操作后，能得到的最大结果是多少呢？

简单来说，就是求 max(a ^ b)，其中 l ≤ a ≤ b ≤ r。

解题思路喵！

这道题要求我们找到一个区间内的最大异或值，一看到“最大值”和“位运算”，我们就可以嗅到一丝贪心的味道啦，喵~

要想让一个数尽可能大，我们肯定希望它的二进制表示中，从左到右（从高位到低位）尽可能都是 1。比如说，10000 (16) 就比 01111 (15) 要大。

所以，我们的策略就是：从最高位开始，依次判断我们能否让答案的这一位变成 1。

假设我们正在考虑第 k 位（二进制从右往左数，第0位，第1位...）。要想让 a ^ b 的第 k 位是 1，那么 a 和 b 的第 k 位必须不相同，一个为 0，一个为 1。

那么，我们能得到的答案的最高位是第几位呢？

让我们来观察一下 l 和 r 的二进制表示。假设 l 和 r 从最高位开始，前面几位都是相同的，直到第 k 位才第一次出现不同。因为 l < r，所以 l 的第 k 位一定是 0，而 r 的第 k 位一定是 1。

举个例子，比如 l = 8 (001000) 和 r = 16 (010000)。它们从左数第 5 位（从0开始计数的话是第4位）开始不同。 l: ...01...r: ...10...

对于比第 k 位更高的位，l 和 r 都是一样的。这意味着，在 [l, r] 区间内的任何数，在这些更高位上都和 l、r 保持一致。所以，当我们任取 a, b 时，它们在这些更高位上的值也都相同，异或起来结果就是 0。

这告诉我们一个重要的结论：a ^ b 的结果中，所有比第 k 位更高的位都必然是 0。因此，我们能得到的最大异或值，它的最高位的 1 最多也就在第 k 位上了。

那么，我们能不能让第 k 位以及所有比 k 低的位都变成 1 呢？如果可以，那得到的结果 ...00111...1 (第k位和其下的所有位都是1) 就是我们能得到的最大值了！

答案是肯定的，喵！我们可以证明，总能在这个区间里找到这样一对 a 和 b。因为 l 的第 k 位是 0，r 的第 k 位是 1，所以我们总能找到一个数 a 它的第 k 位是 0（比如 l 本身），和一个数 b 它的第 k 位是 1（比如 r 本身），并且它们都在 [l, r] 区间内。通过巧妙地构造 a 和 b 的低位，我们就可以让 a^b 的所有低位都变成 1。

我们可以构造一个数 a_target，它的前缀和 l 相同，第 k 位是 0，之后所有低位都是 1。
我们再构造一个数 b_target，它的前缀和 r 相同，第 k 位是 1，之后所有低位都是 0。
可以证明 l <= a_target < b_target <= r 总是成立的。
a_target ^ b_target 的结果就是第 k 位以及所有低位都为 1 的数。

所以，解题步骤就变得非常清晰了呐：

计算 l 和 r 的异或值，即 x = l ^ r。这个 x 的二进制表示中，为 1 的位就代表 l 和 r 在该位上是不同的。
找到 x 的最高有效位（Most Significant Bit, MSB）。也就是 x 的二进制表示中最左边的 1 是在第几位。假设是第 p 位 (从1开始数)。
我们能构造出的最大异或值，就是一个从第 p 位到第 1 位全都是 1 的数。这个数的值就是 2^p - 1。

比如 l=8 (01000), r=16 (10000)。

l ^ r = 24 (11000)。
24 的二进制表示是 11000，最高位是第 5 位。所以 p=5。
答案就是 2^5 - 1 = 31，也就是二进制的 11111。我们可以验证，取 a=15 (01111), b=16 (10000)，它们都在 [8, 16] 区间内，且 15 ^ 16 = 31。成功！

代码实现

cpp

#include <iostream>
using namespace std;

int main() {
    long long l, r;
    cin >> l >> r;

    // 计算 l 和 r 的异或值。
    // x 的最高有效位（MSB）就代表了 l 和 r 第一个不同的二进制位的位置，喵~
    long long x = l ^ r;

    // 用来记录 x 的位数，也就是最高有效位的位置（从1开始数）
    long long msb = 0;

    // 通过不断右移，计算出 x 的二进制表示有多少位
    // 比如 x = 12 (1100)，循环会执行4次，msb 最后等于 4
    while (x) {
        msb++;
        x >>= 1; // 右移一位，相当于除以2
    }

    // 构造一个拥有 msb 个 1 的二进制数，这就是我们能得到的最大异或值啦！
    // (1LL << msb) 会得到 2^msb，也就是一个 1 后面跟着 msb 个 0。
    // 再减 1，根据二进制的性质，就会变成 msb 个 1。例如 10000 - 1 = 1111。
    long long ans = (1LL << msb) - 1;

    cout << ans << endl;

    return 0;
}

复杂度分析

时间复杂度: O(log r) 的说。我们的 while 循环次数取决于输入数字 r 的二进制位数。对于 64 位整数，这个循环最多执行 64 次，所以可以看作是常数时间 O(1) 的。更精确地说是 O(log r)。
空间复杂度: O(1) 的说。我们只用了几个变量来存储 l, r, x, msb 和 ans，没有使用额外的数组或者数据结构，所以空间消耗是恒定的。

知识点与总结

这道题虽然标签很多，但核心是一个非常漂亮的贪心思想和对 位运算 的深刻理解，喵~

贪心策略: 解决“最大/最小”问题时，从高位到低位（或从大到小）依次做出最优决策是一种常见的贪心思路。在这里，我们贪心地想让答案的最高位尽可能地高，并让它为 1。
位运算性质:
- a ^ b：异或操作的核心是“不同为1，相同为0”。l ^ r 能巧妙地标记出 l 和 r 所有不同的二进制位。
- 1LL << k: 左移操作是快速计算 2^k 的方法。1LL 确保了操作数是 long long 类型，防止在 k 比较大时（比如 k=63）发生溢出。
- (1LL << k) - 1: 这是构造一个二进制表示中末尾有 k 个 1 的数字的经典技巧。
问题转化: 问题的关键在于将“求区间内最大异或对”转化为“找到 l 和 r 的最高不同位，并构造一个全为 1 的结果”。这个转化是解题的精髓所在。

希望这篇题解能帮助你理解这道有趣的题目，继续加油哦，喵~！

Little Girl and Maximum XOR - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵！ ​

代码实现 ​

复杂度分析 ​

知识点与总结 ​