Xor Sum
一遍A了之后大呼一声好（keng）题！debug了两小时~~~~百度之星资格赛，可以。
题意：给你一个n个元素的数组，m次查询，每次输入一个数k要求从数组中找到一个数与k异或值最大，输出这个数。
思路：因为拉的字典树专题，所以自然想到用字典树去想思路，手推了一下样例果然发现规律了，把这些数的二进制全部竖着列出来，不足高位补0，然后每次比较比较一个数，从高位开始比较，取其相反即可。于是可以用字典树把输入的数的二进制建树，查找只需转化成二进制然后再转成补码（字典树匹配），特别特别注意的是某个节点往下之后可能会出现空节点，这样只能取存在的节点继续往下了。
相当于一颗二叉树，我猜后天不会很强大，因为动态建树释放内存会消耗时间的。。
struct tree
{
ll f;
tree *next[N];
tree()
{
for(int i=0; i<N; i++) next[i]=NULL;
f=0;
}
};
int a[33];
void insert(tree *root,int *a)
{
int len=31;
tree *p=root;
while(len>=0)
{
int id=a[len];
if(p->next[id]==NULL)
{
tree *temp=new tree();
p->next[id]=temp;
}
p=p->next[id];
if(id) p->f=ll(1)<<len;
len--;
}
}
ll find(tree *root,int *a)
{
tree *p=root;
int len=31;
ll ans=0;
while(len>=0)
{
int id=a[len];
if(p->next[id]==NULL) id^=1;//取存在的节点往下
p=p->next[id];
if(id) ans+=p->f;
len--;
}
return ans;
}
void del(tree *root)
{
for(int i=0; i<N; i++)
if(root->next[i])
del(root->next[i]);
delete(root);
}
void ch(int n,int *a)
{
int len=0;
while(n)
{
a[len++]=n%2;
n/=2;
}
}
int main()
{
int t,n,m;
scanf("%d",&t);
int t1=1;
while(t--)
{
tree *root=new tree();
scanf("%d%d",&n,&m);
int x;
for(int i=0; i<n; i++)
{
scanf("%d",&x);
memset(a,0,sizeof(a));//这个memset放在函数里实现就不行，坑了我两小时~~
ch(x,a);
insert(root,a);
}
printf("Case #%d:\n",t1++);
while(m--)
{
scanf("%d",&x);
memset(a,0,sizeof(a));
ch(x,a);
for(int i=0; i<32; i++) a[i]^=1;//转化成补码
printf("%I64d\n",find(root,a));
}
del(root);
}
return 0;
}
不知你注意了没有，建树是从高位往下建的，这样是一个贪心思路，优先取高位~~
还有一个问题，在输入数据的时候都需要转化成二进制，所以开始我把memset函数放在ch（）函数里，每次调用优先执行这个清空函数，但样例第一组输入1的时候却输出3，然后各种debug~~~，如果有大牛路过望不惜赐教！