[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)}\bigoplus{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亚洲区长春站-重现赛（感谢东北师大）

Recommend

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

Solution

简述题意 :

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

\[{(si+sj)}\bigoplus{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;

}

巴特西