Chip Factory

Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 6277 Accepted Submission(s): 2847

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≤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亚洲区长春站-重现赛（感谢东北师大）

实现代码；

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 1e3+;

int tot;

int ch[*M][],vis[*M];

ll val[*M],a[M];

void init(){

    memset(vis,,sizeof(vis));

    tot = ;

    ch[][] = ch[][] = ;

}

void ins(ll x){

    int u = ;

    for(int i = ;i >= ;i --){

        int v = (x>>i)&;

        if(!ch[u][v]){

            ch[tot][] = ch[tot][] = ;

            val[tot] = ;

            vis[tot] = ;

            ch[u][v] = tot++;

        }

        u = ch[u][v];

        vis[u]++;

    }

    val[u] = x;

}

void update(ll x,int c){

    int u = ;

    for(int i = ;i >= ;i --){

        int v = (x>>i)&;

        u = ch[u][v];

        vis[u] += c;

    }

}

ll query(ll x){

    int u = ;

    for(int i = ;i >= ;i --){

        int v = (x>>i)&;

        if(ch[u][v^]&&vis[ch[u][v^]]) u = ch[u][v^];

        else u = ch[u][v];

    }

    return x^val[u];

}

int main()

{

    ios::sync_with_stdio();

    cin.tie(); cout.tie();

    int t,n,m;

    cin>>t;

    while(t--){

        cin>>n;

        ll mx = ;

        init();

        for(int i = ;i <= n;i ++)

            cin>>a[i],ins(a[i]);

        for(int i = ;i <= n;i ++){

            for(int j = i+;j <= n;j ++){

                update(a[i],-); update(a[j],-);

                mx = max(mx,query(a[i]+a[j]));

                update(a[i],); update(a[j],);

            }

        }

        cout<<mx<<endl;

    }

}

巴特西

hdu 5536 Chip Factory (01 Trie)

Chip Factory

最新文章

热门文章