AcWing 143. 最大异或对
标签：algorithm lse 一个 方向 插入 res 进制 pac stream
//先转换成二进制，然后从从高位开始异或
#include
#include
using namespace std;
const int N = 100010, M = 3000000;
int n;
int a[N], son[M][2], idx;
void insert(int x) {
int p = 0;
for (int i = 30; 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=30; i>=0; i--) {
int u=x>>i&1;//取出最高位 当前位
if(son[p][!u]) { //如果另外一个方向存在
p=son[p][!u];
res=res*2+!u;//相当于把所有数字往左移动一位
} else {
p=son[p][u];
res=res*2+u;
}
}
return res;
}
int main() {
cin>>n;
for(int i=0; i>a[i];
int res=0;
for(int i=0; i) {
insert(a[i]);//先插入 为了不处理空集的情况
int t=query(a[i]);//再查询
res=max(res,a[i]^t);
}
coutendl;
}
AcWing 143. 最大异或对
标签：algorithm lse 一个 方向 插入 res 进制 pac stream
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/11816422.html
评论