C. Trip to the Olympiad 解题思路

核心目标与异或性质分析

本题要求在给定范围 $[L, R]$ 内，找到三个互不相同的数字 $a, b, c$，使得目标和 $\text{Sum} = (a \oplus b) + (b \oplus c) + (c \oplus a)$ 最大。

我们首先分析异或和的性质。对于任意一个二进制位 $i$，它对总和 $\text{Sum}$ 的贡献是 $ 2^i$ 乘以该位上三个异或结果 $(a \oplus b)_i, (b \oplus c)_i, (c \oplus a)_i$ 之和。

在一个特定的位 $i$ 上，数字 $a, b, c$ 的位值（bit values）只有四种组合会产生非零贡献：

  1. $(0, 0, 1)$ 或其排列： 此时 $(a \oplus b)_i = 0, (b \oplus c)_i = 1, (c \oplus a)_i = 1$。总和为 $ 0 + 1 + 1 = 2$。
  2. $(1, 1, 0)$ 或其排列： 此时 $(a \oplus b)_i = 0, (b \oplus c)_i = 1, (c \oplus a)_i = 1$。总和为 $ 0 + 1 + 1 = 2$。
  3. $(0, 0, 0)$ 或 $(1, 1, 1)$： 此时所有异或结果均为 $ 0$。总和为 $ 0$。

因此，要使总和 $\text{Sum}$ 最大，我们应该尽量使高位的三个数字在该位上呈现 $(0, 0, 1)$ 或 $(1, 1, 0)$ 的模式，以保证每一位都能贡献最大值 $ 2 \cdot 2^i$。

寻找关键位 $k$

由于 $a, b, c$ 必须在 $[L, R]$ 范围内，我们不能随意构造数字。最大的挑战在于范围约束。

我们考虑范围的两个端点 $L$ 和 $R$。它们之间的最高不同位是限制我们能构造出多少高位 $ 1$ 的关键。

  1. 计算 $L \oplus R$： 得到一个数，其最高位 $k$ 标志着 $L$ 和 $R$ 在 $ 2^k$ 这一位上是不同的，而在所有更高的位（ $k+1, k+2, \dots$ ）上是相同的。
  2. 确定关键位 $k$： $k$ 即为 $L \oplus R$ 的最高设置位（Most Significant Bit, MSB）的索引。
  • 如果 $L = R$，则 $L \oplus R = 0$，此时 $k=0$（或 $-1$，我们取 $k=0$ 作为安全底线）。
  • 如果 $L \neq R$，则 如果 $L \neq R$，则 $k$ 为 $L \oplus R$ 的最高设置位（MSB）索引，且 $k > 0$。

构造最优解 $a, b, c$

在位 $k$ 以上，所有 $[L, R]$ 范围内的数字都与 $L$ 和 $R$ 相同。我们最大化目标和的潜力在于位 $ 0$ 到 位 $k$。为了最大化贡献，我们希望 $a, b, c$ 在这 $k+1$ 位上实现全 $ 1$ 模式的最高贡献。

我们构造两个数 $a$ 和 $b$ 如下：

  1. 构造 $a$： 我们取 $L$ 的高位部分，并在位 $ 0$ 到 位 $k-1$ 上全部设置为 $ 1$。

    这样构造的 $a$ 满足 $L \le a \le R$ 的条件，因为它只在 $L$ 的低位上做了“或 $ 1$”操作，且 $L$ 和 $R$ 在位 $k$ 上不同。

  2. 构造 $b$： 我们希望 $b$ 能实现与 $a$ 在位 $k$ 上的翻转，并使低位部分尽可能贡献 $ 1$。

    分析 $a$ 和 $b$：

    • $a$ 在位 $k$ 以下全为 $ 1$。
    • $b = a+1$ 将使位 $k$ 以下全变为 $ 0$，并使位 $k$ 上的值从 $a$ 的值翻转（即 $a_k \neq b_k$）。
    • 由于 $a$ 是由 $L$ 通过“或 $ 1$”操作得到的，它必然满足 $L \le a \le R$。
    • $b = a+1$ 必然满足 $L \le b \le R$。这是因为 $R$ 的高位部分与 $L$ 相同，但 $R$ 的位 $k$ 是 $ 1$，而 $L$ 的位 $k$ 是 $ 0$。$a$ 和 $b$ 相当于取到了这个范围内的“最大跨度”数字。

  3. 构造 $c$： 既然 $a$ 和 $b$ 已经实现了在关键位 $k$ 上的翻转，以及在所有低位上对 $\text{Sum}$ 的最大贡献（通过 $a$ 在 $k-1$ 位以下全是 $ 1$），剩下的第三个数字 $c$ 只需要满足：

    • $L \le c \le R$
    • $c \neq a$ 且 $c \neq b$（题目要求互不相同，但实际上对于最大化 $\text{Sum}$ 的影响不大，只要有三个数能达到最大 $\text{Sum}$ 即可）。

    最简单的取法是取 $c = L$ 或 $c = R$，只要它不与 $a$ 或 $b$ 重复即可。由于范围 $[L, R]$ 至少包含 $ 3$ 个数，我们可以保证找到一个不重复的 $c$。

    例如，我们简单取 $c = (a == L ? R : L)$。

C++ 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

// 函数：获取最高设置位的索引
int get_msb_index(i64 n) {
    if (n == 0) {
        return -1;
    }

    // 从 63 位开始向下查找第一个 1
    for (int i = 63; i >= 0; --i) {
        if (n & (1LL << i)) {
            return i;
        }
    }
    return -1; // 理论上 n != 0 不会走到这里
}


void solve() {

    i64 l, r;
    cin >> l >> r;

    // 1. 找出 L 和 R 的最高不同位 k
    i64 xor_result = l ^ r;
    int k = get_msb_index(xor_result);

    // 边界情况：如果 L = R，则 k = -1。
    if (k < 0) {
        k = 0; // 此时 k 不影响后续 mask 的构造，但保证 a 至少是 l
    }

    // 2. 构造 mask，即 k 位以下的 1 ( 2^k - 1 )
    i64 mask = (1LL << k) - 1;

    // 3. 构造 a: L 的高位部分 + k 位以下全 1
    i64 a = l | mask;

    // 4. 构造 b: a + 1。
    i64 b = a + 1;

    // 5. 构造 c: 随便取 L 或 R 中与 a 不重复的一个。
    i64 c = (a == l ? r : l);

    // 实际验证：对于 L=99, R=109。
    // L = (01100011)_2, R = (01101101)_2
    // L ^ R = (00001110)_2. MSB k=3. mask =(00000111)_2 = 7.
    // a = L | 7 = 99 | 7 = 103. b = 104. c = 109.
    // (103 ^ 104) + (104 ^ 109) + (109 ^ 103) = 7 + 13 + 10 = 30.
    // 这是最大值。

    cout << a << " " << b << " " << c << "\n";
}

int main() {

    // 优化 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int test;
    cin >> test;

    while (test--) {
        solve();
    }
}