如何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，秒过。