HDU 5536 Chip Factory

2018-02-11 15:00:40来源:cnblogs.com作者:自为风月马前卒人点击


Chip Factory

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

 Problem DescriptionJohn 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 pro

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} (s_i+s_j) /oplus s_k 
which i,j,k are three different integers between 1 and n. And /oplus is symbol of bitwise XOR.

Can you help John calculate the checksum number of today? InputThe 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 s_1, s_2, .., s_n, separated with single space, indicating serial number of each chip.

1 /le T /le 1000
3 /le n /le 1000
0 /le s_i /le 10^9
There are at most 10 testcases with n > 100  OutputOutputFor each test case, please output an integer indicating the checksum number in a line. Sample Input231 2 33100 200 300 Sample Output6400 Source2015ACM/ICPC亚洲区长春站-重现赛(感谢东北师大)  Recommendhujie   |   We have carefully selected several similar problems for you:  6263 6262 6261 6260 6259   读不懂英语好吃亏啊。一开始一直在想前面的$s_i+s_j$怎么搞。后来看了一下输入,这么不就是个逗比题么。。$s_i+s_j$只要暴力枚举就好,建一颗01Trie树,查询最大的时候优先走不一样的查询之前先把$s_i,s_j$删除查完之后再加进去 
#include<cstdio>#include<cmath>#include<algorithm>using namespace std;const int MAXN=1e6+10;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}#define debug(x) printf("%d",x);struct node{    int val,ch[2];    node(){val=ch[0]=ch[1]=0;}    void clear(){val=ch[0]=ch[1]=0;}}T[MAXN];int a[MAXN],root=0,tot=0;void Insert(int v){    int now=root;    for(int i=31;i>=0;i--)    {        int opt=(v&(1<<i))?1:0;        if(!T[now].ch[opt])             T[now].ch[opt]=++tot;        now=T[now].ch[opt];        T[now].val++;     }}void Delet(int v){    int now=root;    for(int i=31;i>=0;i--)    {        int opt=(v&(1<<i))?1:0;        now=T[now].ch[opt];        T[now].val--;     }}int Query(int v){    int ans=0,now=root;    for(int i=31;i>=0;i--)    {        int opt=(v&(1<<i))?1:0;        if(T[T[now].ch[opt^1]].val)             ans+=1<<i,now=T[now].ch[opt^1];        else             now=T[now].ch[opt];    }    return ans;}int main(){    freopen("a.in","r",stdin);    int Test=read();    while(Test--)    {        int N=read();        for(int i=1;i<=N;i++) a[i]=read();        for(int i=1;i<=4*N;i++)             T[i].clear();        for(int i=1;i<=N;i++)             Insert(a[i]);        int ans=0;        for(int i=1;i<=N;i++)        {            for(int j=1;j<i;j++)            {                Delet(a[i]);Delet(a[j]);                ans=max(ans,Query(a[i]+a[j]));                Insert(a[i]);Insert(a[j]);            }        }        printf("%d/n",ans);    }    return 0;}