🉑乐题解

• 🉑乐题解
  • 题目分析
  • 解题思路
    • 暴力做法
    • 优化思路
      • 查询

参考题解：题解 P6824 【「EZEC-4」可乐】

题目分析

• 有 n 瓶可乐，每瓶可乐有一个口味值 a[i]（非负整数）。
• 你可以选择一个整数 x（非负整数），对于每瓶可乐：
  • 如果 (a[i] XOR x) <= k，那么你能喝到这瓶可乐。
• 目标：选择合适的 x，使得能喝到的可乐瓶数最多，输出这个最大值。

解题思路

暴力做法

最直接的想法是枚举所有可能的 x，然后对每个 x 统计有多少瓶可乐满足 (a[i] XOR x) <= k。

但是 x 的范围是多少呢？ 因为 2^a[i] < 2^21，所以 a[i] 最大可能接近 2^21，但 x 的值其实可以限制在 [0, 2^21)，因为更大的 x 只是高位不同，对比较结果影响不大，而且 k 最大也是 2^21 级别，所以枚举到 2^21 就足够了。

优化思路

我们知道，从暴力法求解主要需要两个步骤：

• 枚举可能的x
• 对于给定的 x，计算有多少 a[i] 满足 (a[i] XOR x) <= k

我们打算使用 Trie 树（二进制 Trie，这样就只用跑）来存储所有 a[i]，并在 Trie 上沿着 x XOR k 的路径走，同时统计满足条件的节点数量。

查询

在Trie上，我们从高位到低位枚举，

记：k的第i位为1，x的第i位为c，假设前面判断的每一位都相等：

1. 如果k的这一位是1，那么a[i] XOR x在这一位为0的所有情况都满足条件。

   因为高位相等，当前位0 < 1，所以整个子树都满足(a[i] XOR x) < k

           if (t == 1) {  
               // 如果k的这一位是1，那么a[i] XOR x在这一位为0的所有情况都满足条件
               // 因为高位相等，当前位0 < 1，所以整个子树都满足(a[i] XOR x) < k
               ret += sz[trie[p][!(c ^ t)]];
           }
   

2. k的当前位为0：

   此时：(a[i] XOR x) 的当前位必须是 0

   • 如果是 1：那么 (a[i] XOR x) > k，不满足条件
   • 如果是 0：继续判断低位

   代码实现：只能沿着c ^ t方向继续走。

           if (!trie[p][c ^ t]) {
               flag = 1;  // 标记提前结束
               break;
           }
           p = trie[p][c ^ t];  // 移动到下一个节点
   

注意：如果没有提前结束（即最后一个节点亦可），记得加上最后相等的情况。

if (!flag) ret += sz[p];

统计 (a[i] XOR x) == k 的情况。