洛谷 P10471 最大异或对 The XOR Largest Pair
题目描述
给定 N 个整数 A1.A2,⋯,AN 中选出两个进行异或计算，得到的结果最大是多少？
输入格式
第一行一个整数 N，第二行 N 个整数 A1.A2,⋯,AN。
输出格式
一个整数表示答案。
输入输出样例
输入 #1复制
3 1 2 3输出 #1复制
3说明/提示
对于所有测试数据，1≤N≤105，保证 0≤Ai<231。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int tr[N*32][2]; int idx; int a[N]; void insert(int x) { int cur=0; for(int i=31;i>=0;i--) { int path=(x>>i)&1; if(tr[cur][path]==0) tr[cur][path]=++idx; cur=tr[cur][path]; } } int find(int x) { int cur=0; int ret=0; for(int i=31;i>=0;i--) { int path=(x>>i)&1; if(tr[cur][path^1]) { ret |=(1<<i); cur=tr[cur][path^1]; }else{ cur=tr[cur][path]; } } return ret; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; insert(a[i]); } int ret=0; for(int i=1;i<=n;i++) { ret=max(ret,find(a[i])); } cout<<ret<<endl; return 0; }