2014百度之星第三题Xor Sum(字典树+异或运算)

Xor Sum

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)

Total Submission(s): 4445    Accepted Submission(s): 652

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

题解

本题数据量非常大,感觉直接暴力时间复杂度O(n*m)会超时。只是想到去年网赛有道题数据量也非常大直接暴力居然过了于是直接敲了敲,终于还是TLE了。

想到位操作运算符的通用思想,逐位处理,相应本题还是比較easy想到字典树的。Memory Limit: 132768/132768 K (Java/Others),提示能够尝试牺牲空间换取时间。直接字典树空间消耗为2^32,但本题数据相对此规模还是比較小的。一共n个数,总共32*n位。所以空间复杂度为O(n)。能够接受。先用原序列中的数按位建立字典树。然后将查找过程中用待询问数与0xffffffff异或XOR来在字典树上跑。终于找到的即为最大的。

如果按查询的XOR的某个分支不存在。则想还有一分支进行。这样答案可能变小,可是正确的。总的时间复杂度O(m*log(32))。常数能够不计。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXN=100000*32+100;
__int64 tree[MAXN][2];
__int64 node[MAXN];
__int64 tot;

void insert(__int64 a)
{
	__int64 j;
	int bit,dep=0;
	for(j=31;j>=0;j--)
	{
		bit=((0x1<<j)&a)?0x1:0x0;
		if(tree[dep][bit]==0)
		{
			tree[dep][bit]=tot++;
			memset(tree[tree[dep][bit]], 0, sizeof(tree[tree[dep][bit]]));
		}
		dep=tree[dep][bit];
	}
	node[dep]=a;
}

__int64 Solve(__int64 val)
{
	__int64 j,bit;
	int dep=0;
	for(j=31;j>=0;j--)
	{
		bit=((0x1<<j)&val)?0x0:0x1;
		if(tree[dep][bit])dep=tree[dep][bit];
		else dep=tree[dep][bit^1];
	}
	return node[dep];
}

int main()
{
	int cas;
	__int64 n,m,j,s,a;
	int tag=0;
	cin>>cas;
	while(cas--)
	{
		tot=1;
		scanf("%I64d%I64d",&n,&m);
		memset(tree[0],0,sizeof(tree[0]));
		while(n--)
		{
			scanf("%I64d",&a);

			insert(a);
		}
		printf("Case #%d:\n",++tag);
		while(m--)
		{
			scanf("%I64d",&s);
			printf("%I64d\n",Solve(s));
		}
	}
	return 0;
}
时间: 12-20

2014百度之星第三题Xor Sum(字典树+异或运算)的相关文章

2014百度之星第三题Xor Sum

Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 4445    Accepted Submission(s): 652 Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Ze

2014 百度之星第三题

Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 0    Accepted Submission(s): 0 Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包括了N个正整数,随后 Prometheus 将向 Zeus 发起

2014年百度之星资格赛第三题Xor Sum

Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包括了N个正整数,随后 Prometheus 将向 Zeus 发起M次询问,每次询问中包括一个正整数 S ,之后 Zeus 须要在集合其中找出一个正整数 K ,使得 K 与 S 的异或结果最大.Prometheus 为了让 Zeus 看到人类的伟大,随即允许 Zeus 能够向人类求助.你能证明人类的智慧么? Input 输入包括若干组測试数据,每组測试数据

2014百度之星资格赛第一题

Energy Conversion Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11867    Accepted Submission(s): 2861 Problem Description 魔法师百小度也有遇到难题的时候-- 现在,百小度正在一个古老的石门面前,石门上有一段古老的魔法文字,读懂这种魔法文字需要耗费大量的能量和大

2014百度之星资格赛第二题

Disk Schedule Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2560    Accepted Submission(s): 366 Problem Description 有很多从磁盘读取数据的需求,包括顺序读取.随机读取.为了提高效率,需要人为安排磁盘读取.然而,在现实中,这种做法很复杂.我们考虑一个相对简单的场景.

2014百度之星第四题Labyrinth

Labyrinth Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1804    Accepted Submission(s): 626 Problem Description 度度熊是一只喜欢探险的熊,一次偶然落进了一个m*n矩阵的迷宫,该迷宫只能从矩阵左上角第一个方格开始走,只有走到右上角的第一个格子才算走出迷宫,每一次只能走一格

HDU 4825 Xor Sum 字典树+位运算

点击打开链接 Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 291    Accepted Submission(s): 151 Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus

2014百度之星资格赛4题

因为都是中文题.题意就不写了. A.Energy Conversion 这题先推断一下能量能否添加,然后再依据添加这个公式去求出一个等比公式.就能够直接求出须要添加几次了 B.Disk Schedule 首先轨道转移和读取数据时间肯定是要花进去的,剩下就是看转的那部分时间,从0,0開始,回到0.0.中间经过n个点,转化为经典的双调欧几里得DP.就能够求出答案了 C.Xor Sum 从高位建字典树,然后贪心.尽量选择0,1不同的位置去放 D.Labyrinth 非经常见的动态规划,dp[i][j]

Xor Sum(字典树加贪心)

Xor Sum Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others) Total Submission(s): 457    Accepted Submission(s): 231 Problem Description Zeus 和 Prometheus 做了一个游戏,Prometheus 给 Zeus 一个集合,集合中包含了N个正整数,随后 Prometheus 将向 Zeu