HDU 5536 Chip Factory （2015长春J题&&Trie树）

比赛的时候这道题想了好久，最后还是没想到正解，一直提醒队友不要暴力，暴力一定不过，最后看那么多人都过了，我们还没想到正解，于是就暴力了， n3 过了。。。

分析：把所有数2进制分解，建一颗Trie树，然后暴力 n2 找出所有 (i,j) 在Trie树里面招出 xor 最大值。

因为要保证 i,j,k 不相等，所以扫 (i,j) 的时候，不妨先删除 i,j 串，查询完了再插入。

trie树每一个节点维护一个 cnt 值，代表有多少个串经过这个节点，删除的时候不需要改变 ch[u][i] 值，只需要维护 cnt 值。（不是真正的删除）。

复杂度 o(n2logn) 。

下面是代码：

#include <bits/stdc++.h>
#define LL long long
#define FOR(i,x,y) for(int i = x;i < y;++ i)
#define IFOR(i,x,y) for(int i = x;i > y;-- i)

using namespace std;

const int maxn = 1010;

int ch[maxn*35][2],cnt[maxn*35],sz;

void Init(){
    memset(ch,0,sizeof(ch));
    memset(cnt,0,sizeof(cnt));
    sz = 0;
}

void Insert(int* str){
int u = 0;
    FOR(i,0,35){
if(!ch[u][str[i]]){
            ch[u][str[i]] = ++sz;
        }
        u = ch[u][str[i]];
        cnt[u] ++;
    }
}

void Delete(int* str){
int u = 0;
    FOR(i,0,35){
        u = ch[u][str[i]];
        cnt[u] --;
    }
}

LL calc(int* str){
    LL res = 0;
int u = 0;
    FOR(i,0,35){
if(ch[u][1^str[i]] && cnt[ch[u][1^str[i]]]){
            res |= (1LL<<(34-i));
            u = ch[u][1^str[i]];
        }
else{
            u = ch[u][str[i]];
        }
    }
return res;
}

int a[maxn],s[maxn][35],n;

void deal(){
    Init();
int str[35];
    FOR(i,0,n){
        scanf("%d",&a[i]);
int num = a[i];
        FOR(j,0,35){
str[j] = num%2;
            num >>= 1;
        }
        FOR(j,0,35) s[i][j] = str[34-j];
        Insert(s[i]);
    }
}

void work(){
int str[35];
int strr[35];
    LL ans = 0;
    FOR(i,0,n-1){
        Delete(s[i]);
        FOR(j,i+1,n){
            Delete(s[j]);
int num = a[i]+a[j];
            FOR(k,0,35){
str[k] = num%2;
                num >>= 1;
            }
            FOR(k,0,35) strr[k] = str[34-k];
            LL res = calc(strr);
            ans = max(ans,res);
            Insert(s[j]);
        }
        Insert(s[i]);
    }
    printf("%I64d\n",ans);
}

int main()
{
//freopen("test.in","r",stdin);
int T;  scanf("%d",&T);
while(T--){
        scanf("%d",&n);
        deal();
        work();
    }
return 0;
}