[HDU-5536] Chip Factory (01字典树)

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:

[max_{i,j,k}{(si+sj)}igoplus{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≤109
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

Source

2015ACM/ICPC亚洲区长春站-重现赛（感谢东北师大）

hujie | We have carefully selected several similar problems for you: 6297 6296 6295 6294 6293

Solution

简述题意 :
有 q 次询问,每次给你一个长度为 n 的序列,要你求出这个序列中

[{(si+sj)}igoplus{sk} ]

的最大值即可，其中 i != j != k;

此题就是一个带修改的 01字典树 的模板。
在考虑某一个数的时候要将它自己先暂时删去。
相对于常规模板,带修改的01字典树只需我们多加一个数组。

[num[maxn] ]

用于储存当值为当前这个节点的值的元素数量。
只有当一个节点的 num 不为 0 时,我们才能访问。

然后我们增加一个 Change 函数。
用于改变在字典树中的元素的 num。
基本遍历过程和插入以及查询类似。
但是到达元素这个节点时，我们进行的是修改 num 操作。

Change 函数代码如下:

void change(int a,int v) //分别为这个元素的值以及对它num的变化值.
{    
	int u=0;
    for(int i=32;i>=0;i--)
	{
        int c=((a>>i)&1);
        u=ch[u][c];
        num[u]+=d;
    }
}

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1008;

int ch[32*maxn][2];
ll val[32*maxn];
int num[32*maxn];
int sz;
ll b[maxn];

void init()
{
    memset(ch[0],0,sizeof(ch[0]));
	sz=1;
}

void insert(ll a){
    int u=0;
    for(int i=32;i>=0;i--)
	{
        int c=((a>>i)&1);
        if(!ch[u][c])
		{
            memset(ch[sz],0,sizeof(ch[sz]));
            val[sz]=0;
            num[sz]=0;
            ch[u][c]=sz++;
        }
        u=ch[u][c];
        num[u]++;
    }
    val[u]=a;
}
void update(ll a,int d)
{
    int u=0;
    for(int i=32;i>=0;i--)
	{
        int c=((a>>i)&1);
        u=ch[u][c];
        num[u]+=d;
    }
}
ll query(ll x)
{
    int u=0;
    for(int i=32;i>=0;i--)
	{
        int c=((x>>i)&1);
        if(ch[u][c^1]&&num[ch[u][c^1]]) 
		u=ch[u][c^1];
        else u=ch[u][c];
    }
    return x^val[u];
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);
        init();
        for(int i=1;i<=n;i++)
		{
            scanf("%lld",&b[i]);
            insert(b[i]);
        }
        ll ans=-1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
			{
                if(i==j) continue;
                update(b[i],-1);update(b[j],-1);
                ans=max(ans,query(b[i]+b[j]));
                update(b[i],1);update(b[j],1);
            }
        cout<<ans<<endl;
    }
    return 0;
}