形式化题目

给定 $N$ 个整数 $A_1, A_2, \dots, A_N$，每个数都不超过 31 位二进制（$0 \leqslant A_i < 2^{31}$，最高位是第 30 位）。求

即在下标不同的一对数中，找出按位异或值最大的那一对，只输出这个最大值。样例给出 $A = [1, 2, 3]$，三对的异或值如下：

最大的一个来自 $1 \oplus 2 = 3$，所以样例输出 3。观察第一条与第三条：$2$ 与 $3$ 只差最低位，反而异或最小；想让异或大，要让两个数在尽量高的位上取相反值。

正解

思路

一句话本质：把所有数按二进制从高位到低位插进一棵 01-Trie，再让每个数沿着树逐位贪心地走「相反位」；走不动才退回同位。走 31 步就得到以这个数为端点时能取到的最大异或值，全部取最大即答案。

先看朴素做法：枚举所有下标对算异或。数对总数是 $\binom{N}{2}$，$N = 10^5$ 时约 $5 \times 10^9$ 对，无论用什么语言都超时。瓶颈不在异或运算本身（它是 $O(1)$ 的），而在于枚举了所有数对——对每个 $A_i$ 都重新扫描了几乎所有其它的数。

要绕开它，就得让「找一个数的最佳搭档」不依赖其它数，能用 $A_i$ 自己的二进制位直接查出来。

关键观察：高位优先。 异或的每一位互不干扰：$A \oplus B$ 的第 $k$ 位只由 $A, B$ 的第 $k$ 位决定。而二进制是带权的，先比第 30 位、再比第 29 位。设已经确定了答案的高位前缀 $P$，当前要定第 $k$ 位：

• 若能凑出第 $k$ 位为 $1$，答案至少是 $P + 2^k$；
• 若第 $k$ 位只能为 $0$，答案至多是 $P + 2^k - 1$（低位全是 1 也补不回来）。

所以每一步只要判断「能不能凑出 1」，能就一定要凑，不需要回溯、不需要比较全局方案。这种“每一位做一次局部最优决策”的结构正适合用 Trie 承载：

• 把每个 $A_i$ 写成 31 位的 0/1 串，从第 30 位到第 0 位插入一棵二叉树（01-Trie），每位决定往 0 儿子还是 1 儿子走。一个数对应根到叶的一条长度 31 的路径，二进制前缀相同的数共享同一条路径。
• 查询 $A_i$ 时从根出发，走到第 $k$ 位就想：「有没有哪个数和 $A_i$ 的高位前缀完全相反？」这个问题的答案就是「$A_i$ 当前所在结点，走相反位的那条边存不存在」——一次数组访问。

下图是样例三个数 $1 = 001$、$2 = 010$、$3 = 011$ 取低 3 位建出的 01-Trie（高位全是 0，结构完全一样），结点标签是路径上的 0/1 前缀：

graph TD
    root(("root"))
    root -->|0| n0["0（前缀，含 1,2,3）"]
    n0 -->|0| n00["00（前缀，含 1）"]
    n0 -->|1| n01["01（前缀，含 2,3）"]
    n00 -->|1| n001["001（数 001）"]
    n01 -->|0| n010["010（数 010）"]
    n01 -->|1| n011["011（数 011）"]

读图要点：$2$ 和 $3$ 在前两位完全相同，所以共享 root → 0 → 01 这条路径，只在最后一位分叉——这正是「前缀相同则共享结点」的含义，也是 Trie 能把 $O(N^2)$ 对数压成 $O(31N)$ 个结点的原因。查询 $2 = 010$ 时，贪心路线是：

第 1 步之所以走不动，是因为样例里所有数都小于 $2^2$，第 2 位统一为 0，无论如何也凑不出 1——这时只能接受这一位是 0；之后两位都成功取反，异或值前缀累积到 011 即 $3$，最后停在叶子 001，也就是数 $1$。所以 $2$ 的最佳搭档是 $1$，答案为 $2 \oplus 1 = 3$，与样例一致。

