这么水的题目折腾了一天,因为var[]数组开小了+多输出了一个空格一直WA。。期间学会了怎么对拍=。=
建立一个字典树,从最高位往下搜索,因为要保证异或和最大,每次往相反的方向搜索。
智硬的鄙人开始还以为节点数组大小等于满二叉树的节点数,后来发现最多用到的节点数就是 10W*32 =凸=
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include <cmath> #include<algorithm> #include<stack> using namespace std; const int M=3400000;//最多只会用到 33*10W个结点,32 nodes need 33 levels int T; long long node[M][2];//字典树,左为1右为0 long long var[M]; long long a; long long b; long long num;//用到的节点数 long long ans; int n; int m; void Add(long long x) { int k,c=0; for(int i=31;i>=0;i--)//从高位到低位 { long long tmp=(1<<i)&x; if(tmp>0) { k=1; } else { k=0; } // cout<<(2&3)<<endl; // cout <<((1<<i)&x)<<" k: "<<k<<endl; if(k==1) { if(node[c][0]==0) { node[c][0]=num++; } c=node[c][0]; } if(k==0) { if(node[c][1]==0) { node[c][1]=num++; } c=node[c][1]; } } var[c]=x; // for(int i=0;i<num;i++) // { // cout<<node[i][0]<<" "<<node[i][1]<<endl; //} //cout<<endl; // cout<<"c: "<<c<<" "<<var[c]<<endl; } void Search(long long x) { int k,c=0; for(int i=31;i>=0;i--) { long long tmp=(1<<i)&x; if(tmp>0) { k=1; } else { k=0; } if(k==1&&node[c][1]) { c=node[c][1]; } else if(k==0&&node[c][0]) { c=node[c][0]; } else { c=node[c][0]?node[c][0]:node[c][1]; } } ans=var[c]; } void input() { num=1; ans=0; memset(var,0,sizeof(var)); memset(node,0,sizeof(node)); // for(int i=0;i<M;i++) {node[i][0]=0; node[i][1]=0;var[i]=0;} for(int i=0;i<n;i++) { scanf("%I64d",&a); Add(a); } for(int i=0;i<m;i++) { scanf("%I64d",&b); Search(b); printf("%I64d\n",ans); } } int main() { // freopen("input.txt","r",stdin); freopen("data.txt","r",stdin); freopen("out1.txt","w",stdout); scanf("%d",&T); for(int i=1;i<=T;i++) { printf("Case #%d:\n",i); scanf("%d %d",&n,&m); input(); } return 0; }