【每日一题】The XOR Largest Pair 题解(01Trie)

Description

Solution

建立01Trie,对于每一个数字都从最高位开始建立字典树，并且贪心地从最高位开始在字典树上走，优先走该位不同的路线，最后取最大的答案。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int a[N];
int trie[N * 50][2];
int tot;
void add(int x) {
  int rt = 0;
  for(int i = 30; i >= 0; i--) {
    int cur = ((x >> i) & 1);
    if(!trie[rt][cur]) trie[rt][cur] = ++tot;
    rt = trie[rt][cur];
  }
}
int query(int x) {
  int ans(0), rt(0);
  for(int i = 30; i >= 0; i--) {
    int cur = ((x >> i) & 1);
    if(trie[rt][cur ^ 1]) {
      ans |= (1LL << i);
      rt = trie[rt][cur ^ 1];
    } else {
      rt = trie[rt][cur];
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i], add(a[i]);
  int ans(0);
  for(int i = 1; i <= n; i++) {
    ans = max(ans, query(a[i]));  
  } 
  cout << ans << '\n';
  return 0;  
}