AcWing 143. 最大异或对
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-16 09:17:47
,
所有人可见
,
阅读 264
#include <iostream>
using namespace std;
// 此时在数组中定义长度的变量一定是使用const来进行修饰
const int N = 100010,M = 31 * N;
int a[N], son[M][2], idx;
void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; i --) {
//此时是取得第i位上的二进制值
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
}
int query(int x) { //此时就是来找到与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() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
int res = 0;
for (int i = 0; i < n; i ++) {
insert(a[i]);
int t = query(a[i]);
res = max(res, a[i] ^ t);
}
printf("%d", res);
return 0;
}