题目链接

板子题，参考题解直接看acwing的就行了；

01字典树的学习可以看这里：链接

01字典树：在一个集合中找和x异或值最大/最小的数（经典用法）

主要思想：
把集合中的每个数看成二进制01字符串，然后建字典树；
对于一个x，从高到低看每一位，假设当前我们要查询的是异或后最大值，对于当前位p：
如果x§=1，则我们优先选字典树中第p位是0的；
如果x§=0，则我们优先选字典树中第p位是1的；
也就是说优先选和x§相反的（如果字典树存在的话）。
如果查询最小值则优先选相同的。

注意字典树的初始化：insert里面也要初始化！

这道题会了可以看这个题：题目链接
题解

代码

#include<iostream>
#include<string>
using namespace std;
typedef long long ll;

const int maxn = 100010;

int n;
int a[maxn];
int tree[maxn * 31][2];
int idx;

void insert(int x)
{
    int p=0;
    for(int i=30;i>=0;i--)
    {
        int u = x >> i & 1;
        if(!tree[p][u]) tree[p][u] = ++idx;
        p = tree[p][u];
    }
}

int query(int x)
{
    int p=0;
    int ans=0;
    for(int i=30;i>=0;i--)
    {
        int u = x >> i & 1;
        if(tree[p][!u]) 
        {
            p = tree[p][!u];
            ans = ans * 2 + !u;
        }
        else
        {
            p = tree[p][u];
            ans = ans * 2 + u;
        }
    }
    return ans;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    int ans=0;
    for(int i=0;i<n;i++)
    {
        insert(a[i]);

        int t = query(a[i]);
        ans = max(ans,a[i] ^ t);
    }

    cout<<ans<<endl;

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