首页 > 代码库 > 百度之星2014资格赛 1003 - Xor Sum
百度之星2014资格赛 1003 - Xor Sum
先上代码:
Xor Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 7837 Accepted Submission(s): 3350
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。
输入的第一行是一个整数T(T < 10),表示共有T组数据。
每组数据的第一行输入两个正整数N,M(<1=N,M<=100000),接下来一行,包含N个正整数,代表 Zeus 的获得的集合,之后M行,每行一个正整数S,代表 Prometheus 询问的正整数。所有正整数均不超过2^32。
Output
对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。
对于每个询问,输出一个正整数K,使得K与S异或值最大。
对于每个询问,输出一个正整数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
中文题意不解释:思路,给定的集合里面的串是不会变的,所以可以开一棵Trie树来保存集合里面的所有数,每个数在Trie树里面转化成一个32位的串,然后将查询的串根Trie数里面的串匹配,匹配原则是这样的:如果同一个位置有存在相异的位,那么就转向相异的位的方向(因为异或是同零异一),如果不存在相异的位,那就只好走相同的位的方向了。这里可以分析得出一定存在路径是从头走到结尾的,因为这里每一个数都被扩展成32位,所以一定可以匹配到。
提交有点坑→_→,当时交上去都是WA和RE,赛后Rejudge有几次的提交过了,据说是卡输出,如果得到的结果用一个中间变量来保存的话会WA,如果直接输出结果的话才AC。目测赛后又改了,所以过了。
上代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <bitset> 5 #define NOT(x) (x == 1 ? 0 : 1) 6 #define MAX 3200002 7 #define LL long long 8 using namespace std; 9 10 typedef bitset<32> bs; 11 int s[MAX][2],tot; 12 13 void reset(){ 14 memset(s[0],0,sizeof(s[0])); 15 tot=1; 16 } 17 18 void insert(bs a){ 19 int j=0; 20 for(int i=31;i>=0;i--){ 21 int u = a[i]; 22 if(!s[j][u]){ 23 memset(s[tot],0,sizeof(s[tot])); 24 s[j][u] = tot++; 25 } 26 j = s[j][u]; 27 } 28 } 29 30 LL check(bs a){ 31 LL r=0; 32 int j=0; 33 for(int i=31;i>=0;i--){ 34 int u = a[i]; 35 r<<=1; 36 if(s[j][NOT(u)]){ 37 r += NOT(u); 38 j = s[j][NOT(u)]; 39 }else if(s[j][u]){ 40 r +=u; 41 j = s[j][u]; 42 } 43 44 } 45 return r; 46 } 47 48 int main() 49 { 50 LL t,n,m,a; 51 LL r; 52 //freopen("data.txt","r",stdin); 53 scanf("%I64d",&t); 54 for(int z=1;z<=t;z++){ 55 printf("Case #%d:\n",z); 56 scanf("%I64d %I64d",&n,&m); 57 reset(); 58 for(int i=0;i<n;i++){ 59 scanf("%I64d",&a); 60 bs e(a); 61 insert(e); 62 } 63 for(int i=0;i<m;i++){ 64 scanf("%I64d",&a); 65 bs e(a); 66 r=check(e); 67 printf("%I64d\n",r); 68 } 69 } 70 return 0; 71 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。