trie树三连击biu~
《进阶指南》P72 例题
思路与上题无异, 只细节不同qaq
代码上!
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 const int sz = 100010; 5 int n, tot = 0; 6 int trie[sz*32][2], a[sz]; 7 void insert(int x) { 8 int root = 0; 9 for(int i = 31; i >= 0; i--) { 10 int id = (x>>i)&1; 11 if(!trie[root][id]) trie[root][id] = ++tot; 12 root = trie[root][id]; 13 } 14 } 15 int search(int x) { 16 int root = 0, sum = 0; 17 for(int i = 31; i >= 0; i--) { 18 int id = (x>>i)&1; 19 if(trie[root][id^1]) { 20 root = trie[root][id^1]; 21 sum = (sum<<1)|1; 22 } 23 else { 24 root = trie[root][id]; 25 sum = sum<<1; 26 } 27 } 28 return sum; 29 } 30 int main() { 31 int ans = 0; 32 scanf("%d", &n); 33 for(int i = 1; i <= n; i++) { 34 scanf("%d", &a[i]); 35 insert(a[i]); 36 } 37 for(int i = 1; i <= n; i++) { 38 if(search(a[i])>ans) { 39 ans = search(a[i]); 40 } 41 } 42 printf("%d\n", ans); 43 return 0; 44 }
【练习——trie树】the xor largest pair
原文:https://www.cnblogs.com/Hwjia/p/9800566.html