算法（最大异或对）

143. 最大异或对​​​​
在给定的 N𝑁 个整数 A1，A2……AN𝐴1，𝐴2……𝐴𝑁 中选出两个举行 xor𝑥𝑜𝑟（异或）运算，得到的效果最大是多少？
输入格式

第一行输入一个整数 N𝑁。
第二行输入 N𝑁 个整数 A1𝐴1～AN𝐴𝑁。
输特别式

输出一个整数表现答案。
数据范围

1≤N≤1051≤𝑁≤105,

思绪：
暴力的做法是对于第i个输入的数，分别于前i-1个数异或，得到一个最大值，然后用当前的最大值和ans比力巨细，更大的给ans。当i从0到n走一遍以后完成求解，所用时间是o（N*N）。
优化的地方是内层的循环，即每次第i个数不消和前i-1个数都比力一遍，而是可以利用tire树找出此中能得到当前最大异或对的解，详细原理是对于已经存入tire树的前i-1个数，用到大到小遍历第i个数的二进制每一位，看tire数对于当前位，有无相反的谁人数（1就是找0，0就是找1），若存在，则最大的异或肯定是在这个分支上（由于高位大的肯定大），若不存在，则只能选择类似的数，然后继承看下一位，重复上述过程。
留意idx是先加一，再去赋值，要把第0位空出来。开始用++idx堕落了，由于若开头位数是0放下标位0的位置，相称于没动。

2. #include<iostream>
3. #include<cstring>
4. using namespace std;
6. const int N=3000100;
7. int e[N][2];
8. int idx;
9. int n;
11. void insert(int x)
12. {   
13.     int p=0;
14.     for(int i=30;i>=0;i--)
15.     {
16.         int t=x>>i&1;
17.         if(!e[p][t])e[p][t]=++idx;
18.         p=e[p][t];
19.     }
20. }
22. int serch(int x)
23. {   
24.     int ans=0;
25.     int p=0;
26.     for(int i=30;i>=0;i--)
27.     {
28.         int t=x>>i&1;
29.         if(e[p][!t])
30.         {
31.             ans=ans*2+1;
32.             p=e[p][!t];
33.         }
34.         else
35.         {
36.             p=e[p][t];
37.             ans*=2;
38.         }
39.     }
40.     return ans;
41. }
43. int main()
44. {   
45.     scanf("%d",&n);
46.     int ans=0;
47.     while(n--)
48.     {
49.         int a;
50.         scanf("%d",&a);
51.         insert(a);
52.         ans=max(ans,serch(a));
53.         
54.     }
55.     printf("%d\n",ans);
56.     return 0;
57.    
58. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金