最大异或对。
【题目描述】
从给定的n个整数A1、a2中选择两个.对于异或运算，最大结果是什么？
输入格式
在第一行输入一个整数n。
在第二行输入n个整数a1 ~ an。
输出格式
输出一个整数来表示答案。
数据范围
1N105，
0Ai231
输入样例：
三
1 2 3
输出样例：
三
(1)使用Trie优化，所有数字从高位到低位存储在Trie树中。因为要计算最大异或对，所以对于一个数num，可以获得最大异或值的数在每一位都必须与num相反。
然后取num的每个数字和Trie树中的数字进行查询。如果可以找到对位数，继续查询，如果找不到，继续查询。
最大的数是二进制的32位，所以所有的数都会统一视为32位，避免了判断的麻烦，走到叶节点后才能视为一个数。
1 #包含iostream
2使用命名空间标准；
3 const int N=31 * 100009
4 int Trie[N][2]，idx
5个空心嵌件(整数)
6 {
7 int p=0；
8表示(int i=30I=0；我)
9 {
10 int u=(num I)1；
11 if(！特里[p][u])
12 Trie[p][u]=idx；
13 p=Trie[p][u]；
14 }
15 }
16
17整数查询(整数)
18 {
19 int p=0，RES=0；
20表示(int i=30I=0；我)
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个
29 {
30 RES=(RES 1)u；
31 p=Trie[p][u]；
32 }
33 }
34返回^水库；
35 }
36
37 int n，res
38 int main()
39 {
cin北纬40度；
41 while(n -)
42 {
43整数；
44 cin数字；
45插入(数量)；
46 res=max(res，query(num))；
47 }
48个国家；
49返回0；
50 }
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/37476.html