$\color{green}{<–画图不易,点下这里赞一下吧}$
Trie 树详解点这里
思路:
用Trie(字典树)。
-
建树时,根据输入数字的对应的二进制串构造一个 Trie 树。
-
Trie 树的每个结点两个分支,分支指向的两个son结点分别表示当前位的数值为0或1
-
记录每次输入的数字转化成的二进制串,当前位为1,就走到数值为1的结点,否则走到0结点
-
这样每个数字对应的Trie中的路径就是唯一的。
因为要求异或对的值最大,可以用贪心的思想。
- 在第一个数字固定的情况下,尽可能地让第二个数的每一位都与第一个数的对应位相反,这样最终确定的第二个数与第一个数的异或值就最大,所以在查询时,遍历第一个串o(n),根据固定的第一个二进制串,每次尽可能走到与当前位的值相反的结点,这样的路径对应的就是与第一个二进制串异或值最大的二进制串,便利了这个数的位数次o(logn),所以总的时间复杂度o(n*logn);
本题ac代码:参考yxc
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
//保存 Trie 树
int son[N * 31][2];
int n, idx;
void insert(int x)
{
int p = 0;//初始化指向根节点
//从最高位开始,依次取出每一位
for (int i = 31; i >= 0; i--)
{ // 取出当前位
int u = x >> i & 1;
//如果树中不能走到当前数字
//为当前数字创建新的节点,保存该数字
if (!son[p][u])
// 新节点编号为 idx + 1
son[p][u] = ++idx;
p = son[p][u];
}
}
int query(int x)
{
//指向根节点
int p = 0;
// 保存与 x 异或结果最大的那个数
int ret = 0;
//从最高位开始,依次取出 x 的每一位
for (int i = 31; i >= 0; i--)
{
// 取出 x 的当前位
int u = x >> i & 1;
//如果树中能走到 !u,就走到!u
if (son[p][!u]){
//走到!u
p = son[p][!u];
//更新 x 异或的对象
ret = ret * 2 + !u;
}
//没有!u,就只能走到u了
else{
p = son[p][u];
//更新 x 异或的对象
ret = ret * 2 + u;
}
}
//计算异或结果
ret = ret ^ x;
return ret;
}
int main()
{
cin >> n;
int maxXorNum = 0;
int x;
for (int i = 0; i < n; i++)
{
cin >> x;
insert(x);
maxXorNum = max(maxXorNum, query(x));
}
cout << maxXorNum << endl;
return 0;
}
如果x远小于2的31次方为什么可以从30开始,不会出错吗
请问query里i为什么从31开始
从30开始也可以,笔误写成了31
设定范围是31,但最高位是符号位,所以都可以