首页 > 代码库 > HDU 4825 Trie树 异或树!
HDU 4825 Trie树 异或树!
Xor Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 2403 Accepted Submission(s): 1041
Problem Description
Zeus
和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向
Zeus 发起M次询问,每次询问中包含一个正整数 S ,之后 Zeus 需要在集合当中找出一个正整数 K ,使得 K 与 S
的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大,随即同意 Zeus 可以向人类求助。你能证明人类的智慧么?
Input
输入包含若干组测试数据,每组测试数据包含若干行。
输入的第一行是一个整数T(T < 10),表示共有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。
输入的第一行是一个整数T(T < 10),表示共有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。
Output
对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。
对于每个询问,输出一个正整数K,使得K与S异或值最大。
对于每个询问,输出一个正整数K,使得K与S异或值最大。
Sample Input
2
3 2
3 4 5
1
5
4 1
4 6 5 6
3
Sample Output
Case #1:
4
3
Case #2:
4
先声明自己智障的看错输出的结果,以为输出最大的异或后的值,谁知道与哪个数异或后的值最大,就输出那个数,尴尬还以为样例错了。。。
字典树这样玩真的好酷炫,我是看了用字典树才想到怎么写惭愧,这样真的好巧妙,利用了字典树前缀和的思想在O(len)的时间就能算出结果!
将每个数按二进制33位不够得话高位补零,从高到低位存入字典树中,其实就是一颗只含01的字典树。
之所以由高到低是由于高位决定数的大小(贪心思想),对于读入的每个数也按33位在树上匹配,在满足条件的情况下尽可能的选择与bit不相同的位置走,
这样答案就会最大,最后输出ans^num就是原来的数!
可能动态键树释放内存的操作时间挺慢的跑700+ms,我看静态数组都是200左右
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 5 struct node 6 { 7 node *child[2]; 8 node(){child[0]=child[1]=NULL;} 9 }; 10 node *root; 11 void Clear(node *p) 12 { 13 if(p==NULL) return; 14 for(int i=0;i<2;++i){ 15 if(p->child[i]!=NULL) Clear(p->child[i]); 16 } 17 delete p; 18 } 19 void add(LL num) 20 { 21 node *p=root; 22 int i,bit; 23 for(i=32;i>=0;--i){ 24 bit=(num&((LL)1<<i))?1:0; 25 if(p->child[bit]==NULL) 26 p->child[bit]=new node(); 27 p=p->child[bit]; 28 } 29 } 30 LL solve(LL num) 31 { 32 node *p=root; 33 int i,bit[2]; LL ans=0; 34 for(i=32;i>=0;--i){ 35 bit[0]=(num&((LL)1<<i))?1:0; 36 if(p->child[bit[0]^1]!=NULL){ 37 p=p->child[bit[0]^1]; 38 bit[1]=1; 39 } 40 else {p=p->child[bit[0]];bit[1]=0;} 41 if(bit[1]) ans+=((LL)1<<i); 42 } 43 return ans; 44 } 45 int main() 46 { 47 int T,N,M,i,j,k=0; 48 LL n; 49 cin>>T; 50 while(T--){root=new node(); 51 cin>>N>>M; 52 for(i=1;i<=N;++i){ 53 scanf("%lld",&n); 54 add(n); 55 }printf("Case #%d:\n",++k); 56 for(i=1;i<=M;++i){ 57 scanf("%lld",&n); 58 printf("%lld\n",n^solve(n)); 59 } 60 Clear(root); 61 } 62 return 0; 63 }
HDU 4825 Trie树 异或树!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。