描述
Keroro来侵略地球之前，曾跟Giroro伍长打赌：“我一个人灭掉整个地球给你看！”.
于是Keroro同学真的自己一个人来到地球开始他的侵略行动了。从K隆星出发之前，Keroro从Kururu曹长那儿拿了若干台左手武器{Li}和若干台右手武器{Ri}，Keroro需要从{Li}里选一台左手武器，从{Ri}里选一台右手武器，用来组合成可用的恐怖武器。
左右手武器组合的规则很简单，假设从{Li}选出来攻击力为p的武器，从{Ri}选出来攻击力为q的武器，组合起来的攻击力就是p XOR q.
Keroro想知道，他能组合成的最强武器攻击力为多少？
Hint：必须左右手武器都选出来一个，才能组合成可用武器
XOR表二进制里的“异或”操作，pascal语言里是"xor", C/C++/Java里是"^".
输入
第一行两个整数n, m (1 <= n,m <= 100000), 表有n件左手武器，m件右手武器。
第二行n个正整数{L},li表第i件左手武器的攻击力，0 <= li <= 10^12
第三行m个正整数{R},ri表第i件右手武器的攻击力，0 <= ri <= 10^12
输出
最强组合武器的最大值。
样例输入
6 8
179
667
43
65
217
717
798
495
810
380
553
650
350
52
样例输出
1011
直接求解的话,时间复杂度为O(N^2),肯定超时.异或的操作可以看做按位匹配,使用字典树,时间复杂度降为O(N).
代码如下:
#include<iostream>
using namespace std;
int maxx;
struct node
{
struct node *zero,*one;
node()
{
zero=NULL;
one=NULL;
}
}*first;
struct node *p,*q;
int pos=1;
void insert(int a)
{
p=first;
int i=31;
while(i--)
{
if(a&pos)
{
if(p->one)
p=p->one;
else
{
q=new struct node;
p->one=q;
p=q;
}
}else
{
if(p->zero)
p=p->zero;
else
{
q=new struct node;
p->zero=q;
p=q;
}
}
a=a<<1;
}
}
void query(int a)
{
int temp=0;
p=first;
int i=31;
int pos1=pos;
while(i--)
{
if(a&pos1)
{
if(p->zero)
{
p=p->zero;
temp+=pos1;
}
else
{
p=p->one;
}
}
else
{
if(p->one)
{
p=p->one;
temp+=pos1;
}
else
{
p=p->zero;
}
}
pos1=pos1>>1;
}
if(temp>maxx)
maxx=temp;
}
int main()
{
// freopen("aa.txt","r",stdin);
int i=30;
while(i--)
{
pos=pos<<1;
}
int n,k,m,a;
p=new struct node;
first=p;
maxx=-1;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a;
insert(a);
}
for(int j=0;j<m;j++)
{
cin>>a;
query(a);
}
cout<<maxx<<endl;
return 0;
}acm.njupt--2026,布布扣,bubuko.com
原文：http://blog.csdn.net/ice110956/article/details/20154721