HDU - 5536 Chip Factory（带删除操作01字典树）

链接：HDU - 5536 Chip Factory

题意：

给出$n(3\le n\le 1000)$个非负整数$s_1,s_2,?,s_n$，求最大的$(s_i+s_j)?s_k$，其中$i,j,k$互不相同且$1\le i,j,k\le n$。

分析：

由于$n$只有$1000$，所以我们可以暴力枚举$i,j$，然后在除$s_i,s_j$以外元素构成的01字典树中找到异或最大的$s_k$。

每次都去建树肯定不行，所以就要加一个数组$num[u]$来实现带删除操作的01字典树，先把$s_1$~$s_n$都放入01字典树，枚举了$i,j$就删除$s_i,s_j$，询问最大异或值后再将$s_i,s_j$恢复即可。

以下代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=1000+50;
const int max_base=31;
int n;
int ch[31*maxn][2],num[31*maxn],tot;
LL s[maxn],val[31*maxn];
void init()
{
    tot=1;ch[0][0]=ch[0][1]=0;val[0]=0;num[0]=0;
}
void ins(LL x)
{
    int u=0;num[u]++;for(LL i=max_base;i>=0;i--){
    LL c=(x>>i)&1LL;if(!ch[u][c]){
    ch[tot][0]=ch[tot][1]=0;val[tot]=0;num[tot]=0;ch[u][c]=tot++;}u=ch[u][c];num[u]++;}val[u]=x;
}
void updata(LL x,int op)   //op=-1：删除x
{
                              //op=1：恢复之前被删除的xint u=0;num[u]+=op;for(LL i=max_base;i>=0;i--){
    LL c=(x>>i)&1LL;u=ch[u][c];num[u]+=op;}
}
LL query(LL x)
{
    int u=0;for(LL i=max_base;i>=0;i--){
    LL c=(x>>i)&1LL;if(ch[u][c^1]&&num[ch[u][c^1]])u=ch[u][c^1];elseu=ch[u][c];}return x^val[u];
}
int main()
{
    int T;scanf("%d",&T);while(T--){
    init();scanf("%d",&n);for(int i=1;i<=n;i++){
    scanf("%d",&s[i]);ins(s[i]);}LL ans=0;for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
    LL x=s[i]+s[j];updata(s[i],-1);updata(s[j],-1);ans=max(ans,query(x));updata(s[i],1);updata(s[j],1);}}printf("%lld\n",ans);}return 0;
}