The XOR Largest Pair

时间限制: 1 Sec  内存限制: 128 MB

题目描述

在给定的N个整数A1，A2……AN中选出两个进行xor运算，得到的结果最大是多少？

 

输入

第一行一个整数N，第二行N个整数A1～AN。

 

输出

一个整数表示答案。

 

样例输入

复制样例数据

3
1 2 3

样例输出

3

 

提示

对于100%的数据: N<=10^5, 0<=Ai<2^31。

二进制转换建字典树，然后查一下就行了，当查到1的时候看有没有0，有的话异或肯定数会变大，并且深度设为31，不足31位的在前面补0。。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int c[3100005][3];//注意这边是深度位31，但是有10000个数，所以开3100005
int n, a[100005], tot;

void insert(int x){
	int p = 0;
	for (int i = 30; i >= 0; i--){
		int t = (x >> i) & 1;
		if(!c[p][t]) c[p][t] = ++tot;
		p = c[p][t];
	}
}

int solve(int x){
	int p = 0, ans = 0;
	for (int i = 30; i >= 0; i--){
		int t = (x >> i) & 1;
		if(c[p][t ^ 1]) p = c[p][t ^ 1], ans = (ans << 1) | 1;
		else p = c[p][t], ans <<= 1;
	}
	return ans;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		insert(a[i]);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		ans = max(ans, solve(a[i]));
	}
	printf("%d\n", ans);

	return 0;
}
/**/