题解 SP25844 / CF276D【MAXXOR - Find the max XOR value / Little Girl and Maximum XOR】

以下用 \(\oplus\) 表示异或运算。

先说结论：设 \(x=L\oplus R\)，则答案为最小的 \(2^k-1\) 使得 \(2^k-1\ge x\) 即 \(2^k > x\)。

（一）答案不可能超过 \(2^k-1\)。

为了让异或后最高位尽量高，我们先取一个最高位最高的数，也就是 \(R\)，然后再取一个数使得该位尽量为 \(0\)。

如果 \(L\) 的该位为 \(0\)，符合条件，此时答案最高位与 \(x\) 都相同，而 \(2^k-1\) 是最高位相同的最大的数，所以答案一定不超过 \(2^k-1\)。如果 \(L\) 的该位为 \(1\)，则该位异或出来为 \(0\)，不考虑这一位，去找后面的位也是同理。极端情况是 \(L=R\)，此时 \(x=0\)，\(2^k-1=0\) 也是没有问题的。

（二）答案可以取到 \(2^k-1\)。

我们称在二进制下表示 \(0\) 或 \(2^i\) 的数位为“第 \(i\) 位”。

因为 \(x=L\oplus R\) 在第 \(k-1\) 位为 \(1\)，说明 \(L\sim R\) 之间有一个位置的第 \(k-1\) 位发生了变化。而 \(L\sim R\) 是连续变化的，每次加一，也就是说必然有一个位置从 \(\underbrace{11\cdots 1}_{k-1\ \text{个}}\) 变成了 \(1\underbrace{00\cdots 0}_{k-1\ \text{个}}\)，显然这两个数的异或为 \(2^k-1\)。

综上，结论正确。

//By: Luogu@rui_er(122461)
#include 
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

template void chkmin(T& x, T y) {if(x > y) x = y;}
template void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
    int L, R;
    scanf("%d%d", &L, &R);
    R ^= L;
    for(int i=0;;i++) {
        if((1 << i) > R) {
            printf("%d\n", (1 << i) - 1);
            break;
        }
    } 
    return 0;
}

顺带一提，因为数据水，第 \(18\) 行的大于号打成大于等于也可以通过，但显然不对，例如 \(L=2,R=3\)。