The XOR Largest Pair LibreOJ - 10050
题意：
给你n个数，要你找到两个数。使他们的异或最大。
思路：
直接找肯定
T
L
E
TLE
TLE,所以这时候要引进Trie树。
每次碰到一个数
x
x
x，都把
x
x
x按照二进制，加入trie树中。（这里的加入从二进制最高位开始看）每次加入一个数
x
x
x之前，可以把这个数
x
x
x与这棵trie树进行异或操作。（因为前面遇到一个数，都是贪心地从最高位开始insert。所以对于
x
x
x的search，也是从最高位开始，这一步就是贪心）
AC
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define mst(x,a) memset(x,a,sizeof(x))
using namespace std
;
const int maxnode
=4e6+10;
const int sigma_size
=2;
typedef long long ll
;
int sz
=1;
int ch
[maxnode
][sigma_size
];
void clear(){sz
=1;mst(ch
[1],0);}
void insert(ll str
){
int u
=1,n
=32;
for(int i
=n
; i
>=0; i
--){
ll k
=(str
>>i
)&1;
if(!ch
[u
][k
]){
mst(ch
[sz
+1],0);
ch
[u
][k
]=++sz
;
}
u
=ch
[u
][k
];
}
return ;
}
ll
search(ll str
){
ll res
=0;
ll u
=1,n
=32;
for(int i
=n
; i
>=0; i
--){
ll k
=(str
>>i
)&1;
if(ch
[u
][k
^1]){
u
=ch
[u
][k
^1];
res
+=(1<<i
);
}else u
=ch
[u
][k
];
}
return res
;
}
int main()
{
ios
::sync_with_stdio(0);cin
.tie(0);cout
.tie(0);
int n
;
cin
>>n
;
ll ans
=0,x
;
For(i
,1,n
){
cin
>>x
;
ans
=max(ans
,search(x
));
insert(x
);
}
cout
<<ans
<<endl
;
return 0;
}
