在给定的 \(N\) 个整数 \(A_1,A_2……A_N\) 中选出两个进行 \(xor\)(异或)运算,得到的结果最大是多少?
第一行输入一个整数 \(N\)。
第二行输入 \(N\) 个整数 \(A_1~A_N\)。
输出一个整数表示答案。
\(1≤N≤10^5,\)
\(0≤A_i<2^{31}\)
3 1 2 3
3
字典树
按位考虑,对数从高位开始建立一棵01tire,从前往后遍历,对一个数的一位尽量走位相反的方向,这样走到最后可以找到前面跟该数异或值最大的数
// Problem: 最大异或对 // Contest: AcWing // URL: https://www.acwing.com/problem/content/description/145/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> //#define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } int n,tr[2][3000005],idx=1; void insert(int x) { int p=1; for(int i=30;~i;i--) { int t=x>>i&1; if(tr[t][p]==0)tr[t][p]=++idx; p=tr[t][p]; } } int find(int x) { int res=0,p=1; for(int i=30;~i;i--) { int t=x>>i&1; if(tr[t^1][p])res|=1<<i,p=tr[t^1][p]; else if(!tr[t][p])break; else p=tr[t][p]; } return res; } int main() { int res=0; cin>>n; while(n--) { int x; cin>>x; res=max(res,find(x)); insert(x); } cout<<res; return 0; }