「一本通 2.3 例 2」The XOR Largest Pair

题目描述

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

输入输出格式

输入格式：

第一行一个整数 N。
第二行 N 个整数 $A_i$。

输出格式：

一个整数表示答案。

输入输出样例

输入样例#1：

5
2 9 5 7 0

输出样例#1：

14

提示信息

对于 $100$% 的数据，$1\le N\le 10^5$，$0\le A_i<2^{31}$

解法

#include <bits/stdc++.h>
using namespace std;
const int N=2e6,M=5e6;
int a[N],s[M][2],idx,res,n;
void insert(int x) {
	int t,p=0;
	for (int i=30;i>=0;i--) {
		t=x>>i&1;
		if (s[p][t]==0)
			s[p][t]=++idx;
		p=s[p][t];
	}
}
int ans (int x) {
	int t,p=0,l=0;
	for (int i=30;i>=0;i--) {
		t=x>>i&1;
		if (s[p][!t]) {
			l+=1<<i;
			p=s[p][!t];
		}
		else {
			p=s[p][t];
		}
	}
	return l;
}
int main(){
	cin >>n;
	for (int i=1;i<=n;i++) {
		cin >>a[i];
		insert(a[i]);
	}
	for (int i=1;i<=n;i++) {
		res=max(res,ans(a[i]));
	}
	cout <<res;
	return 0;
}