2.数据结构：2.最大异或对

数据结构

• 2.数据结构：1.Tire 字符串统计

当前题

最大异或对

#include<algorithm>
#include<cstring>
#include<iostream>using namespace std;const int N=100010,M=31*N;// M 表示节点个数，每一个数最多有 31 位int n;
int a[N];
int son[M][2];
int idx;//把二进制的每一位插入 Trie 树
void insert(int x){int p=0;for(int i=30;i>=0;i--){//从最高位开始插入int &s=son[p][x>>i&1];if(!s){s=++idx;}p=s;}
}int query(int x){int p=0;int ans=0;for(int i=30;i>=0;i--){int u=x>>i&1;if(son[p][!u]){//尽可能取不同的数字，如给的数字是 1 ，尽可能ans+=1<<i;//选择 0p=son[p][!u];}else{p=son[p][u];}}return ans;
}int main(){cin>>n;for(int i=0;i<n;i++){cin>>a[i];insert(a[i]);}int ans=0;for(int i=0;i<n;i++){ans=max(ans,query(a[i]));}cout<<ans<<endl;return 0;
}