HDU5536 01字典树求模板

傷城~ 2022-05-09 05:18 181阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    struct Tire{
        int nxt[N][2], cnt[N], ed[N];
        int L, root;
        void init(){
            L=root=0;
            nxt[root][0]=nxt[root][1]=-1;
            ed[root]=0;
            cnt[root]=0;
        }
    
        int newnode(){
            ++L;
            cnt[L]=0;
            nxt[L][0]=nxt[L][1]=-1;
            ed[L]=0;
            return L;
        }
    
        void _insert(int x){
            int now=root;
            cnt[now]++;
            for(int i=31; i>=0; i--){
                bool to=x&(1<<i);
    
                if(nxt[now][to]==-1)
                    nxt[now][to]=newnode();
                now=nxt[now][to];
                cnt[now]++;
            }
    
            ed[now]=x;
        }
    
        void del(int x){
            int now=root;
            cnt[now]--;
            for(int i=31; i>=0; i--){
                bool to=x&(1<<i);
                now=nxt[now][to];
                cnt[now]--;
            }
        }
    
        int query(int x){
            int now=root;
    
            for(int i=31; i>=0; i--){
                bool to=x&(1<<i);
    
                now=(nxt[now][to^1]==-1 || cnt[nxt[now][to^1]]==0)?nxt[now][to]:nxt[now][to^1];
    
            }
    
            return x^ed[now];
        }
    }Tr;
    int a[N];
    
    int main(){
        int T, n;
        scanf("%d", &T);
        while(T--){
            Tr.init();
           
            scanf("%d", &n);
            for(int i=1; i<=n; i++)
                scanf("%d",  a+i), Tr._insert(a[i]);
            int mx=-1;
            for(int i=1; i<=n; i++){
                for(int j=i+1; j<=n; j++){
                    Tr.del(a[i]);
                    Tr.del(a[j]);
    
                    int t=a[i]+a[j];
                    mx=max(mx, Tr.query(t));
                   
                    Tr._insert(a[i]);
                    Tr._insert(a[j]);
                }
            }
            printf("%d\n", mx);
        }
        return 0;
    }