Description
给 n 个数 a[1] ~ a[n],求 (a[i] + a[j]) ⊕ a[k] 的最大值,其中 i, j, k 为互不相同的序号,“⊕”表示按位异或。
Input
多组数据,每组数据第一行一个 n ,第二行 n 个正整数 a[i]。
其中 3 <= n <= 2000, 0 <= a[i] <= 10^9。
Output
每组数据输出最大的结果。
Sample Input
3
3 1 2
5
1 7 6 8 9
Sample Output
6
24
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
const int maxn = 2e3 + 10;
int a[maxn << 5 | 1], n;
struct Node
{
int cnt;
int nex[2];
void Init() {nex[0] = nex[1] = -1; cnt = 0;}
};
Node trie[maxn << 5];
int tp;
void Insert(int x)
{
int now = 0;
for(int i = 30; i >= 0; i --)
{
int ith1 = x >> i & 1;
if(trie[now].nex[ith1] == -1)
{
trie[tp].Init();
trie[now].nex[ith1] = tp ++;
}
trie[now].cnt ++;
now = trie[now].nex[ith1];
}
trie[now].cnt ++;
}
int Find(int x, int rev=0)
{
int now = 0, tmpx = 0;
for(int i = 30; i >= 0; i --)
{
int ith1 = (x >> i & 1) ^ rev;
if(rev && (trie[now].nex[ith1] == -1 || !trie[trie[now].nex[ith1]].cnt)) ith1 ^= 1;
if(trie[now].cnt == 0 || trie[now].nex[ith1] == -1) return -1;
now = trie[now].nex[ith1];
tmpx |= ith1 << i;
}
return trie[now].cnt > 0 ? tmpx : -1;
}
void Delete(int x)
{
int now = 0;
for(int i = 30; i >= 0; i --)
{
int ith1 = x >> i & 1;
trie[now].cnt --;
now = trie[now].nex[ith1];
}
trie[now].cnt --;
}
int main()
{
while(scanf("%d", &n) != EOF)
{
trie[0].Init();
tp = 1;
for(int i = 0; i < n; i ++)
scanf("%d", &a[i]), Insert(a[i]);
int ans = 0;
for(int i = 0; i < n; i ++)
{
Delete(a[i]);
for(int j = i + 1; j < n; j ++)
{
Delete(a[j]);
ans = std::max(ans, Find(a[i] + a[j], 1) ^ (a[i] + a[j]));
Insert(a[j]);
}
Insert(a[i]);
}
printf("%d\n", ans);
}
return 0;
}