2 3 2 3 4 5 1 5 4 1 4 6 5 6 3
Case #1: 4 3 Case #2: 4
//437MS 24520K #include<stdio.h> #include<string.h> #define ll long long int root,q; ll s[35]={1}; struct Node { int l,r; ll val; void clear(){l=r=-1;}//初始化 }node[32*100000]; void insert(int& root,int h,ll x) { if(root==-1) { root=q++; node[root].clear(); } if(h==-1) { node[root].val=x; return; } if(x&s[h])insert(node[root].r,h-1,x);//这一为是1,则沿着右子树走 else insert(node[root].l,h-1,x);//否则沿着左子树走 } void query(int root,int h,ll x) { if(h==-1) { printf("%lld\n",node[root].val); return; } if(((x&s[h])&&node[root].l!=-1)||(node[root].r==-1))//因为异或是0^1=0,0^0=1所以要使结果最大,则0应找1,1应找0 query(node[root].l,h-1,x); else query(node[root].r,h-1,x); } int main() { int t,cas=1; for(int i=1;i<=32;i++) s[i]=s[i-1]<<1; scanf("%d",&t); while(t--) { int n,m; q=0; root=-1; ll a,b; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld",&a); insert(root,32,a); } printf("Case #%d:\n",cas++); for(int i=1;i<=m;i++) { scanf("%lld",&b); query(root,32,b); } } return 0; }
HDU 4825 Xor Sum 字典树+位运算,布布扣,bubuko.com
原文:http://blog.csdn.net/crescent__moon/article/details/33758893