AcWing 143. 最大异或对
原题链接
简单
作者:
叱咤月海鱼鱼猫
,
2023-11-13 17:39:43
,
所有人可见
,
阅读 36
#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 1e5 + 10 ;
const int M = N * 31 ; // 每个数需要遍历31个节点,因此最多需要N*31个节点
int son[M][2] ,idx ; // 将每个数以二进制的方式存储,因此每个节点的子节点只有2个,0或1
int a[N] ;
void insert(int x){
int p = 0 ; // 指针,从根节点开始遍历
for(int i = 30 ; i >= 0 ; i--){ // 从最高位开始依次遍历每一位
/* &s表示取引用,方便后续修改节点的值 , s等价于son[p][x >> i &1]
* x >> i & 1 表示数x的第i位是多少,注意:最低位索引为0,数有31位 */
int &s = son[p][x >> i & 1] ;
if(!s) s = ++idx ; // 如果对应的子节点不存在,则创建
p = s ;
}
}
/*寻找与x异或后值最大的数,并返回其结果*/
int query_max_xor(int x){
int res = 0 , p = 0 ;
for(int i = 30 ; i >= 0 ; i--){
int s = x >> i & 1 ; // x的第i位的值
/* 要使异或值最大,就需要从最高位开始,每次尽可能走与当前位相反的分支,
* 即当前数的第i位为1,若存在0分支,则需要走0分支;反之,同理
* 若不存在相反分支,则只能走相同分支*/
if(son[p][!s]){ // 存在相反的分支
p = son[p][!s] ; // p走向相反分支
res += 1 << i ; // 每个相反分支为res的贡献值
}
else p = son[p][s] ; // 不存在相反分支,则只能走同分支,对res没有贡献
}
return res ;
}
int main(){
/*加快IO*/
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int n ;
cin >> n ;
for(int i = 0 ;i < n ; i++){
cin >> a[i] ;
insert(a[i]) ; // 构建01-trie树
}
int res = 0 ;
/*固定第一个数,查找集合中与该数进行异或的最大值,并选择数组中最大的异或值*/
for(int i = 0 ; i < n ; i++) res = max(res, query_max_xor(a[i])) ;
cout << res << endl ;
return 0 ;
}