hdu5536 Chip Factory 字典树+暴力 处理异或最大 令X=(a[i]+a[j])^a[k]， i，j，k都不同。求最大的X。

/**
题目：hdu5536 Chip Factory
链接：http://acm.hdu.edu.cn/showproblem.php?pid=5536
题意：给定n个数，令X=(a[i]+a[j])^a[k]， i，j，k都不同。求最大的X。

思路：字典树，由于转化为二进制最大是32位。将所有数转化为二进制，不足32位补0.
然后逆序插入字典树（逆序是为了查询的时候，保证先找最大的位，这样结果才是最大的）。
枚举i，j。从字典树删除i，j。然后在字典树找k。计算结果。然后把i，j的数重新插入。


*/


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxnode = 3e4+10;///最多可能有多少个节点
const int maxn = 1e3+100;
const int sigma_size = 2;///0或者1
int ch[maxnode][sigma_size];///由于很大，所以结构体内部放不下。要放在外面。
int a[maxn];
int save[32];
int z;
struct Trie{
    int val[maxnode];
    int sz;
    int idx(char c){return c-'a';}

    void insert(int *s)
    {
        int u = 0;
        z--;
        while(z>=0){
            int c = s[z];
            if(!ch[u][c]){
                memset(ch[sz], 0, sizeof ch[sz]);
                val[sz] = 0;
                ch[u][c] = sz++;
            }
            u = ch[u][c];
            val[u]++;
            z--;
        }
    }
    void del(int *s)
    {
        int u = 0;
        z--;
        while(z>=0){
            int c = s[z];
            u = ch[u][c];
            val[u]--;
            z--;
        }
    }

    LL query(int *s)
    {
        int u = 0;
        LL ans = 0;
        z--;
        while(z>=0){
            int c = s[z];
            if(ch[u][!c]&&val[ch[u][!c]]){///因为删除数字之后，ch[u][!c]没有处理，所以要通过val来判断是否还存在。
                ans = ans*2+1;
                u = ch[u][!c];
            }else
            {
                ans = ans*2;
                u = ch[u][c];
            }
            z--;
        }
        return ans;
    }
};
void getSave(int n)
{
    z = 0;
    while(n){
        save[z++] = n%2;
        n /= 2;
    }
    while(z<32){  ///存了32个数。
        save[z++] = 0;
    }
}
int main()
{
    int T, n;
    Trie trie;
    cin>>T;
    while(T--)
    {
        scanf("%d",&n);
        trie.sz = 1;
        memset(ch[0], 0, sizeof ch[0]);
        for(int i = 0; i < n; i++){
            scanf("%d",&a[i]);
            getSave(a[i]);
            trie.insert(save);
        }
        LL ans = 0;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                getSave(a[i]);
                trie.del(save);
                getSave(a[j]);
                trie.del(save);
                getSave(a[i]+a[j]);
                ans = max(ans,trie.query(save));
                getSave(a[i]);
                trie.insert(save);
                getSave(a[j]);
                trie.insert(save);
            }
        }
        printf("%lld
",ans);
    }
    return 0;
}