题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4825
题意:给定一个含有若干整数的序列,m个询问,在序列中找到一个数字与询问的数字异或的值最大。
思路:异或一般想到用二进制的方法来做。这里我们建立一个字典树,把序列中每个数字以二进制展开插入字典树中,并在叶节点处存储这个数字的值,对于每个询问,我们也将数字展开,贪心的从高到低进行搜索,因为异或就是不进位的加法,如果我们能找到这个数字当前位的值^1的节点,那么我们就能把当前位异或为1就能保证最后的结果最大,如果找不到就顺着当前位的值找下去就可以了。
#pragma comment(linker, "/STACK:102400000,102400000") #include <map> #include <set> #include <stack> #include <queue> #include <cmath> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #define MOD 1e9+7 #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 using namespace std; typedef long long ll; const int maxn=100000+5; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); template<typename T> inline T read(T&x){ x=0;int _f=0;char ch=getchar(); while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x=_f?-x:x; } struct Trie{ int val; int next[2]; }tree[maxn*32]; int T,n,m,cnt; void Insert(int x); int Find(int x); int main(){ int cas=1; for (read(T);T;T--){ read(n),read(m); tree[0].val=0; memset(tree[0].next,0,sizeof(tree[0].next)); cnt=0; for (int i=1;i<=n;i++){ int x; read(x); Insert(x); } printf("Case #%d:\n",cas++); for (int i=1;i<=m;i++){ int x; read(x); printf("%d\n",Find(x)); } } return 0; } void Insert(int x){ int pos=0; for (int i=31;i>=0;i--){ int c=((x>>i)&1); if (!tree[pos].next[c]){ cnt++; tree[pos].next[c]=cnt; tree[cnt].val=0; memset(tree[cnt].next,0,sizeof(tree[cnt].next)); } pos=tree[pos].next[c]; } tree[pos].val=x; } int Find(int x){ int pos=0; for (int i=31;i>=0;i--){ int c=((x>>i)&1); if (!tree[pos].next[c^1]) pos=tree[pos].next[c]; else pos=tree[pos].next[c^1]; } return tree[pos].val; }