The XOR Largest Pair

题目链接：noi.ac# sycOJ LOJ

这道题是字典树的入门初学题。(因为对XOR不太熟系，卡了很久)

初步的思想就是将数字以二进制数保存在字典树里

对一个数\(x\)而言，我们用x>>i&1来表示他的二进制第i位

直接上代码

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
typedef long long ll;
ll tr[N*31][2],cnt[N*31],idx;
ll a[N];
void insert(ll x)
{
	ll p=0;
	for (ll i=30;i>=0;i--)
	{
		int u=x>>i&1;
		if (!tr[p][u]) tr[p][u]=++idx;
		p=tr[p][u];
	}
}
ll query(ll x)
{
	ll p=0,ans=0;
	for (ll i=30;i>=0;i--)
	{
		int u=x>>i&1;
		if (tr[p][!u])
		{
			p=tr[p][!u];  //这里一开始写的是p=tr[p][u]，但明显错了。思考了很久。
			ans=ans*2+1;
		}
		else
		{
			p=tr[p][u];
			ans=ans*2;
		}
	}
	return ans;
	
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	ll n;
	cin>>n;
	for (ll i=1;i<=n;i++)
	{
		cin>>a[i];
		insert(a[i]);
	}
	ll res=-INF;
	for (ll i=1;i<=n;i++)
	{
		res=max(res,query(a[i]));
	}
	cout<<res;
	

	return 0;

}