11. 388535

本文主要是介绍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 <bits/stdc++.h>
using namespace std;
int l, r;
set<int> 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<int> 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);elseans *= (*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$ 即可。

这篇关于11. 388535的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---