Skip to content

Instantly share code, notes, and snippets.

@dylanliuh2o
Created October 7, 2021 15:17
Show Gist options
  • Save dylanliuh2o/64d8ce6b4c673334b557234db07fbcc0 to your computer and use it in GitHub Desktop.
Save dylanliuh2o/64d8ce6b4c673334b557234db07fbcc0 to your computer and use it in GitHub Desktop.
AcWing 143. 最大异或对
#include <iostream>
#include <vector>
#include <array>
using namespace std;
class TrieTree {
public:
TrieTree() : nodeSize(1) { }
void insert(int num) {
int currNodeIndex = 0;
for (int digit = 30; digit >= 0; digit--) {
int bit = (num >> digit) & 1;
/* node does not exist */
if (nodes[currNodeIndex][bit] == 0) {
nodeSize++;
nodes[currNodeIndex][bit] = nodeSize-1;
}
/* jump to next node */
currNodeIndex = nodes[currNodeIndex][bit];
}
}
int query(int num) {
int ans = 0;
int currNodeIndex = 0;
for (int i = 30; i >= 0; i--) {
int bit = (num >> i) & 1;
if (nodes[currNodeIndex][!bit] != 0) {
ans += (1 << i);
currNodeIndex = nodes[currNodeIndex][!bit];
} else {
currNodeIndex = nodes[currNodeIndex][bit];
}
}
return ans;
}
private:
array<array<int, 2>, static_cast<long unsigned int>(32*(1e5))> nodes;
int nodeSize = 0;
};
int main()
{
int N;
TrieTree trie;
vector<int> nums;
cin >> N;
int num;
for (int i = 0; i < N; i++) {
cin >> num;
nums.push_back(num);
trie.insert(num);
}
int ans = 0;
for (auto val : nums) {
ans = max(ans, trie.query(val));
}
cout << ans;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment