有一个数组,让你选取三个数,使其中两个数相加异或上另外一个数值最大。
很明显的异或最大要用01字典树,问题是要选取三个数。我们可以提前把所有的数字插入到01字典树上,每次枚举其中两个数时,先在字典树上面删除这两个数,然后再查询。问题又来了,我们怎么删除了,因为我们用的是公共前缀,所以我们可以对01字典树上的边进行计数,每次插入 +1,删除 -1,如此就可以完成删除操作了。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 7; // 插入字符串个数
typedef long long ll;
const ll inf = 1e5;
int ch[maxn * 32][2], sz; // 边
ll val[maxn * 32]; // 点
ll a[maxn], num[maxn * 32]; // num 记录每条边的使用次数
void init() // 初始化
{
sz = 1; // 根结点
memset(ch, 0, sizeof(ch));
memset(num, 0, sizeof(num));
}
void insert(ll x) // 插入
{
int u = 0;
for(int i = 32; i >= 0; i--) {
int v = (x >> i) & 1;
if(ch[u][v]) num[ch[u][v]] ++; // 如果已经有了 边的访问次数+1
if(!ch[u][v]) {
ch[u][v] = sz++;
num[ch[u][v]] ++;
val[ch[u][v]] = 0;
}
u = ch[u][v];
}
val[u] = x;
}
void delete1(ll x) // 删除
{
int u = 0;
for(int i = 32; i >= 0; i--) {
int v = (x >> i) & 1;
num[ch[u][v]]--; // 只需要把走的边的次数-1
u = ch[u][v];
}
}
ll query(ll x) // 查询
{
int u = 0;
for(int i = 32; i >= 0; i--) {
int v = (x >> i) & 1;
if(ch[u][v^1] && num[ch[u][v^1]] > 0) u = ch[u][v^1]; // 贪心选择不同的
else u = ch[u][v];
}
return val[u];
}
int main()
{
int t, n;
scanf("%d", &t);
while(t--) {
init();
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
insert(a[i]);
}
ll maxx = -inf;
int x, y;
for(int i = 0; i < n; i++) {
delete1(a[i]);
for(int j = i + 1; j < n; j++) {
delete1(a[j]);
ll ans = query(a[i] + a[j]);
if((ans ^ (a[i] + a[j])) > maxx) maxx = (ans ^ (a[i] + a[j]));
insert(a[j]);
}
insert(a[i]);
}
printf("%lld\n", maxx);
}
return 0;
}