题意

任选两个数异或，求最大值。

思路

异或看的是二进制，那我们就看看二进制有什么规律。

要求异或出来的值最大，就要尽量让每位二进制相反。

是否想到了字典树？

在字典树插入时找与其相反的的数，也就是分两路遍历。一边是插入要插入的数，另一边是查找相反的数。然后异或，存进 $mx$。

科普：这里的字典树是 01 字典树，也就是二叉的字典树。

代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long ul;
const int N = 1e5 * 31 + 5;

ul mx;

int trie[N][2],word[N],tot;
void insert(string s){
    string t = "";
    int u = 0,v = 0;
    for (int i = 0;i < s.size();i++){
        bool c = s[i] - '0';
        if (!trie[u][c])    trie[u][c] = ++tot;
        u = trie[u][c];
        if (trie[v][!c])    t += (!c) + '0',v = trie[v][!c];
        else    t += c + '0',v = trie[v][c];
    }
    word[u]++;
    bitset<31> a(s),b(t);
//	cout << a << ' ' << b << ' ' << (a ^ b) << '\n';
    mx = max(mx,(a ^ b).to_ulong());
}

int main(int argc, char **argv){
    int n;
    cin >> n;
    for (int i = 0;i < n;i++){
        int x;
        cin >> x;
        bitset<31> b(x);
        insert(b.to_string());
    }
    cout << mx;
    return 0;
}

题意

求出所有异或对的最大值

思路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;
}

因为异或的定义是不同为1相同为0，所以要取得最大的异或值，对应的数的二进制每一位都跟原数不同。

但是不一定都是最理想状态，故在无法确保数位不同时选择相同的即可

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005]={};//输入的序列 
int nxt[10000005][2]={}/*二进制只需要0和1*/,cnt=0; 
int mx=-1;//存最大值 
void insert(int x){
	int p=0;
	for(int i=31;i>=0;i--){
		int c=(x>>i)&1;//取当前二进制位 
		if(!nxt[p][c]) nxt[p][c]=++cnt;
		p=nxt[p][c];
	}
}//建字典树 
int find(int x){
	int p=0;
	int ans=0;//存最大异或的数 
	for(int i=31;i>=0;i--){
		int c=(x>>i)&1;//取当前二进制位
		ans<<=1;
		if(nxt[p][(c==1?0:1)]) ans+=(c==1?0:1),p=nxt[p][(c==1?0:1)];
		else if(nxt[p][c]) ans+=(c==1?1:0),p=nxt[p][c];
		//分类讨论即可 
	}
	return ans;
}
signed main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		insert(a[i]);
	}
	for(int i=0;i<n;i++) mx=max(mx,a[i]^find(a[i]));//枚举最大值 
	cout<<mx<<"\n";
	return 0;
}