AcWing 143. 最大异或对 C++
原题链接
简单
作者:
张立斌
,
2019-10-26 20:01:37
,
所有人可见
,
阅读 869
main
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
int n, x;
scanf("%d", &n);
Trie trie(1024);
int res = INT_MIN;
for (int i = 0; i < n; ++i) {
scanf("%d", &x);
trie.insert(x);
res = max(res, static_cast<int>(trie.searchMax(x)));
}
printf("%d\n", res);
return 0;
}
Trie
class Trie {
class TrieNode {
public:
explicit TrieNode() {
children[0] = 0;
children[1] = 0;
}
inline int &operator[](const int bit) { return children[bit]; }
inline int operator[](const int bit) const { return children[bit]; }
private:
int children[2];
};
public:
explicit Trie(int capacity = 64) {
nodeVec.reserve(capacity);
nodeVec.emplace_back();
}
void insert(uint32_t x) {
int j = 0;
for (int i = 31; i >= 0; --i) {
const int bit = (x >> i) & 1;
int &child = nodeVec[j][bit];
if (!child) {
child = nodeSize();
nodeVec.emplace_back();
}
j = nodeVec[j][bit];
}
}
uint32_t searchMax(uint32_t x) const {
int j = 0, res = 0;
for (int i = 31; i >= 0; --i) {
const int bit1 = (x >> i) & 1;
const int bit0 = bit1 ^ 1;
if (nodeVec[j][bit0]) {
j = nodeVec[j][bit0];
res |= 1 << i;
} else {
j = nodeVec[j][bit1];
}
}
return res;
}
private:
inline int nodeSize() const { return nodeVec.size(); }
vector<TrieNode> nodeVec;
};