Chip Factory
Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 368 Accepted Submission(s): 202
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
3
1 2 3
3
100 200 300
Sample Output
6
400
400
Source
题意：给出一组n的数，问max((a[i]+a[j])^a[k]) i != j != k
分析：
有几种方法
1、现将a[i]+a[j]存起来，枚举k，在数据结构中查询。。。注意要去除ak的影响，我是用了主席树，其实可以用trie，这是最蠢的一种做法。。。就是我的做法。。。
2、将ak存起来，枚举ai,aj，注意到时间9s，同上的方法。比第一种快
3、暴力。。。。实在太猥琐了。。。居然没卡掉。。。。n^3暴力居然过了。。。
4、cheat做法。。。枚举前80%
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define MLL (1000000000000000001LL)
#define INF (1000000001)
#define For(i, s, t) for(int i = (s); i <= (t); i ++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i --)
#define Rep(i, n) for(int i = (0); i < (n); i ++)
#define Repn(i, n) for(int i = (n)-1; i >= (0); i --)
#define mk make_pair
#define ft first
#define sd second
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define sz(x) ((int) (x).size())
#define clr(x, y) (memset(x, y, sizeof(x)))
inline void SetIO(string Name)
{
string Input = Name + ".in";
string Output = Name + ".out";
freopen(Input.c_str(), "r", stdin);
freopen(Output.c_str(), "w", stdout);
} inline int Getint()
{
char ch = ' ';
int Ret = ;
bool Flag = ;
while(!(ch >= '' && ch <= ''))
{
if(ch == '-') Flag ^= ;
ch = getchar();
}
while(ch >= '' && ch <= '')
{
Ret = Ret * + ch - '';
ch = getchar();
}
return Ret;
} const int N = , M = , Dep = ;
struct SegmentType
{
int Child[], Sum;
#define Lc(x) (Seg[x].Child[0])
#define Rc(x) (Seg[x].Child[1])
#define Child(x, y) (Seg[x].Child[y])
#define Sum(x) (Seg[x].Sum)
} Seg[(M+N)*Dep];
int Tot;
int n, Arr[N];
int Cnt[M], Length;
int Ans; inline void Solve(); inline void Input()
{
int TestNumber = Getint();
while(TestNumber--)
{
n = Getint();
For(i, , n) Arr[i] = Getint();
Solve();
}
} inline void Init(int x) {
clr(Seg[x].Child, ), Sum(x) = ;
} inline void Insert(int Val, int x, int Depth)
{
Sum(x)++;
if(Depth < ) return;
int Type = (Val & ( << Depth)) > ;
if(!Child(x, Type)) {
Child(x, Type) = ++Tot;
Init(Child(x, Type));
}
Insert(Val, Child(x, Type), Depth-);
} inline int Work(int Val, int x, int Depth)
{
if(!x) return ;
if(Depth < ) return Sum(x);
int Type = (Val & ( << Depth)) > ;
if(Type) return Sum(Lc(x)) + Work(Val, Rc(x), Depth - );
return Work(Val, Lc(x), Depth - );
} inline void Query(int Val, int x, int Depth, int &Ret)
{
if(Depth < ) return;
int Type = (Val & ( << Depth)) > ;
if(Child(x, Type ^ ))
{
int p1 = Ret;
p1 |= ( << Depth) * (Type ^ );
p1 = p1 - Val - ;
int A = Work(p1, , );
int p2 = Ret;
p2 |= ( << Depth) * (Type ^ );
p2 |= ( << Depth) - ;
p2 = p2 - Val;
int B = Work(p2, , );
int p = B - A;
if(Val > p1 && Val <= p2) p--;
if(Sum(Child(x, Type ^ )) - p > )
{
Ret |= ( << Depth) * (Type ^ );
Query(Val, Child(x, Type ^ ), Depth - , Ret);
return;
}
}
Ret |= ( << Depth) * Type;
Query(Val, Child(x, Type), Depth - , Ret);
} inline void Solve()
{
Tot = , Length = ;
Init(), Init(), Init();
For(i, , n)
{
For(j, i + , n)
{
Cnt[++Length] = Arr[i] + Arr[j];
Insert(Cnt[Length], , );
}
Insert(Arr[i], , );
} Ans = ;
for(int i = ; i <= n; i++)
{
int x = ;
Query(Arr[i], , , x);
Ans = max(Ans, x ^ Arr[i]);
}
printf("%d\n", Ans);
} int main()
{
Input();
//Solve();
return ;
}