30.Acwing基础课第143题-简单-最大异或对
题目描述
在给定的 N 个整数 \(A_1，A_2……A_N\)中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数\(A_1，A_2……A_N\)。
输出格式
输出一个整数表示答案。
数据范围
\(1≤N≤10^5\),
\(0≤A_i<2^{31}\)
输入样例：
3
1 2 3
输出样例：
3
最大异或对（字典树应用）
1. 题意
- 给定 n 个整数（n≤1e5，每个数≤2³¹-1），从其中选两个数进行异或运算，求最大值。
- 异或规则：二进制位相同为 0，不同为 1（俗称 “不进位加法”），例：5 (101) XOR 3 (011)=6 (110)。
2. 解法思路
（1）暴力解法（超时）
- 思路：两重循环枚举所有数对（i,j），计算 a [i]^a [j]，维护最大值。
- 时间复杂度：O (n²)（n=1e5 时为 1e10 次运算，远超 1 秒阈值 1e8），必然超时。
（2）优化解法：字典树（Trie）
- 核心思想：将 “找与 a [i] 异或最大的数” 转化为 “字典树的贪心查询”，把内层循环 O (n) 优化为 O (31)（31 位二进制）。
- 字典树作用：存储所有数的二进制形式（从高位到低位，共 31 位），支持高效查询 “与目标数异或最大的数”。
3. 核心知识点
（1）字典树的构建与查询规则
- 构建：每个数按二进制从高位（第 30 位）到低位插入字典树，0 走左子树，1 走右子树。
- 查询（贪心策略）：
- 对目标数 a [i]，从高位到低位遍历二进制位；
- 每一位优先选择与当前位不同的子树（异或结果为 1，最大化高位）；
- 若目标子树不存在，则选择同方向子树；
- 遍历完 31 位后，得到的数即为与 a [i] 异或最大的数。
（2）时间复杂度
- 构建字典树：O (n×31)，查询每个数：O (31)，总复杂度 O (n×31)≈3e6，秒过。
代码：
#include <iostream>
#include <algorithm>using namespace std;// 数组大小定义
const int N = 100010; // 输入数字的最大数量
const int M = 3100010; // 字典树节点总数：每个数31位，31*1e5=310万int n; // 数字个数
int a[N]; // 存储输入的所有数字
int son[M][2]; // 字典树：son[节点编号][0/1] = 子节点编号
int idx; // 节点编号分配器，0是根节点// 把数字 x 插入字典树（按二进制位从高位到低位插入）
void insert(int x)
{int p = 0; // 从根节点开始// 从第30位到第0位遍历（int是31位有效数字）for (int i = 30; i >= 0; i--){// 取出 x 的第 i 位二进制数（0 或 1）int u = x >> i & 1;// 如果当前节点没有这个子节点，就新建一个节点if (!son[p][u]) son[p][u] = ++idx;// 走到子节点p = son[p][u];}
}// 在字典树中查找与 x 异或结果最大的数，并返回最大异或值
int search(int x)
{int p = 0; // 从根节点开始int res = 0; // 记录最大异或结果// 从高位到低位贪心查找for (int i = 30; i >= 0; i--){// 取出 x 的第 i 位二进制int u = x >> i & 1;// 贪心策略：尽量走相反的位（异或=1）if (son[p][!u]){// 这一位可以异或出1，结果加上这一位的值res += 1 << i;// 走向相反的节点p = son[p][!u];}else{// 没有相反的位，只能走相同的节点（异或=0）p = son[p][u];}}return res;
}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;
}