如何Acwing143题，使其成为最大异或对的？

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; }