把 $1, 2, 3$ 都查一遍：$1$ 得到 $3$，$2$ 得到 $3$，$3$ 得到 $2$，取最大值仍是 $3$。

两个实现细节：

• 查询时会不会选中自己？$A_i$ 与自身异或为 $0$，对应「所有位都走同位」的那条路径，结果最小；只要还存在任何能在某一位取反的数，贪心就会优先走上相反位的分支。$N = 1$ 时答案自然是 $0$，也是对的。
• 另一种等价做法是按位确定答案：从高位往低位试着把答案的这一位置 1，把所有数截断到当前前缀丢进哈希集合，检查是否存在 $p \oplus cand$ 也在集合里。它同样只要 31 轮，但每轮都要重建集合，常数比 Trie 大。

对应到代码：build_trie() 做上面第一步（插树并返回扁平的 array('i') 儿子表），best_xor() 做第二步（每个数贪心一遍并取最大），solve() 只负责读入和输出。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:53
# update_at: 2026-10-01 11:56

import sys
from array import array

BITS = 31        # A_i < 2^31，所以要看二进制第 30 位到第 0 位
ROOT = 0         # 根结点固定编号 0
NO_CHILD = 0     # 儿子槽里的哨兵：0 表示这条边还没建出来（结点编号从 1 开始）


def build_trie(values: list[int]) -> array:
    """把所有数按二进制从高位到低位插入 Trie，返回扁平化的儿子数组。

    结点 p 的两位儿子放在 children[2p]（走 0）和 children[2p+1]（走 1）。
    每个数最多新建 BITS 个结点，所以 2*(BITS*n+1) 个 int 槽位一定够用；
    一次分配整块数组，比给三百万个结点逐个建 dict 省下大量内存。
    """
    children = array('i', [0]) * (2 * (BITS * len(values) + 1))
    top = 1                          # 下一个可用的结点编号
    for value in values:
        node = ROOT
        for shift in range(BITS - 1, -1, -1):
            slot = (node << 1) | (value >> shift & 1)   # 当前结点走这一位对应的槽
            nxt = children[slot]
            if nxt == NO_CHILD:                         # 这条边还没有，现建一个儿子
                nxt = top
                top += 1
                children[slot] = nxt
            node = nxt
    return children


def best_xor(children: array, values: list[int]) -> int:
    """每个数都在 Trie 里贪心走“相反位”，取所有数能配出的最大异或值。"""
    answer = 0
    for value in values:
        node = ROOT
        current = 0
        for shift in range(BITS - 1, -1, -1):
            bit = value >> shift & 1
            base = node << 1
            opposite = children[base | (bit ^ 1)]       # 想要异或出 1，就先找相反位那条边
            if opposite != NO_CHILD:
                current |= 1 << shift                   # 相反位存在，这一位异或结果必是 1
                node = opposite
            else:
                node = children[base | bit]             # 只能走同位，这一位异或结果是 0
        if current > answer:
            answer = current
    return answer


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    values = [next(data) for _ in range(n)]
    children = build_trie(values)
    print(best_xor(children, values))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:50
 * update_at: 2026-10-06 15:50
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
const int BITS = 31;                  // A_i < 2^31，所以看二进制第 30 位到第 0 位
const int MAX_NODE = BITS * MAXN + 5; // 每个数最多新建 BITS 个结点

// 01-Trie 的儿子表：children[2*p] 是结点 p 走 0 的儿子，children[2*p+1] 是走 1 的儿子。
// 0 表示这条边还没建出来（结点编号从 1 开始，根固定为 0），所以数组要开两倍结点数。
int children[2 * MAX_NODE];
int node_count = 1; // 下一个可用的结点编号

ll n;
ll a[MAXN]; // 输入序列

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
}

// 把一个数按二进制从高位到低位插入 01-Trie。
void insert_value(ll value) {
    int node = 0; // 从根出发
    for (int bit = BITS - 1; bit >= 0; bit--) {
        int b = value >> bit & 1;
        int slot = (node << 1) | b;
        if (children[slot] == 0) { // 这条边还没有，现场新建一个儿子
            children[slot] = node_count;
            node_count++;
        }
        node = children[slot];
    }
}

