HDU 5536 Chip Factory (暴力+01字典树)

<题目链接>

题目大意:

给定一个数字序列,让你从中找出三个不同的数,从而求出:$\max_{i,j,k} (s_i+s_j) \oplus s_k$的值。

解题分析:
先建好01字典树,然后枚举两个不同的数,从字典树中删除这两个数,然后进行匹配,找到能够使 $ (s_i+s_j) \oplus s_k$ 值最大的值。之后再将这两个数插入,进行下一轮询问。

#include <bits/stdc++.h>
using namespace std; #define clr(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int N = 1e3+;
int n,m,pos;
ll arr[N],nxt[N*][],val[N*],num[N*]; void init(){
pos=;clr(nxt,);clr(val,);clr(num,);
}
void Insert(ll x){
int now=;
for(int i=;i>=;i--){
int to=(x>>i)&;
if(!nxt[now][to])nxt[now][to]=++pos;
now=nxt[now][to];
num[now]++;
}
val[now]=x;
}
void del(int x){
int now=;
for(int i=;i>=;i--){
int to=(x>>i)&;
now=nxt[now][to];
num[now]--;
}
}
ll query(ll x){
int now=;
for(int i=;i>=;i--){
int to=(x>>i)&;
if(nxt[now][to^] && num[nxt[now][to^]])now=nxt[now][to^];
else now=nxt[now][to];
}
return x^val[now];
}
int main(){
int T;scanf("%d",&T);while(T--){
init();
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lld",&arr[i]),Insert(arr[i]);
ll mx=-;
for(int i=;i<n;i++){
for(int j=i+;j<=n;j++){
del(arr[i]);del(arr[j]); //因为三个数应该不同,所以先将这两个数删除
mx=max(mx,query(arr[i]+arr[j]));
Insert(arr[i]);Insert(arr[j]);
}
}
printf("%lld\n",mx);
}
}

2019-03-02

上一篇:CF908G Original Order


下一篇:解决JSP表单数据到Controller中乱码问题