题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=5536

题目：

Chip Factory

Time Limit: 18000/9000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Problem Description

John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, the factory produces n chips today, the i-th chip produced this day has a serial number si.
At the end of the day, he packages all the chips produced this day, and send it to wholesalers. More specially, he writes a checksum number on the package, this checksum is defined as below:

maxi,j,k(si+sj)⊕sk
which i,j,k are three different integers between 1 and n. And ⊕ is symbol of bitwise XOR.

Can you help John calculate the checksum number of today?

Input

The first line of input contains an integer T indicating the total number of test cases.

The first line of each test case is an integer n, indicating the number of chips produced today. The next line has n integers s1,s2,..,sn, separated with single space, indicating serial number of each chip.

1≤T≤1000
3≤n≤1000
0≤si≤10^9
There are at most 10 testcases with n>100

Output

For each test case, please output an integer indicating the checksum number in a line.

Sample Input

2

3

1 2 3

3

100 200 300

Sample Output

6 400

 

 解题思路：

两层for遍历寻找i和j（i≠j），问题转化为01字典树的经典问题，在一堆数里找一个数s[k],使得s[k]和(s[i]+s[j])的异或值最大，但是题目又要求k,i,j互不相同，所以在i，j一定找k时，需要在01字典树上“删除”s[i],s[j]。

但是并非真的的删除，exist[]记录每个节点在建01字典树时被访问的次数，当要删除s[i]时， 只需要把s[i]在树上的节点的exist值都-1，这样就实现了“删除”s[i]。后，+1 即恢复。

在树上遍历贪心寻找s[k]时，ch[u][v^1]节点不仅要在第一次建树时存在，而且要删除s[i]和s[j]之后也必须存在（exist值不为0）才能贪心的跳转到ch[u][v^1]去。

注：树上的一个节点在第一次建树的时候可能会被多次访问。

 

ac代码：

时间：近4s

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1005;// 8！=40320！！不是10000
const int max_base = 32;
ll val[32*maxn], a[maxn];
int ch[32*maxn][2], exist[32*maxn];
int tol = 0;
void init()
{
    tol = 1;
    ch[0][0] =  ch[1][0] = 0;
}
void insert(ll x)
{
    int u = 0;
    for(int i = max_base; i >= 0; i--)
    {
        int v = (x >> i & 1);
        if(!ch[u][v]) // 新建节点
        {
            ch[tol][1] = ch[tol][0] = 0;
            val[tol] = 0; //不是数值节点
            exist[tol] = 0;//当前要确定的节点编号tol
            ch[u][v] = tol++;
        }
        u = ch[u][v];
        exist[u]++;//可能会被访问多次
    }
    val[u] = x;
}
void update(ll x, int add)
{
    int u = 0;
    for(int i = max_base; i >= 0; i--)
    {
        int v = x >> i & 1;
        u = ch[u][v];
        exist[u] += add;
    }
}
ll query(ll x)
{
    int u = 0;
    for(int i = max_base; i >= 0; i--)
    {
        int v = x >> i & 1;
        if(ch[u][v^1] && exist[ch[u][v^1]]) u = ch[u][v^1]; // 贪心的找每位异或起来的1的节点, 且这个节点存在，可能其他数在该节点上有相应的值
        else u = ch[u][v];
    }
    return  x^val[u];
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        init();
        scanf("%d", &n);
        ll ans = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%lld", &a[i]);
            insert(a[i]);
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                ll x = a[i] + a[j];
                update(a[i], -1);
                update(a[j], -1);//在01字典树上'删除'这两个数
                ans = max(ans, query(x));
                update(a[i], 1);
                update(a[j], 1);//恢复
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}