11. 388535

题目链接：388535 (Hard Version)

有一个数组，原先含有 \([l,r]\) 内的整数各一个，现在将它们全都异或上一个 \(x\)。给出变化后的数组以及 \(l,r\)，求 \(x\) 的值。

这题有一个神奇的做法，但是需要挖掘一些性质。

注意到 \((a\oplus x)\oplus(b\oplus x)=a\oplus b\)。根据这个性质，对于 \([l,r]\) 中的一对相邻整数 \((2k,2k+1)\)，它们原来的异或值和变化后的异或值都为 \(1\)，所以我们能够对它们进行匹配。匹配完会出现四种情况：

• \(l,r\) 均为奇数，\(l\oplus x\) 无法匹配，与 \(l\) 异或就得到 \(x\)
• \(l\) 为奇数，\(r\) 为偶数，\(l\oplus x,r\oplus x\) 均无法匹配，把两种可能都试一试，暴力检测即可
• \(l\) 为偶数，\(r\) 为奇数，全都可以匹配，说明 \(x\) 的最后一位可以随便取，钦定这一位为 \(0\)，将所有数右移一位，重复匹配过程
• \(l,r\) 均为偶数，\(r\oplus x\) 无法匹配，与 \(r\) 异或就得到 \(x\)

这里解释一下为什么第三种情况下最后一位可以随便取：原来范围内的一对整数 \((2k,2k+1)\) 的二进制表示形如 A0 与 A1，当 \(x\) 的二进制形如 B0，即最后一位取 \(0\) 时，异或出来的二进制表示形如 C0 与 C1；当 \(x\) 的二进制形如 B1，即最后一位取 \(1\) 时，异或出来的二进制表示形如 C1 与 C0。容易发现，这两个结果唯一的差别只是顺序不同，所以是等价的。

#include 
using namespace std;
int l, r;
set s;
bool check(int x) {
    for (auto it : s) {
        if ((it ^ x) > r || (it ^ x) < l)
            return false;
    }
    return true;
}
void solve() {
    cin >> l >> r;
    s.clear();
    for (int i = l, x; i <= r; i++) {
        cin >> x;
        s.insert(x);
    }
    int ans = 1;
    while (!s.empty()) {
        set t = s;
        for (auto it : s)
            t.erase(it ^ 1);
        if ((l & 1) && (r & 1)) {
            ans *= (*t.begin() ^ l);
            break;
        }
        if ((l & 1) && !(r & 1)) {
            if (check(*t.begin() ^ l))
                ans *= (*t.begin() ^ l);
            else
                ans *= (*t.begin() ^ r);
            break;
        }
        if (!(l & 1) && !(r & 1)) {
            ans *= (*t.begin() ^ r);
            break;
        }
        t.clear();
        for (auto it : s)
            t.insert(it >> 1);
        s = t;
        l >>= 1, r >>= 1, ans <<= 1;
    }
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

这道题也有 01trie 的做法，同样十分巧妙。将每个数异或上 \(l\) 就是 \(x\) 的所有可能值，对于 \(x\) 的每个可能值都去 trie 上计算最大异或值是否等于 \(r\) 即可。