正题 ybtoj Trie-2
题目大意
给你n个数，选择2个，使其异或值最大
解题思路
对于每个数的二进制建立Trie，然后每个数在Trie中搜索，每次尽量走不同方向
代码 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long long#define N 100100using namespace std;int n, x, w, ans, to[N*32][2];void insert(int x){int now = 0, y;for (int i = 30; i >= 0; --i){y = (x>>i)&1;if (!to[now][y]) to[now][y] = ++w;now = to[now][y];}return;}int ask(int x){int ans = 0, now = 0, y = 0;for (int i = 30; i >= 0; --i){y = (x>>i)&1^1;//走不同方向if (to[now][y]) ans += 1<<i;else y ^= 1;now = to[now][y];}return ans;}int main(){scanf("%d", &n);for (int i = 1; i <= n; ++i){scanf("%d",&x);ans = max(ans, ask(x));insert(x);}printf("%d", ans);return 0;}
