HDU 5536 Chip Factory (字典树——序列中查找最大异或和)

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5536
题意：在一组序列中找到三个数，使两个数的和异或第三个数的值最大。
思路：我们可以知道，字典树有一个经典应用，就是在一组序列中找到一对异或和最大的两个数。只要枚举一个数，然后贪心的在字典树中找每一位不同的数字就可以了。所以我们可以建一棵字典树，先(n^2)把除了第一个数以外的两两数字的和，插入到字典树中。然后枚举每一个数字，查询异或和最大的数字。在每一个数字查询完以后，插入当前数字与其他数字相关的和，然后删除下一个数字的相关的和。不断更新答案就能求出，记得在每次样例结束以后要清书，而且用memset貌似会TLE。
但是不知道为什么，我AC的时间8s多，有时候会TLE。所以根据题目描述，100以内的时候n^3暴力一下，其余用字典树，就能过了。虽然不知道别人这么快是怎么完成的，还是提供一下我的思路。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define calm (l+r)>>1
const int INF=2139062143;

const int maxn=1010;
int n,a[maxn];
struct trie{
int next[2];
int cnt;
}tree[34000000];
int vis;
void Insert(int x){
int a[32];
for(int i=31;i>=0;i--){
        a[i]=x%2;
        x/=2;
    }
int rt=0;
    tree[rt].cnt++;
for(int i=0;i<32;i++){
int t=a[i];
if(!tree[rt].next[t]){
            rt=tree[rt].next[t]=++vis;
        }
else rt=tree[rt].next[t];
        tree[rt].cnt++;
    }
}
int solve(int x){
int a[32];
for(int i=31;i>=0;i--){
        a[i]=x%2;
        x/=2;
    }
int ans=0,rt=0;
for(int i=0;i<32;i++){
int t=a[i];
if(tree[rt].next[1-t]&&tree[tree[rt].next[1-t]].cnt){
            rt=tree[rt].next[1-t];
if(1-t)ans+=(1-t)*(1<<(31-i));
        }
else {
            rt=tree[rt].next[t];
if(t)ans+=t*(1<<(31-i));
        }
    }
return ans;
}
void Delete(int x){
int a[32];
for(int i=31;i>=0;i--){
        a[i]=x%2;
        x/=2;
    }
int rt=0;
    tree[rt].cnt--;
for(int i=0;i<32;i++){
int t=a[i];
        rt=tree[rt].next[t];
        tree[rt].cnt--;
    }
}
void Clear(int rt){
if(tree[rt].cnt){
if(tree[rt].next[0])Clear(tree[rt].next[0]);
if(tree[rt].next[1])Clear(tree[rt].next[1]);
        tree[rt].next[0]=tree[rt].next[1]=tree[rt].cnt=0;
    }
}
int main(){
//freopen("D://input.txt","r",stdin);
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);
        vis=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
        }
if(n<=100){
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)if(i!=j){
for(int k=1;k<=n;k++)if(i!=k&&j!=k){
                        ans=max(ans,(a[i]+a[j])^a[k]);
                    }
                }
            }
printf("%d\n",ans);
continue;
        }
for(int i=2;i<=n;i++){
for(int j=i+1;j<=n;j++){
                Insert(a[i]+a[j]);
            }
        }
int ans=0;
for(int i=1;i<=n;i++){
            ans=max(ans,solve(a[i])^a[i]);
for(int j=1;j<=n;j++){
if(i!=j&&j!=i+1)Insert(a[i]+a[j]);
            }
for(int j=1;j<=n;j++){
if(i<n&&i!=j&&i+1!=j)Delete(a[i+1]+a[j]);
            }
        }
printf("%d\n",ans);
        Clear(0);
    }
return 0;
}