> ✅ **OJ 验证通过**：Accepted（runid 4115393，2026-08-14 提交于校内 OJ Contest3056） ## 题目大意有 $n$ 箱可乐，第 $i$ 箱上标着正整数 $a_i$。选择一个非负整数"聪明值" $x$ 后，若 $(a_i \oplus x) \le k$ 就能喝到第 $i$ 箱可乐。求通过选择合适的 $x$ 最多能喝到的可乐箱数。$1 \le n, k, a_i \le 10^6$。 ## 思路分析问题等价于：**找一个 $x$，使满足 $a_i \oplus x \le k$ 的 $i$ 尽量多**。对每个 $a_i$，能使它"达标"的 $x$ 构成集合： $$ S_i = \{x \mid a_i \oplus x \le k\} = \{a_i \oplus y \mid 0 \le y \le k\} $$ 我们要找被最多 $S_i$ 覆盖的 $x$。 **关键转化**：$[0, k]$ 按二进制可拆成 $O(\log V)$ 个"高位固定、低位任意"的块。枚举到第 $bit$ 位且 $k$ 该位为 $1$ 时，$y$ 在此位取 $0$、高位与 $k$ 相同、低位任意的块均满足 $y < k$。由于 $x = a_i \oplus y$，异或只改变高位、低位保持任意，该块映射到 $x$ 空间后仍是**一段连续区间**： - 高位：$x_{high} = (a_i \gg (bit+1)) \oplus (k \gg (bit+1))$； - 第 $bit$ 位固定为 $a_i$ 的第 $bit$ 位； - 低于 $bit$ 的位任意。最后再单独计入 $y = k$（即 $x = a_i \oplus k$）这一个点。对每个 $a_i$ 拆出 $O(20)$ 个 $x$ 区间后，用**差分数组**做区间加，前缀和取最大值即为答案。 > 由于 $a_i, k \le 10^6 < 2^{20}$，$x$ 的取值空间取 $[0, 2^{20})$ 即可。 ## 复杂度分析每个 $a_i$ 拆 $O(20)$ 个区间，总复杂度 $O(n \times 20 + 2^{20})$，约 $2 \times 10^6$ 量级。 ## 参考代码 ```cpp #include using namespace std; const int B = 20; const int SIZE = 1 << B; int diff[SIZE + 1]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { int b; cin >> b; for (int bit = B - 1; bit >= 0; bit--) { if ((k >> bit) & 1) { int prefix = k >> (bit + 1); // y 的高位与 k 相同 int x_high = (b >> (bit + 1)) ^ prefix; int x_bit = (b >> bit) & 1; int xl = (x_high << (bit + 1)) | (x_bit << bit); int xr = xl + (1 << bit) - 1; diff[xl]++; diff[xr + 1]--; } } int x = b ^ k; // y == k 的精确点 diff[x]++; diff[x + 1]--; } int cur = 0, ans = 0; for (int i = 0; i < SIZE; i++) { cur += diff[i]; ans = max(ans, cur); } cout << ans << endl; return 0; } ```