Created
October 7, 2021 15:17
-
-
Save dylanliuh2o/64d8ce6b4c673334b557234db07fbcc0 to your computer and use it in GitHub Desktop.
AcWing 143. 最大异或对
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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