AcWing 143. 最大异或对
原题链接
简单
作者:
cppgod
,
2021-05-10 21:30:03
,
所有人可见
,
阅读 221
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1E5 + 5;
int arr[MAXN];
int n;
struct TrieNode {
TrieNode* child[2];
TrieNode(){
for (int i = 0; i < 2; ++i) {
child[i] = nullptr;
}
};
~TrieNode() {
for (int i = 0; i < 2; ++i) {
if (child[i])
delete child[i];
}
}
};
class Trie {
public:
Trie() : root(new TrieNode()) {};
~Trie() {
delete root;
}
void insert(int v) {
auto ptr = root;
for (int i = 31; i >= 0; --i) {
int bit = (v >> i & 0x1);
if (ptr->child[bit] == nullptr)
ptr->child[bit] = new TrieNode();
ptr = ptr->child[bit];
}
}
int query(int v) {
auto ptr = root;
int cur = 0;
for (int i = 31; i >= 0; --i) {
int bit = v >> i & 0x1;
if (ptr->child[bit ^ 1]) {
cur += (1 << i);
ptr = ptr->child[bit ^ 1];
} else {
ptr = ptr->child[bit];
}
}
return cur;
}
private:
TrieNode* root;
};
int main()
{
cin >> n;
for (int i = 0; i < n; ++i)
cin >> arr[i];
Trie trie;
for (int i = 0; i < n; ++i) {
trie.insert(arr[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, trie.query(arr[i]));
}
cout << ans;
}