D. 邪恶博士的最低异或值 详细题解

题目核心理解

给定 $n$ 个整数 $a_1,a_2,\dots,a_n$，你需要选择一个整数 $X$，使得所有数与 $X$ 异或后的结果的最大值尽可能小。 输出这个最小化后的最大异或值。

数据范围：

• $1\le n\le 10^5$
• $0\le a_i\le 2^{30}-1$

---

核心思路

1. 关键性质

• 异或结果的大小由高位优先决定，因此从最高位（第 $29$ 位）到最低位逐位贪心。
• 对当前处理的第 $i$ 位，把数字分成两类：该位为 $0$ 的一组、该位为 $1$ 的一组。
• 如果某一组为空，说明可以通过选择 $X$ 的当前位，让所有数异或后该位都为 $0$，直接递归处理下一位。
• 如果两组都不为空，则无论 $X$ 该位取 $0$ 还是 $1$，最终最大异或值的这一位一定是 $1$，必须计入答案。

2. 计算规则

对两组数字分别递归求解低位的最优答案，取两种选择中结果更小的那个：

$$ans = 2^i + \min(\text{递归0组结果},\text{递归1组结果})$$

递归到无位可处理时，返回 $0$。

---

算法流程

1. 从最高位 $bit=29$ 开始，将当前数字按该位 $0/1$ 分组。
2. 如果某一组为空，递归处理另一组并直接返回结果。
3. 如果两组均非空，当前位贡献 $2^i$，递归求解两组的子问题。
4. 取两个子问题结果的最小值，与当前位贡献相加，作为本层答案返回。
5. 递归出口：$bit=-1$ 时返回 $0$。

---

公式与复杂度分析

递归公式：

$$ans= \begin{cases} dfs(bit-1, 非空组),&一组为空\\ 2^{bit}+\min(dfs(bit-1,0组),dfs(bit-1,1组)),&两组均非空 \end{cases} $$

复杂度

• 时间复杂度：$O(n\cdot 30)$，即 $O(n\log \max a_i)$
• 空间复杂度：$O(n)$（递归分组存储）

可在时限内轻松处理 $n=10^5$、值域到 $2^{30}$ 的数据。