【题目来源】
AcWing：143. 最大异或对 - AcWing题库
【题目描述】
在给定的\(N\)个整数 \(A_1,A_2,...,A_N\) 中选出两个进行 \(xor\) （异或）运算，得到的结果最大是多少？
【输入】
第一行输入一个整数\(N\)。
第二行输入\(N\)个整数\(A_1\sim A_N\)。
【输出】
输出一个整数表示答案
【输入样例】
3
1 2 3
【输出样例】
3
【解题思路】
【算法标签】
《AcWing 143 最大异或对》 #Trie# #字典树# #贪心#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100010, M = 3000000; // N: 数字个数上限, M: Trie节点数上限
int n; // 实际数字个数
int son[M][2], idx; // son: Trie树结构, idx: 当前可用节点编号
int a[N]; // 存储输入数字的数组// 向Trie树中插入一个数字（按二进制位从高到低）
void insert(int x)
{int p = 0; // 从根节点开始for (int i = 30; i >= 0; i--) // 处理31位（包括符号位）{int &s = son[p][x >> i & 1]; // 获取当前二进制位的子节点if (!s) s = ++idx; // 如果子节点不存在则创建p = s; // 移动到子节点}
}// 查询与x异或结果最大的值
int query(int x)
{int res = 0, p = 0; // res: 存储结果, p: 当前节点for (int i = 30; i >= 0; i--) {int s = x >> i & 1; // 获取x的第i位if (son[p][!s]) // 优先选择相反的位（使异或结果最大）{res += 1 << i; // 该位异或结果为1，贡献2^ip = son[p][!s]; // 移动到相反位的子节点}else // 没有相反的位则选择相同位{res += 0 << i; // 该位异或结果为0（可省略）p = son[p][s]; // 移动到相同位的子节点}}return res;
}int main()
{cin >> n; // 输入数字个数for (int i = 0; i < n; i++) {cin >> a[i]; // 输入数字insert(a[i]); // 插入Trie树}int res = 0; // 存储最大异或结果for (int i = 0; i < n; i++) res = max(res, query(a[i])); // 查询每个数字能得到的最大异或值cout << res; // 输出最终结果return 0;
}
【运行结果】
3
1 2 3
3