首页 > 代码库 > 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): 1786 Accepted Submission(s): 758
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
Source
2014年百度之星程序设计大赛 - 资格赛
同Trie水题,但多叉字典树的模板不可用了,因为时间效率太过低下(每次都无法一次性定位),所以干脆用数组去做。
以下是超时模板:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define clr(x) memset(x,0,sizeof(x)) 5 #define clrmin(x) memset(x,-1,sizeof(x)) 6 #define LL long long 7 using namespace std; 8 struct node 9 { 10 int lt,rt; 11 bool num; 12 LL val; 13 }; 14 struct Trie 15 { 16 int head,len; 17 node tr[500010]; 18 Trie () { clr(tr); head=0; len=1;} 19 void init() 20 { 21 clr(tr); 22 head=0; 23 len=1; 24 return ; 25 } 26 int newnode(LL num,int dep) 27 { 28 if(!head) 29 { 30 head=len; 31 } 32 tr[len].num=((num>>(32-dep))%2)^1; 33 return len++; 34 } 35 void push(int fa,int now,LL num,int dep) 36 { 37 int p; 38 if(!now) 39 { 40 now=newnode(num,dep); 41 tr[fa].lt=now; 42 if(dep==32) 43 tr[now].val=num; 44 else 45 push(now,0,num,dep+1); 46 return ; 47 } 48 while(now && (((num>>(32-dep))%2)^1)!=tr[now].num) 49 { 50 p=now; 51 now=tr[now].rt; 52 } 53 if(!now) 54 { 55 now=newnode(num,dep); 56 tr[p].rt=now; 57 } 58 if(dep==32) 59 tr[now].val=num; 60 else 61 push(now,tr[now].lt,num,dep+1); 62 return; 63 } 64 LL getxor(int now,LL num,int dep) 65 { 66 int p; 67 while(now && (num>>(32-dep))%2!=tr[now].num) 68 { 69 p=now; 70 now=tr[now].rt; 71 } 72 if(!now) 73 { 74 if(dep==32) 75 return tr[p].val; 76 else 77 return getxor(tr[p].lt,num,dep+1); 78 } 79 else 80 { 81 if(dep==32) 82 return tr[now].val; 83 else 84 return getxor(tr[now].lt,num,dep+1); 85 } 86 } 87 }tree; 88 int main() 89 { 90 int T,n,m; 91 LL num; 92 scanf("%d",&T); 93 for(int kase=1;kase<=T;kase++) 94 { 95 tree.init(); 96 printf("Case #%d:\n",kase); 97 scanf("%d%d",&n,&m); 98 for(int i=1;i<=n;i++) 99 { 100 scanf("%lld",&num); 101 tree.push(0,tree.head,num,0); 102 } 103 for(int i=1;i<=m;i++) 104 { 105 scanf("%lld",&num); 106 printf("%lld\n",tree.getxor(tree.head,num,0)); 107 } 108 } 109 return 0; 110 }
hdu 4825(Trie)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。