AcWing 143. 最大异或对 C++
原题链接
简单
作者:
LaChimere
,
2021-05-20 14:16:56
,
所有人可见
,
阅读 295
C++
#include <iostream>
using namespace std;
const int N = 100010, MAXSIZE = 31 * N;
int trie[MAXSIZE][2], idx;
void insert(int x) {
int p = 0;
for (int k = 30; k >= 0; --k) {
int xBit = (x >> k) & 1;
if (!trie[p][xBit]) {
trie[p][xBit] = ++idx;
}
p = trie[p][xBit];
}
}
int query(int x) {
int p = 0, y = 0;
for (int k = 30; k >= 0; --k) {
int xBit = (x >> k) & 1;
if (trie[p][!xBit]) {
p = trie[p][!xBit];
y = (y << 1) + !xBit;
} else {
p = trie[p][xBit];
y = (y << 1) + xBit;
}
}
return y;
}
int main() {
int n, x, curMax = 0;
cin >> n;
while (n--) {
cin >> x;
insert(x);
int y = query(x);
curMax = max(curMax, x ^ y);
}
cout << curMax << endl;
return 0;
}