思路:
直观的做法是枚举,枚举步骤是:
步骤1:枚举每一个数
步骤2:枚举每一个数并与步骤1中枚举的数异或,选取其中的最大值
但是时间复杂度是o(n^2)级别的,显然会超时
优化:
对于步骤1,我们只需枚举二进制下最高位1的最大位数
解释:比如最高位1的最大位数是k,那么对于任何小于1<<k的数无论如何异或都不会超过1<<k;
对于步骤2,此时步骤1的数已经固定了,那么我们尽量从它二进制下的最高位开始找不同与它的数(trie字典)
#include<iostream>
#include<algorithm>
using namespace std ;
const int MAX = 1e5 + 5, M = 3e6 + 10 ;
int f[MAX], son[M][2], idx, N ;
void insert(){
for(int i = 0; i < N; i++){
int p = 0 ;
for(int j = 30; j >= 0; j--){
int &s = son[p][(f[i] >> j) & 1] ;
if(s == 0){
s = ++idx ;
}
p = s ;
}
}
}
int upper_bit(int v){
int res = v ;
while(v != 0){
res = v ;
v -= v & -v ;
}
return res ;
}
int get_Max(int v){
int p = 0, res = 0 ;
for(int i = 30; i >= 0; i--){ // 从最高位开始枚举
int x = (v >> i) & 1 ;
if(son[p][1 - x]){ // 优先取不同的数
res += (1 << i) ;
p = son[p][1 - x] ;
} else{
p = son[p][x] ;
}
}
return res ;
}
int main(){
int res = 0, mx = 0 ;
cin >> N ;
for(int i = 0; i < N; i++){
cin >> f[i] ;
mx = max(mx, f[i]) ; // 先找出最大值
}
insert() ;
mx = upper_bit(mx) ; //取出最高位
for(int i = 0; i < N; i++){
if(f[i] >= mx){
res = max(res, get_Max(f[i])) ;
}
}
cout << res << endl;
}