HDU 4825 Xor Sum(二进制的字典树,数组模拟)

时间:2022-10-28 07:59:19

题目

//居然可以用字典树。。。
//用cin,cout等输入输出会超时

//这是从别处复制来的

#include<cstdio>
#include<algorithm>
#include<cstring> using namespace std; int node[][];
int tag,m,n,cas=,T;
long long one[],allone,tmp;
//0/1树的加数据操作,增加一个32的数
//其中如果当前位是0,则加左儿子,否则加右儿子,即这棵树中左儿子表示0,右儿子表示1
void add(long long temp) // l 0 r 1
{
int rt=,t;//rt为当前节点
for(int i=;i>=; i--)
{
t=temp&one[i]?:;//取得当前位是0还是1
if(node[rt][t]==-)//如果没有对应的儿子,就增加给它分配一个数组的下标
node[rt][t]=++tag;
rt=node[rt][t];//迭代执行
}
} long long lookfor(long long temp)//查找答案
{
int rt=,t;
long long ans=;
for(int i=; i>=; i--)
{
t=temp&one[i]?:;// temp&one[i] 1
if(node[rt][t]==-) t=t^;//如果没有与当前符合的儿子,则选择相反的儿子,显然这个儿子一定存在
rt=node[rt][t];//迭代当前节点
ans=ans*+t;//计算出查找的值
}
return ans;
} int main()
{
//freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
one[]=;
for(int i=; i<; i++)//得到2的幂次的数组
one[i]=one[i-]<<; allone=one[]-;//0xffffffff 用来异或
//printf("one %I64d\n",allone);
scanf("%d",&T);
while(T--)
{
tag=;//注意这个初始化,
memset(node,-,sizeof(node));
scanf("%d%d",&m,&n);
for(int i=; i<m; i++)
{
scanf("%I64d",&tmp);
add(tmp);
}
printf("Case #%d:\n",++cas);
for(int i=; i<n; i++)
{
scanf("%I64d",&tmp);//tmp为要查找的值
tmp=tmp^allone;//tmp变成和原来的它异或值最大的数,而我们就是要查找,最接近它的一个数m,接近是,数值和二进制的形式接近
printf("%I64d\n",lookfor(tmp));
}
}
return ;
}

//这是我看懂之后,跟着写了一遍(嘻嘻,因为是找这写的,所以差不多。。)