题目描述
在给定的N个整数A1,A2……AN中选出两个进行xor(异或)运算,得到的结果最大是多少?
输入格式
第一行输入一个整数N。
第二行输入N个整数A1~AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai<231
输入样例:
3
1 2 3
输出样例:
3
使用 Tire 树,可以将复杂度从 O(nn) 优化到 O(nm) m指字符串长度,m < n
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int const N = 100005, MAX_CNT = 31 * N;
int const BRANCH_CNT = 2;
/*
tree 二维数组,建立查询的树状结构;
idx 标记树状结构各个点的编号;
*/
int node[MAX_CNT][BRANCH_CNT], idx;
// 为输入的一个数字建立 Tire 树;
void buildTree(int x) {
int p = 0;
// 逐位读入,高位者添至上层,后续遍历逐层加权;
for (int i = 31; i >= 0; i--) {
// 由每一位的值确定所属分支;
int brc = x >> i & 1;
// 对指定分支设置编号信息;
if (!node[p][brc]) node[p][brc] = ++idx;
// 更新父节点编号值,进入下一层树;
p = node[p][brc];
}
return;
}
// 基于传入的参数 漫游整个 Tire树 计算输出;
int searchTree(int x) {
int ret = 0;
int p = 0;
// 传入参数 逐位读取;
for (int i = 31; i >= 0; i--) {
int brc = x >> i & 1;
// 当前参数对应的结点为 node[p][brc],由根节点开始检索;
// 所在分支的对立分支 使得异或运算值为 1;
// 期望对立分支的存在;
if (node[p][!brc]) {
p = node[p][!brc];
ret = ret * 2 + 1; // 按二进制逻辑更新异或值;
}
else {
// 对立分支不存在,以当前分支向下查找计算;
p = node[p][brc];
ret *= 2;
}
}
// for 循环结束,已经加权计算树中 所有 异或为 1 的结点;
return ret;
}
int main() {
int n, a[N];
cin >> n;
idx = 0;
memset(node, 0, sizeof(node));
memset(a, 0, sizeof(a));
// 为输入的数组建立查询用的树;
for (int i = 1; i <= n; i++) {
scanf_s("%d", &a[i]);
buildTree(a[i]);
}
// 基于 Tire 树的检索,计算最大异或值,复杂度O(n * m);
int maxXorNum = 0;
for (int i = 1; i <= n; i++) {
maxXorNum = max(maxXorNum, searchTree(a[i]));
}
cout << maxXorNum << endl;
system("PAUSE");
return 0;
}