题目大意：从n个数中选出两个数异或，求最大的异或值。
1≤N≤10^5
0≤Ai<2^ 31
题解：
首先考虑暴力的写法
for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { ans=max(ans,a[i]^a[j]); } }
考虑用数据结构优化，对于每个枚举到的数，找到与它异或结果最大的数。
假设第i个数001101101那么它与110010010异或，结果是最大的，从第i个数的高位开始看，尽量从剩下的n-1个数中找高位与它二进制相反的。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100000+10; int n,cnt; int t[N][2]; int a[N]; long long ans; inline int read() { int x=0,f=-1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } void insert(int x) { int p=0; for(int i=30;~i;i--) { if(t[p][(x>>i)&1]==0) t[p][(x>>i)&1]=++cnt; p=t[p][(x>>i)&1]; } } long long slove(int x) { long long res=0; int p=0; for(int i=30;~i;i--) { if(t[p][!((x>>i)&1)]) { res=res+1<<i; p=t[p][!((x>>i)&1)]; }else p=t[p][(x>>i)&1]; } return res; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { a[i]=read(); insert(a[i]); } for(int i=1;i<=n;i++) { ans=max(ans,slove(a[i])); } cout<<ans; return 0; }
原文：https://www.cnblogs.com/zzyh/p/14791108.html