题意

求出所有异或对的最大值

思路1

首先可以暴力

暴力代码

#include<iostream>
using namespace std;
int n,ma=0;
int a[100005];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            ma=max(ma,a[i]^a[j]);
        }
    }
    cout<<ma;
    return 0;
}

这也是非常逆天, $81$ 分这么高

思路2

使用字典树

思路解析(如何快速找到最大值)

将每一个数字转换为 $32$ 位二进制来构造字典树

对比 $1010$ 和 $1100$

哪个与 $1011$ 异或后的值最大

是不是 $1100$

为什么?

第一位都一样,没办法比

在第二位时 $1100$ 的 $1$ 和 $1011$ 的 $0$ 异或值( $1$ ^ $0$ )是最大的

然而在第二位时 $1010$ 的 $0$ 和 $1011$ 的 $0$ 异或值( $0$ ^ $0$ )是最小的

所以选择 $1100$

在这道题中可以对每个数字用这个方法就能在 $O(32)$ 的时间比较找出最大的值

思路解析(如何更简单的将数字转为 $32$ 位二进制)

首先想到的是通过的 $2$ 的次方得出二进制

但是可以通过 $STL$ 来便捷的得出二进制

$STL$ 容器 $bitset$ 介绍:

可以将数字转为二进制数组

注意的是,在写代码时是要通过从 i=31 到 i>=0 这样遍历数组

语法:

bitset<位数>变量名(转二进制的数字)

当然,详细的介绍可以上网搜

字典树代码

$100$ AC

#include<iostream>
#include<bitset>
#define N 3200005 
using namespace std;
int n,tot=0,ma=0;
int a[N];
int trie[N][5];
int word[N];
void insert(int sn,int id)//插入的代码
{
	bitset<64>s(sn);//32位二进制
	int u=0;
	for(int i=31;i>=0;i--)//从最大的位数开始找
	{
		bool x=s[i];
		if(!trie[u][x])
			trie[u][x]=++tot;
		u=trie[u][x];
	}
	word[u]=id;//记录以u节点为结尾的数字下标
}
void find(int sn)//找出这个数字对应的最大异或值
{
	bitset<64>s(sn);//32位二进制
	int u=0;
	int j=0;
	for(int i=31;i>=0;i--)//从最大的位数开始找
	{
		bool x=s[i];
		u=trie[u][x];
		if(trie[j][!x])//尽量取反
			j=trie[j][!x];
		else if(trie[j][x])//没办法取反
			j=trie[j][x];
	}
	ma=max(ma,a[word[u]]^a[word[j]]);//取max
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		insert(a[i],i);
	}
	for(int i=1;i<=n;i++)
	{
		find(a[i]);
	}
	cout<<ma;
	return 0;
}