题目描述
巧用trie树,这题真不错
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 3200000 + 10;
int son[M][2], idx, a[N];
void insert(int x){
int p = 0;
for(int i = 31; i >= 0 ; i--){
int u = x >> i & 1;
if(!son[p][u])
son[p][u] = ++idx;
p = son[p][u];
}
}
int query(int x){
int p = 0, res = 0;
for(int i = 31; i >= 0; i--){
int u = x >> i & 1;
if(son[p][!u]){ // 亦或找不同的,如果有不同的进上一位
p = son[p][!u];
res += 1 << i; //亦或结果为1,进行累加
}
else{
//这种情况下亦或为0,相当于res保持不变
p = son[p][u];
}
}
return res;
}
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
insert(a[i]);
}
int res = 0;
for(int i = 0; i < n; i++)
res = max(res, query(a[i]));
cout << res << endl;
}