题目描述
在给定的 $N$ 个整数 $A_1,A_2……A_N$ 中选出两个进行 $xor$(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数 $N$。
第二行输入 $N$ 个整数 $A_1$~$A_N$。
输出格式
输出一个整数表示答案。
数据范围
$1 \le N \le 10^5$,
$0 \le A_i < 2^{31}$
输入样例:
3
1 2 3
输出样例:
3
Trie树
时间复杂度 $O(n)$
我们考虑所有的二元组$(i,j)$且$i<j$,那么本题的目标就是在其中找到$A_i$ $xor$ $A_j$的最大值。也就是说,对于每个$i$ $(1 \le i \le N)$,我们希望找到一个$j$ $(1 \le j < i)$,使$A_i$ $xor$ $A_j$最大,并求出这个最大值。
我们可以把每个整数看作长度为$31$的二进制$01$串(数值较小时在前边补$0$),并且把$A_1~A_{i-1}$对应的$31$位二进制串插入一棵$Trie$树(其中最低二进制位为叶子节点)。接下来,对于$A_i$对应的$31$位二进制串,我们在$Trie$中进行一次与检索类似的过程,每一步都尝试沿着“与$A_i$的当前位相反的字符指针”向下访问。若“与$A_i$的当前位相反的字符指针”指向空节点,则只好访问与$A_i$当前位相同的字符指针。根据$xor$ 运算“相同得$0$,不同得$1$”的性质,该方法即可找出与$A_i$:做$xor$运算结果最大的$A_j$。
综上所述,我们可以循环$i$ =$1$ ~$N$,对于每个$i$,$Trie$树中应该存储了$A_1$~$A_{i-1}$对应的$31$位二进制串(实际上每次$i$增长前,把$A_i$插入$Trie$ 即可)。根据我们刚才提到的“尽量走相反的字符指针”的检索策略,就可以找到所求的$A_j$,更新答案。
参考教材 《算法竞赛进阶指南》
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 3100010;
int n;
int a[N], son[M][2], idx;
//在这个问题中,我们需要存储一个二进制的字典树,每个节点有两个子节点,分别对应二进制的0和1。
void insert(int x)//将一个数 x 插入到字典树中。它从 x 的最高位开始,依次检查每一位,如果这一位是1,就向右子树走,如果这一位是0,就向左子树走。如果对应的子树不存在,就创建一个新的节点。
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int &s = son[p][x >> i & 1];
if (!s) s = ++ idx; // 如果s不存在,则创建一个新节点
p = s;//p指向这个新节点,也就是向左或向右走
}
}
//在 insert 函数中,我们通过 son[p][x >> i & 1] 来找到或创建 x 的第 i 位对应的子节点。
int search(int x)//在字典树中找到一个数,使得这个数与 x 的异或结果最大。它也是从 x 的最高位开始,依次检查每一位,如果这一位是1,就尽量向左子树走,如果这一位是0,就尽量向右子树走,因为这样可以使得异或结果最大。如果对应的子树不存在,就只能向另一边走。
{
int p = 0, res = 0;
for (int i = 30; i >= 0; i -- )
{
int s = x >> i & 1;
if (son[p][!s])
{
res += 1 << i;//计算 x 与字典树中某个数的异或结果,因为我们总是尽量选择与 x 的当前位不同的子节点,所以如果 son[p][!s] 存在,就说明我们找到了一个与 x 的当前位不同的数
p = son[p][!s];
}
else p = son[p][s];//实在无法移动到左右子节点则向另一个子节点移动
}
return res;
}
//在 search 函数中,我们通过 son[p][!s] 和 son[p][s] 来找到与 x 的第 i 位不同或相同的子节点,以此来使得异或结果最大。
//p 是一个在字典树中移动的指针,它帮助我们在 insert 和 search 函数中遍历 x 的每一位,并在字典树中相应地向左或向右移动。
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
insert(a[i]);
}
int res = 0;
for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));
printf("%d\n", res);
return 0;
}