// 在 Trie 里为 value 贪心找异或最大的搭档，返回这个最大的异或值。
// 高位权重大于所有低位之和，所以每一位只要能走相反位就一定走。
ll best_xor(ll value) {
    int node = 0;
    ll result = 0;
    for (int bit = BITS - 1; bit >= 0; bit--) {
        int b = value >> bit & 1;
        int base = node << 1;
        int opposite = children[base | (b ^ 1)]; // 想要这一位异或出 1，先看相反位有没有儿子
        if (opposite != 0) {
            result |= 1LL << bit; // 相反位存在，这一位一定是 1
            node = opposite;
        } else {
            node = children[base | b]; // 只能走同位，这一位异或结果是 0
        }
    }
    return result;
}

void solve() {
    for (ll i = 1; i <= n; i++) {
        insert_value(a[i]);
    }

    ll answer = 0;
    for (ll i = 1; i <= n; i++) {
        ll current = best_xor(a[i]);
        if (current > answer) {
            answer = current;
        }
    }
    cout << answer << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

记 $B = 31$ 为二进制位数（常数）。代码里 $B$ 就是模块常量 BITS，儿子槽 children[2p+b] 表示结点 $p$ 走位 $b$ 的儿子，NO_CHILD = 0 是“这条边还没建出来”的哨兵。

• 时间复杂度：建树每个数走 $B$ 层、查询每个数也走 $B$ 层，总时间 $O(BN) = O(N)$。朴素枚举是 $O(N^2)$，$N = 10^5$ 时两者相差约 $10^4$ 倍。
• 空间复杂度：结点数最多 $BN + 1$，每个结点两个儿子槽，$O(BN) = O(N)$。Python 里用 array('i') 把儿子槽存成连续内存，$N = 10^5$ 时表本身约 24.8 MB，加上输入与中间列表，实测峰值 48.7 MB，低于 128 MB 限制。

Python 侧的风险只在常数，不在复杂度：最大数据实测 0.572s，相对 OJ 的 1000ms 限制有约 1.7 倍余量（仓库本地校验还会再放宽到 20s）。若换成「每个结点一个 dict」的写法，时间相近但内存会涨到 200 MB 以上，这是实现取舍而非算法差异。

总结

• 模型转换：把「枚举所有数对」换成「为每个数在二进制前缀树上查一个最佳搭档」。数对数量 $O(N^2)$，而 Trie 的结点数是 $O(BN)$，量级彻底脱钩。
• 贪心依据：高位权重大于所有低位之和，所以「第 $k$ 位能凑出 1 就必须凑」；这让每一步都无需回溯，31 步直接定出答案。
• 01-Trie 的两个要点：每个数是一条长度 $B$ 的路径，前缀相同即共享结点；「找相反位」就是访问当前结点的另一条边。
• 本题是 01-Trie 的模板题，可持久化 01-Trie（区间异或最值）、最大异或路径（树上异或和 + 01-Trie）都建立在这套骨架上。

图示解析

把从输入到答案的主线压缩成一张图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15A = [1, 2, 3]
        │
        ▼
  按 31 位二进制插入 01-Trie
        │          每个数一条长度 31 的路径
        │          相同前缀共享结点，共 O(31N) 个结点
        ▼
  对每个 A_i 从根逐位贪心（第 30 位 → 第 0 位）
        │
        ├── 想走的相反位儿子存在 → 异或值这一位 = 1，走相反位
        │
        └── 不存在             → 异或值这一位 = 0，只能走同位
        │
        ▼
  每个 A_i 得到一个候选值 ──取 max──▶ 答案

图的观察重点：整条流程只有「建树」和「逐位贪心」两个动作，没有分治、也没有回溯，每个数只与自己的一条贪心路线有关；每个数独立查询一次，所以总代价就是 $N$ 次 31 步的走树。图中「相反位存在 → 置 1」是唯一的判断，它的正确性由高位优先性质保证。