Chip Factory

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5536

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?

Under two situations the player could score one point.

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

HINT

题意

给你100组test，然后每组数据有1000个数，然后让你求(ai+aj)^ak的最大值，i!=j!=k

题解：

比较裸的字典树，写一个删除和添加操作就好了

代码

#include
     
      #include
      
       #include
       
        using namespace std;const int maxn = 1000 + 10;const int maxnode = 100000 + 10;int a[maxn];int ch[maxnode][2];int val[maxnode];int sz;void init(){    sz=1;    memset(ch[0],0,sizeof(ch[0]));    memset(val,0,sizeof(val));}void add(int x,int v){    int p = 0;    for(int i=31;i>=0;i--)    {        int id = (x>>i)&1;        if(ch[p][id]==0)        {            memset(ch[sz],0,sizeof(ch[sz]));            val[sz]=0;            ch[p][id]=sz++;        }        p = ch[p][id];        val[p]+=v;    }}int match(int x){    int ans = 0,u = 0;    x = ~x;    for(int i=31;i>=0;i--)    {        ans*=2;        int id = (x>>i)&1;        if(ch[u][id]&&val[ch[u][id]])        {            ans++;            u = ch[u][id];        }        else            u = ch[u][1-id];    }    return ans;}int main(){    int t;scanf("%d",&t);    while(t--)    {        init();        int n;scanf("%d",&n);        for(int i=1;i<=n;i++)            scanf("%d",&a[i]);        for(int i=1;i<=n;i++)            add(a[i],1);        int ans = 0;        for(int i=1;i<=n;i++)        {            add(a[i],-1);            for(int j=i+1;j<=n;j++)            {                add(a[j],-1);                ans = max(ans,match(a[i]+a[j]));                add(a[j],1);            }            add(a[i],1);        }        printf("%d\n",ans);    }}

转载于:https://www.cnblogs.com/qscqesze/p/4955980.html

你可能感兴趣的文章

嵌入式Linux驱动学习之路(十)字符设备驱动-my_led