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