[字典树] 树之呼吸-伍之型-最大异或和

E.树之呼吸-伍之型-最大异或和

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 29 (5 users)

Total Accepted: 4 (4 users)

Special Judge: No

Description

在给定的 n 个整数 A1,A2,...,An 中选出两个进行 xor（异或）运算，得到的结果最大是多少？

Input

输入第一行为一个正整数 case，表示测试数据组数；

对于每组测试数据，输入第一行为一个正整数 n，表示给定的整数个数；

接下来一行给出 n 个整数 A1,A2,...,An；

保证：

1 <= case <= 50，1 <= n <= 1e5，0 <= Ai < 2^31；

∑n <= 1e6。

Output

对于每组测试数据，输出一行一个整数，表示在给定整数中选出两个进行 xor 运算的最大值。

Sample Input

1 2 3 4 5

5 1 8 9 3 1

Sample Output

Author

陈鑫

题意:在给定的 n 个整数 A1,A2,...,An 中选出两个进行 xor（异或）运算求出最大结果
思路:若要让2个数的异或结果尽可能的大,则他们每一位数从高位开始要尽可能的不同(什么是高位低位?123中1是相对2和3的高位,3是相对1和2的高位),
若用每一个数与其他数去比较,则是O(n*n)的复杂度,1e6的n会TLE,所以我们可以对n个数建一颗字典树来求一个数i与这n个数异或的最大值,枚举n个数保存一个最大值作为答案.
使用二进制来建字典树时,要从数的高位开始向低位建.
接着枚举第1到第n的数,看哪个数求得的异或值最大,对每个数从这个数的高位往低位在字典树中匹配,
如果与当前位的数相反的结点存在则访问这个结点并且ans加上2的i-1次幂,否则就访问与当前位的数相同的结点,
最后保存一个最大的答案并输出

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int amn=1e5+5;
 5 int n,tr[32*amn][2],tot,bit[33],tp; ///每个数有32位,1e5个数,所以要开32*1e5的空间
 6 ll a[amn];
 7 void init(){
 8     memset(bit,0,sizeof bit);
 9     memset(tr,0,sizeof tr);
10     tot=0;
11 }
12 void tobit(ll x){     ///将x转换为2进制数组
13     tp=0;
14     while(x){
15         if(x&1)bit[++tp]=1;     ///x&1表示取出x的最低位的数
16         else bit[++tp]=0;
17         x>>=1;  ///x>>1代表x右移一位
18     }
19     while(tp<32)bit[++tp]=0;    ///如果二进制数长度不够32则要在高位添0使数
20 }
21 void Insert(ll x){
22     tobit(x);
23     int rt=0;
24     for(int i=tp;i>=1;i--){                     ///从高位往低位建树
25         if(!tr[rt][bit[i]])tr[rt][bit[i]]=++tot;
26         rt=tr[rt][bit[i]];
27     }
28 }
29 ll query(ll x){
30     tobit(x);
31     int rt=0;
32     ll ans=0,base=1;
33     for(int i=tp;i>=1;i--){     ///从高位往低位匹配
34         if(tr[rt][bit[i]^1]){   ///如果与当前位的数相反的结点存在则访问这个结点
35            rt=tr[rt][bit[i]^1];
36            ans+=(1<<(i-1));     ///ans加上2的i-1次幂
37         }
38         else rt=tr[rt][bit[i]]; ///否则就访问与当前位的数相同的结点
39     }
40     return ans;
41 }
42 int main(){
43     int T;scanf("%d",&T);
44     ll ans;
45     while(T--){
46         init();
47         scanf("%d",&n);
48         for(int i=1;i<=n;i++){
49             scanf("%lld",&a[i]);
50             Insert(a[i]);
51         }
52         ans=0;
53         for(int i=1;i<=n;i++){
54             ans=max(ans,query(a[i]));   ///保存一个最大的答案来输出
55         }
56         printf("%lld
",ans);
57     }
58 }
59 /**
60 题意:在给定的 n 个整数 A1,A2,...,An 中选出两个进行 xor（异或）运算求出最大结果
61 思路:若要让2个数的异或结果尽可能的大,则他们每一位数从高位开始要尽可能的不同(什么是高位低位?123中1是相对2和3的高位,3是相对1和2的高位),
62 若用每一个数与其他数去比较,则是O(n*n)的复杂度,1e6的n会TLE,所以我们可以对n个数建一颗字典树来求一个数i与这n个数异或的最大值,枚举n个数保存一个最大值作为答案.
63 使用二进制来建字典树时,要从数的高位开始向低位建.
64 接着枚举第1到第n的数,看哪个数求得的异或值最大,对每个数从这个数的高位往低位在字典树中匹配,
65 如果与当前位的数相反的结点存在则访问这个结点并且ans加上2的i-1次幂,否则就访问与当前位的数相同的结点,
66 最后保存一个最大的答案并输出
67 **/