首页 > 代码库 > 2014年百度之星资格赛第三题Xor Sum
2014年百度之星资格赛第三题Xor Sum
Problem Description
Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包括了N个正整数,随后 Prometheus 将向 Zeus 发起M次询问,每次询问中包括一个正整数 S ,之后 Zeus 须要在集合其中找出一个正整数 K ,使得 K 与 S 的异或结果最大。Prometheus 为了让 Zeus 看到人类的伟大,随即允许 Zeus 能够向人类求助。你能证明人类的智慧么?
Input
输入包括若干组測试数据,每组測试数据包括若干行。
输入的第一行是一个整数T(T< 10),表示共同拥有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包括N个正整数,代表Zeus 的获得的集合,之后M行,每行一个正整数S,代表Prometheus 询问的正整数。全部正整数均不超过2^32。
Output
对于每组数据,首先须要输出单独一行”Case #?:”,当中问号处应填入当前的数据组数,组数从1開始计算。
对于每一个询问,输出一个正整数K,使得K与S异或值最大。
Sample Input
2
3 2
3 4 5
1
5
4 1
4 6 5 6
3
Sample Output
Case #1:
4
3
Case #2:
4
这道题是用字典树写的。字典树就就两个字符0和1。将n个数所有按二进制从高位到低位存入字典树中。对于S,每次从最高位找起,去找与自己当前位置相反的树枝,假设该树枝没有存数,再去找同样的树枝。这样最后找到的那个数就一定是异或之后最大的数了。
#include <stdio.h> #include <string.h> #define NODE 3400010 #define N 100010 int n ,m; __int64 v[N]; __int64 node; __int64 next[NODE][2]; __int64 end[NODE]; void add(int cur,int k) { memset(next[node],0,sizeof(next[node])); end[node] = 0; next[cur][k] = node++; } __int64 cal(__int64 x) { int i,k,cur=0; for(i = 32;i >= 0;i--) { k = ( (1LL<<i)&x ) ? 0 : 1; if(next[cur][k]) { cur = next[cur][k]; } else { cur = next[cur][1-k]; } } return (x^end[cur]); } int main() { int cur ,k ,t; __int64 x; __int64 ans; scanf("%d",&t); for(int r = 1;r<=t;r++) { printf("Case #%d:\n",r); scanf("%d%d",&n,&m); node = 1; memset(next[0],0,sizeof(next[0])); for(int i = 0;i < n;i++) { scanf("%I64d",&x); v[i] = x; cur = 0; for(int j = 32;j >= 0;j--) { k = ( (1LL<<j)&x ) ? 1 : 0; if(next[cur][k]==0) { add(cur,k); } cur = next[cur][k]; } end[cur] = x; } for(int i = 0;i < m;i++) { scanf("%I64d",&x); ans = cal(x); printf("%I64d\n",ans^x); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。