HDU 5536 Chip Factory

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 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?

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 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

Output

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:  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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

    给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1

    attack
  • P1257 平面上的最接近点对

    题目描述 给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的 输入输出格式 输入格式: 第一行:n;2≤n≤...

    attack
  • BZOJ 1174: [Balkan2007]Toponyms

    Description 给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化. Input 第一行给出...

    attack
  • BZOJ 1174: [Balkan2007]Toponyms

    Description 给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化. Input 第一行给出...

    attack
  • P1257 平面上的最接近点对

    题目描述 给定平面上n个点,找出其中的一对点的距离,使得在这n个点的所有点对中,该距离为所有点对中最小的 输入输出格式 输入格式: 第一行:n;2≤n≤...

    attack
  • 黄蓉填充九宫格

    经过分析此题要点是边界处理,即向右上移动时,超出九宫格时的处理过程,右上冲突时向下移动不需要考虑边界问题,均未超出边界。

    一份执着✘
  • BZOJ 1083: [SCOI2005]繁忙的都市【Kruscal最小生成树裸题】

    1083: [SCOI2005]繁忙的都市 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2925  Sol...

    Angel_Kitty
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • 【 HDU - 4456 】Crowd (二维树状数组、cdq分治)

    给你一个n行n列的格子,一开始每个格子值都是0。有M个操作,p=1为第一种操作,给格子(x,y)增加z。p=2为询问与格子(x,y)的曼哈顿距离不超过z的格子值...

    饶文津

扫码关注云+社区

领取腾讯云代金券