HDU 5969 最大的位或 题解

题目大意

给定 \(l, r\) ，求所有 \(l\leq a\leq b\leq r\) 的最大 \(a\,|\,b\) 异或值。

题解

我们按二进制逐位考虑，在前缀的部分我们发现，如果上下界该位相等，则没有选择的余地（利用数位 \(\text{trie}\) 树表示比较好理解，转化为一个二进制下的字典树），假设我们扫描到了第一个上下界该位不等的地方，之后一定会在字典树上取连续的一些叶子节点，由于异或只需要尽可能取出 \(1\) ，在 \(a,b\) 里哪一个取均可，我们发现在字典树该位置以下，一定可以存在一种方案，使得后边的位可以全部得到 \(1\)（由 \(a\) 或 \(b\) 贡献），原因如下：我们想象一个特殊的结构：

\[ \begin{aligned} 10000000 \\ 01111111 \end{aligned} \]

上面这两个数在二进制字典树中正好构成了一个类似“菱形”的结构，且这两个边界刚好相邻。我们发现，在这个菱形内部的所有节点都是可选的，就已经可以组合出每一位的 \(1\) 了，由于给定的 \(l, r\) 的范围一般要更大，可以理解为菱形的左右两边多了一些部分，对刚才的的性质不产生影响，所以把后边全部取 \(1\) 是可行的。

代码

// https://acm.hdu.edu.cn/showproblem.php?pid=5969
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
 
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
    for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
 
template <typename _Tp>
void write(_Tp a) {
    if(a < 0) putchar('-'), a = -a;
    if(a > 9) write(a / 10); putchar(a % 10 + '0');
}

template <typename _Tp>
void write2(_Tp a) {
    for(int i = 0; i < 64; i++) {
        ll o = a & (1ll << (63 - i));
        write(o ? 1 : 0);
    }
}

int main() {
    // freopen("0727_1.in", "r", stdin);
    int T;
    read(T);
    while(T--) {
        ll a, b;
        read(a), read(b);
        // write2(a), putchar('\n');
        // write2(b), putchar('\n');
        ll ans = 0;
        bool f = 1;
        for(int i = 62; i >= 0; i--) {
            ll t = 1ll << i;
            ll op1 = a & t;
            ll op2 = b & t;
            bool c1 = op1;
            bool c2 = op2;
            if(c1 == c2 && f) {
                ans += a & t;
                continue;
            }
            f = 0;
            ans += t;
        }
        write(ans), putchar('\n');
        // write2(ans), putchar('\n'), putchar('\n');
    }
    return 0;
}