[AcWing143] 最大异或和 [字典树]
题意
给出N个整数，选择两个整数，使得异或和最大（\(0<A_i<2^{31}\)）
思路
从数据范围很容易想到二进制，进而想到字典树Trie。
字典树的典型应用是存储字符串，存储二进制也是一样的。
我一开始在处理取二进制位的时候想的比较麻烦，我是使用右移运算符先预处理出每个数的二进制表示，再根据二进制表示插入字典树中。后来了解到x >> i & 1;可以直接取二进制数的任意一位，这样简单了许多。
查询的时候，先取出对应位的二进制数，在树中先走该二进制数的对立面，如果对立面不存在，再沿着该二进制数向下走一层。
Code：
#include <bits/stdc++.h>
using namespace std;
#define fre freopen("data.in","r",stdin);
#define ms(a) memset((a),0,sizeof(a))
#define go(i,a,b) for(register int (i)=(a);(i)<(b);++(i))
#define rep(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
#define sf(x) scanf("%d",&(x))
#define reg register
typedef long long LL;
const int inf=(0x3f3f3f3f);
const int maxn=1e5+5;
int a[maxn],son[maxn*31][2],idx;
int n;
inline void insert(int x){
int p=0,t;
for(int i=30;i>=0;i--){
t= x >> i & 1; //取二进制数的第i位，从0开始
if(!son[p][t])son[p][t]=++idx;
p=son[p][t];
}
}
inline int query(int x){
int ans=0,t,p=0;
for(int i=30;i>=0;--i){
t=x>>i&1;
if(son[p][!t]){
p=son[p][!t];
ans|=(1<<i);
}
else {
p=son[p][t];
}
}
return ans;
}
int main(){
sf(n);
rep(i,1,n){
sf(a[i]);
insert(a[i]);
}
int mx=-1;
rep(i,1,n){
mx=max(mx,query(a[i]));
}
printf("%d",mx);
return 0;
}