题目描述
在给定的 N 个整数 A1,A2,…,AN 中选出两个进行异或运算,得到的结果最大是多少?
输入格式
第一行一个整数 N。
第二行 N 个整数 Ai。
输出格式
一个整数表示答案。
样例
输入
5
2 9 5 7 0
输出
14
1 #include <iostream>
2 using namespace std;
3 int n;
4 const int N = 1e5 + 5;
5 int a[N];
6 int son[N * 35][3], cnt[N * 35];
7 int idx;
8
9 void insert(int x) {
10 int p = 0;
11
12 for (int i = 30; i >= 0; i--) {
13 int u = (x >> i) & 1;
14
15 if (!son[p][u])
16 son[p][u] = ++idx;
17
18 p = son[p][u];
19 }
20
21 cnt[p] = x;
22 }
23
24 int query(int x) {
25 int p = 0;
26 int ans = 0;
27
28 for (int i = 30; i >= 0; i--) {
29 int u = (x >> i) & 1;
30
31 if (son[p][u ^ 1]) {
32 ans += 1 << i;
33 p = son[p][u ^ 1];
34 } else
35 p = son[p][u];
36 }
37
38 return ans;
39 }
40
41 int main() {
42 scanf("%d", &n);
43 int res = 0;
44
45 for (int i = 1; i <= n; i++)
46 scanf("%d", &a[i]), insert(a[i]);
47
48 for (int i = 1; i <= n; i++) {
49 int t = query(a[i]);
50
51 if (t > res)
52 res = t;
53 }
54
55 cout << res << '\n';
56 return 0;
57 }