首页 > 代码库 > HDU 4825 Xor Sum(二进制的字典树,数组模拟)
HDU 4825 Xor Sum(二进制的字典树,数组模拟)
题目
//居然可以用字典树。。。
//用cin,cout等输入输出会超时
//这是从别处复制来的
#include<cstdio>#include<algorithm>#include<cstring>using namespace std;int node[3011111][2];int tag,m,n,cas=0,T;long long one[64],allone,tmp;//0/1树的加数据操作,增加一个32的数//其中如果当前位是0,则加左儿子,否则加右儿子,即这棵树中左儿子表示0,右儿子表示1void add(long long temp) // l 0 r 1{ int rt=0,t;//rt为当前节点 for(int i=31;i>=0; i--) { t=temp&one[i]?1:0;//取得当前位是0还是1 if(node[rt][t]==-1)//如果没有对应的儿子,就增加给它分配一个数组的下标 node[rt][t]=++tag; rt=node[rt][t];//迭代执行 }}long long lookfor(long long temp)//查找答案{ int rt=0,t; long long ans=0; for(int i=31; i>=0; i--) { t=temp&one[i]?1:0;// temp&one[i] 1 if(node[rt][t]==-1) t=t^1;//如果没有与当前符合的儿子,则选择相反的儿子,显然这个儿子一定存在 rt=node[rt][t];//迭代当前节点 ans=ans*2+t;//计算出查找的值 } return ans;}int main(){ //freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); one[0]=1; for(int i=1; i<60; i++)//得到2的幂次的数组 one[i]=one[i-1]<<1; allone=one[32]-1;//0xffffffff 用来异或 //printf("one %I64d\n",allone); scanf("%d",&T); while(T--) { tag=0;//注意这个初始化, memset(node,-1,sizeof(node)); scanf("%d%d",&m,&n); for(int i=0; i<m; i++) { scanf("%I64d",&tmp); add(tmp); } printf("Case #%d:\n",++cas); for(int i=0; i<n; i++) { scanf("%I64d",&tmp);//tmp为要查找的值 tmp=tmp^allone;//tmp变成和原来的它异或值最大的数,而我们就是要查找,最接近它的一个数m,接近是,数值和二进制的形式接近 printf("%I64d\n",lookfor(tmp)); } } return 0;}
//这是我看懂之后,跟着写了一遍(嘻嘻,因为是找这写的,所以差不多。。)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。