首页 > 代码库 > 2014百度之星资格赛—— Xor Sum(01字典树)
2014百度之星资格赛—— Xor Sum(01字典树)
Xor Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
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。
Output
对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。 对于每个询问,输出一个正整数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
题解:把集合中的每一个数,都存放到深度为32的01字典树;左结点为0,右结点为1;然后询问数s取反与字典树中的存的数比 较找出最大异或数;
对于任意非负整数x,可以沿着树根往下贪心找到y,使得a异或y最大,复杂度为树的深度。
下面为代码实现
#include<stdio.h> #include<iostream> #include<stdlib.h> using namespace std; typedef struct tire{ __int64 w; //从根节点到该结点的 struct tire *next[2]; //每个节点下面可能有2个数,0和1 }tree,*tiretree; /* 字典树的存储结构 */ tiretree T; void insert(__int64 a) //把a的32位二进制码插入到字典树中 { int i; tiretree q,p; q=T; for(i=31;i>=0;i--) { if(!(a&1<<i)) //若为0就插入到第一个子结点,a的32位二进制码是按高位往地位从根节点到叶子结点存放的; { p=q->next[0]; if(p==NULL) //如果该二进制数应该在的位置为空,则将二进制数插入到该位置 { p=(tiretree)malloc(sizeof(tree)); p->next[0]=NULL; p->next[1]=NULL; if(i==0) //若a结点达到叶子节点,就把a存到叶子结点中; p->w=a; else p->w=0; //若为a的中间经过结点,则不赋值;即字典树中只有叶子结点有数字,其余结点都为0; q->next[0]=p; } q=p; } else { p=q->next[1]; //若为1就插入到第二个子结点, if(p==NULL) { p=(tiretree)malloc(sizeof(tree)); p->next[0]=NULL; p->next[1]=NULL; if(i==0) p->w=a; else p->w=0; q->next[1]=p; } q=q->next[1]; //如果该二进制应该在的位置不空,则继续比较下一个二进制 } } } __int64 find(__int64 a) // 对于任意非负整数x,可以沿着树根往下贪心找到y,使得a异或y最大,复杂度为树的深度。 { int i; tiretree q; q=T; for(i=31;i>=0;i--) { if(q->next[0]==NULL) q=q->next[1]; else if(q->next[1]==NULL) q=q->next[0]; else if((a&1<<i)==0) q=q->next[0]; else q=q->next[1]; } return q->w; } int main() { int n,i,p,TT,count=0; __int64 max,a,m,q; scanf("%d",&TT); while(TT--) { scanf("%d %d",&n,&p); delete(T); T=(tiretree)malloc(sizeof(tree)); //构造单个根结点 T->next[0]=NULL; T->next[1]=NULL; T->w=0; max=0; for(i=0;i<n;i++) { scanf("%I64d",&a); insert(a); //分别把集合中的每个数插入到树中 } for(i=0;i<p;i++) { scanf("%I64d",&q); m=~q; //然后把要比较的数取反后,与字典树中存的数进行比较 if(i==0) printf("Case #%d:\n",++count); printf("%I64d\n",find(m)); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。