首页 > 代码库 > 【JDFZOJ】最富有的人 Trie树+异或性质

【JDFZOJ】最富有的人 Trie树+异或性质

2024-11-27 02:31:39   203人阅读

#include <stdio.h>
int main()
{
	puts("转载请注明出处谢谢");
	puts("http://blog.csdn.net/vmurder/article/details/43446799");
}


题面：

最富有的人

Time Limit: 1 Sec  Memory Limit: 64 MB

Description

　　你经过了一段时间的打工，老板带你来到了他的私人金库。

　　在你的面前有n堆金子，老板要求你只能选择其中的两堆，而你的工资为这两堆金子价值的xor值，你想成为最富有的人，你就要做出最优的选择。

/*

　　名词解释：

　　　　xor运算，两个数的对应二进制位相同则答案的二进制该位为0，不同则为1，例如10的二进制表示为1010，5的二进制表示为101，15的二进制表示为1111，则10 xor 5 = 15，当然，xor运算满足交换律，即5 xor 10 = 15。

　　　　xor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。

　　　　xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即（a xor b) xor b = a。

　　　　xor运算可以用于简单的加密。比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19961008作为密钥。1314520 xor 19961008 = 19176040，我就把19176040告诉MM。MM再次计算19176040 xor 19961008的值，得到1314520，于是她就明白了我的企图。

*/

Input

第一行包含一个正整数t，表示有t组数据。
每组数据的第一行包含两个正整数n，表示有n堆金子；
第二行包含n个正整数，表示每堆金子的价值。

Output

对于每组数据用一行输出。
每行包含一个正整数，表示能获得的最大工资。

Sample Input

251 2 3 4 5101 2 3 4 5 6 7 8 9 10

Sample Output

715

HINT

数据范围：

t<=10 2<=n<=100000 每堆金子数<=2^31-1

题解：随便乱搞

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
#define LOGN 35
#define T 2
using namespace std;
struct Trie
{
	int son[N*LOGN][T],cnt;
	void init()
	{
		memset(son,0,sizeof son);
		cnt=0;
	}
	void insert(long long a)
	{
		int i,x=0,alp;
		for(i=31;i>=0;i--)
		{
			alp=(a>>i)&1;
			if(!son[x][alp])son[x][alp]=++cnt;
			x=son[x][alp];
		}
	}
	long long find(long long a)
	{
		int i,x=0,alp;
		long long ret=0;
		for(i=31;i>=0;i--)
		{
			alp=!((a>>i)&1);
			ret<<=1;
			if(son[x][alp])
			{
				x=son[x][alp];
				ret++;
			}
			else x=son[x][!alp];
		}
		return ret;
	}
}trie;
long long ans,x[N];
int n;
int main()
{
//	freopen("test.in","r",stdin);

	int i,j,k,g;
	scanf("%d",&g);
	while(g--)
	{
		trie.init(),ans=0;
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%lld",&x[i]),trie.insert(x[i]);
		for(i=1;i<=n;i++)ans=max(ans,trie.find(x[i]));
		printf("%lld\n",ans);
	}
	return 0;
}


【JDFZOJ】最富有的人 Trie树+异或性质


联系
我们