The XOR Largest Pair

The XOR Largest Pair

链接：https://ac.nowcoder.com/acm/problem/50993
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

在给定的N个整数$$A_1,A_2\dots A_N$$中选出两个进行xor运算，得到的结果最大是多少？

输入描述:

$$第一行一个整数N，第二行N个整数A_1\sim A_N$$

输出描述:

一个整数表示答案。

示例1

输入

3
1 2 3

输出

3

备注:

$$

$$

对于100%的数据:
$$

对于 100% 的数据: N leq 10^5,
0 leq Ai lt 2^{31}
。
$$
思路：01字典树模板题，技能点++，建立一颗01字典树，有点像huffman树，如果是求最小就一直找相同的最长前缀，求最大就是遇到0位就往1走，很巧妙

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],cnt;
struct trie{
	int nex[100005*32][2];
	void insert(int x)
	{
		int p=0;
		for(int i=30;i>=0;i--)
		{
			int k=x>>i&1;
			if(!nex[p][k])nex[p][k]=++cnt;
			p=nex[p][k];
		}
	}
	int  find(int x)
	{
		int res=0,p=0;
		for(int i=30;i>=0;i--)
		{
			int k=x>>i&1;
			if(nex[p][k^1])p=nex[p][k^1],res|=1<<i;
			else p=nex[p][k];
		}
		return res;
	}
}t;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		t.insert(a[i]);
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		ans=max(ans,t.find(a[i]));
	}
	cout<<ans<<endl;
	return 0;
}

最后

以上就是真实墨镜为你收集整理的The XOR Largest Pair的全部内容，希望文章能够帮你解决The XOR Largest Pair所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。