关于此题CF[Hello 2025] 2057C - Trip to the Olympiad的一些总结

传送门
题目大意：给定两个数l,r，试求l~r中选三个数a,b,c，使得\((a xor b) + (b xor c) + (a xor c)\)的值最大。

有关此类异或最大的题目，首先想到的是确定最高位，因为假如说异或后二进制下k位置为1，那么此时答案就已经比k位置不为1，而k以后的位置都是1的情况要大了。而观察l,r这两个数，我们如果想要确定两个数异或之后可能的最高位的1，就一定要找到l与r这两个数二进制下从高位到低位第一个不一样的位置，那么这个位置就是对应的k位置。

找到这个k位置之后，我们发现两个数异或起来的最大值就是\(1+2+2^{2}+...+2^{k}\)，也就是异或之后k位置即以后都变成1的情况，由于题目只需要我们找到一组答案即可，那么我们此时其实就已经可以确定答案中的两个数了，即，第一个数为，k以前的位与l,r相同（因为k是从高到低位上l,r第一个不同的位），k位置为1，往后全为0，这样的话这个数一定会小于等于r（因为实际上，k位置上l,r不同，这个位置上一定是r为1，l为0）；第二个数为，k以前的位与l,r相同，k位置为0，往后全为1，这样的话这个数一定大于等于l。

那么我们只需要再确定第三个数即可。我们发现，仅仅考虑k位置及其往后的位，不管这第三个数的这些位置上是0还是1，它与前面已经确定的那两个数分别异或之后再加起来，得到的数总是定值，也就是前面提到的\(1+2+2^{2}+...+2^{k}\)，所以第三个数只需要在\([l,r]\)范围内随便找一个不是上述确定的两个数的另外一个数即可。

代码如下：

#include<bits/stdc++.h>

using namespace std;

int t,l,r;

void solve() {
    cin >> l >> r;
    int k = 31 - __builtin_clz(l ^ r);
    int a = l | ((1 << k) - 1);
    int b = a + 1;
    int c = (a == l ? r : l);
    cout << a << ' ' << b << ' ' << c << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while(t--) solve();

    return 0;
}