【题目描述】

在给定的 N 个整数 A₁，A₂……A_N 中选出两个进行 xor（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A₁～A_N。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤10⁵,
0≤Ai<2³¹

输入样例：

3
1 2 3

输出样例：

3

 

①利用Trie优化，将所有数字按位从高到低位存入Trie树中，由于要计算最大异或对，那么对于一个数字num，能够与其得出最大异或值得数字一定是每一位都与num相反的。

那么就取num的每一位与Trie树中的数字进行查询，如果能够找到相反的位，就继续往下，找不到也继续往下查询。

②最大的数字是二进制32位的，那么就将所有数字都统一视为32位的，免去判断的麻烦，只有走完走到了叶子结点才算是一个数字。

 

 1 #include <iostream>
 2 using namespace std;
 3 const int N = 31 * 100009;
 4 int Trie[N][2],idx;
 5 void insert(int num)
 6 {
 7     int p = 0;
 8     for(int i = 30;i >= 0;--i)
 9     {
10         int u = (num >> i) & 1;
11         if(!Trie[p][u])
12             Trie[p][u] = ++idx;
13         p = Trie[p][u];
14     }
15 }
16 
17 int query(int num)
18 {
19     int p = 0,res = 0;
20     for(int i = 30;i >= 0;--i)
21     {
22         int u = num >> i & 1;
23         if(Trie[p][!u])
24         {
25             res = (res << 1) + !u;  //  注意：加号运算符优先级高于<<
26             p = Trie[p][!u];
27         }
28         else
29         {
30             res = (res << 1) + u;
31             p = Trie[p][u];
32         }
33     }
34     return num ^ res;
35 }
36 
37 int n,res;
38 int main()
39 {
40     cin >> n;
41     while(n--)
42     {
43         int num;
44         cin >> num;
45         insert(num);
46         res = max(res,query(num));
47     }
48     cout << res << endl;
49     return 0;
50 }