首页 > 其他 > 详细

【练习——trie树】the xor largest pair

时间:2018-10-16 21:14:40      阅读:219      评论:0      收藏:0      [点我收藏+]

LOJ #10050. The XOR Largest Pair

trie树三连击biu~

《进阶指南》P72 例题

思路与上题无异, 只细节不同qaq

  1. 分解二进制,高位在前, 建立trie树(0/1)
  2. search操作:首选不同的(xor值才能大), 就等于在后面加了一个1, 所以 sum = (sum<<1)|1
  3. 如果没有不同的, 就等于在后面加了一个0, 所以 sum = (sum<<1);
  4. (唔为什么变紫色了啊啊啊
  5. 如果从32开始枚举, 爆int 记得开long long , (gjh:多枚举几位, 开个long long保险啊! )这题从31开始也可以, 只要int即可
  6. 后面search(a[i]) 写成search(i) 可还行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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!