HDU – 5536 Chip Factory（带删除的0-1字典树）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<cstdlib>
//#include<bits/stdc++.h>
using namespace std;
#define scan(n) scanf("%d",&n)
#define scand(n) scanf("%lf",&n)
#define ll long long
const int maxn = 1e3+10;
int Base[40];
int trie[maxn*40][2], tot;
int endd[maxn*40];


void dele(){
    int p=0;
    for(int i=1;i<=32;++i){
        int ch = Base[i];
        p = trie[p][ch];
        --endd[p];
    }
}

void into_base(int x) {
    int cnt=33;
    memset(Base,0,sizeof(Base));
    while(x) {
        Base[--cnt]=x%2;
        x/=2;
    }
}

void insertt() {
    int p=0;
    for(int i=1;i<=32;i++) {
        int ch=Base[i];
        if(trie[p][ch]==0)trie[p][ch]=++tot;
        p=trie[p][ch];
        endd[p]++;

    }
}
int searchh() {
    int p=0;
    int cnt=0;
    for(int i=1;i<=32;i++) {
        cnt*=2;
        int ch=Base[i];
        if(trie[p][!ch]!=0&&endd[trie[p][!ch]]>0) {
            ch=!ch;
            cnt++;
        }
        p=trie[p][ch];
    }
    return cnt;
}
int a[maxn];

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        memset(trie,0,sizeof(trie));
        memset(endd,0,sizeof(endd));
        tot = 0;
        int n;
        scanf("%d", &n);
        int T=0;
        int ans = 0;
        for(int i=1;i<=n;++i){
            scanf("%d", &a[i]);
            into_base(a[i]);
            insertt();
        }
//        int m;
//        scanf("%d", &m);
//        for(int i=1;i<=n;++i){
//            int x;
//            scanf("%d", &x);
//            into_base(x);
//
//            cout<<searchh()<<endl;
//        }
        for(int i=1;i<=n;++i){
            into_base(a[i]);
            dele();
            for(int j=i+1;j<=n;++j){
                into_base(a[j]);
                dele();
                into_base(a[i]+a[j]);
                ans = max(ans,searchh());
                into_base(a[j]);
                insertt();
            }
            into_base(a[i]);
            insertt();
        }
        printf("%d\n", ans);
    }

    return 0;
}