【LOJ 10050】The XOR Largest Pair

【题目】

传送门

题目描述:

在给定的 n nn个整数 a 1 a_1a1a 2 a_2a2……a n a_nan 中选出两个进行 x o r xorxor 运算,得到的结果最大是多少?

输入格式:

第一行一个整数 n nn,第二行 n nn 个整数 a 1 a_1a1a n a_nan

输出格式:

一个整数表示答案。

样例数据:

输入
3
1 2 3

输出
3

数据范围与约定:

对于 100% 的数据:n nn1 0 5 10^51050 00a i a_iai < 2 31 2^{31}231

【分析】

首先说一下异或吧,对于异或,是先把要进行计算的数转换成二进制数,然后按位比较,相同为 0 00,不同为 1 11

为了使最后的结果最大,我们就尽量想让最后答案的两个数中各个位上的数不同,并且尽量让答案的高位为 1 11(想想 1000 10001000 肯定比 0111 01110111 优)

这个时候我们神奇的Trie树就闪亮登场了

我们对每个数按照二进制位来建立 t r i e trietrie 树;建完之后,枚举每个数,在 t r i e trietrie 树上跑,每次都尽量跑相反的路(就是如果当前为 1 11 就尽量跑 0 00,当前为 0 00 就尽量跑 1 11),如果不能跑最相反的就只能跑相同的

在代码中我是先找出在原序列中与 a i a_iai 异或值最大的那个数,还需要再异或一下才是答案(当然直接找答案也是可行的)

最后对每个答案取最大值就可以了


【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
using namespace std;
int t,a[N];
struct Trie
{
	int son[2];
}tree[N<<5];
void build(int x)
{
	int i,k,p=0;
	for(i=30;~i;--i)
	{
		k=(x>>i&1)?1:0;
		if(tree[p].son[k]==0)
		  tree[p].son[k]=++t;
		p=tree[p].son[k];
	}
}
int find(int x)
{
	int i,k,s,p=0,ans=0;
	for(i=30;~i;--i)
	{
		k=(x>>i&1)?0:1;
		s=(tree[p].son[k])?k:k^1;
		p=tree[p].son[s];
		if(s)  ans|=(1<<i);
	}
	return ans;
}
int main()
{
	int n,i,x,Max=0;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		build(a[i]);
	}
	for(i=1;i<=n;++i)
	  Max=max(Max,a[i]^find(a[i]));
	printf("%d",Max);
	return 0;
}

版权声明:本文为forever_dreams原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。