AcWing 143. 最大异或对 01字典树打卡

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

输入格式

第一行输入一个整数N。

第二行输入N个整数A1A1～ANAN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤1051≤N≤105,
0≤Ai<2310≤Ai<231

输入样例：

3
1 2 3

输出样例：

3


题意：让你求一对数，他们的异或值最大
思路：首先暴力肯定不行，1e5的范围，我们想想贪心高数位可不可以，我们为了保证异或值最大，肯定是从高位开始保留起，但是确实是要从高位开始找，但是我们这样不好查找
前面说了Trie是一个高效的查找数据结构，我们建立一个Trie,每插入一个节点我们就查找前面所有的，这样能查找到所有情况，因为我们是要查找最大异或，肯定是走与当前数字
相反的那一条路线，如果实在是另一条没有路，我们就只能走那条了，然后计算从上而下的计算值是多少
！叶子节点是二进制最低位，为什么呢，因为我们是要贪心从高位开始取，而我们字典树是从一开始就避免相同，所以正好与我们贪心取高位相吻合，所以必须按这个插入顺序

#include<bits/stdc++.h>
#define maxn 100005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,top;
ll a[maxn];
ll tree[maxn*32][2];
void insert(ll x){
    ll root=0;
    for(int i=0;i<32;i++){
        ll z=(x>>(31-i))&1;
        if(!tree[root][z]) tree[root][z]=++top;
        root=tree[root][z];
    } 
}
ll query(ll x){
    ll root=0;
    ll sum=0;
    for(int i=0;i<32;i++){
        ll z=(x>>(31-i))&1;
        if(tree[root][!z]){
            sum+=1<<(31-i);
            root=tree[root][!z];
        }
        else{
            root=tree[root][z];
        }
    }
    return sum;
}
int main(){
    scanf("%lld",&n);
    ll mx=0,x;
    for(int i=0;i<n;i++){
        scanf("%lld",&x);
        mx=max(mx,query(x)); 
        insert(x);
    }
    printf("%lld",mx);
}