HDU

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

Sample Output

6
400

题解：

最直白的3重for循环暴力，按说是过不去的，不过这题的数据没有那么严，可以暴力过。

当然最推荐的还是用01字典树。

代码：

暴力

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int board[1005];
 
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int N,maxn = 0;
		scanf("%d" ,&N);
		for(int i=0 ; i<N ; ++i)
			scanf("%d", &board[i]);
		for(int i=0 ; i<N ; ++i)
			for(int j=i+1 ; j<N ; ++j)
				for(int k=j+1 ; k<N ; ++k)
				{
					maxn = max(maxn, (board[i] + board[j]) ^ board[k]);
					maxn = max(maxn, (board[i] + board[k]) ^ board[j]);
					maxn = max(maxn, (board[j] + board[k]) ^ board[i]);
				}
		printf("%d
", maxn);
	}
}

01字典树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef struct Node* node;

struct Node
{
	int val;
	int num;
	node Next[2];
	Node()
	{
		val = num = 0;
		memset(Next,NULL,sizeof(Next));
	}
};

void Insert(node root,int x,int flag)
{
	node p = root;
	for(int i=31 ; i>=0 ; i--)
	{
		int t = (x>>i)&1;
		if(p->Next[t] == NULL)p->Next[t] = new struct Node();
		p->num += flag;
		p = p->Next[t]; 
	}
	p->num += flag;
	p->val = x;
}

int Judge(node root,int x)
{
	node p = root;
	for(int i=31 ; i>=0 ; i--)
	{
		int t = ((x>>i)&1)^1;
		if(p->Next[t] == NULL || p->Next[t]->num == 0)t = (x>>i)&1;
		if(p->Next[t] && p->Next[t]->num)p = p->Next[t];
		else return -1;
	}
	return p->val;
} 

void Del(node root){
	for(int i=0 ; i<2 ; ++i){
		if(root->Next[i])Del(root->Next[i]);
	}
	delete(root);
}

int board[1005];

int main(){
	
	int T,N;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&N);
		node root = new struct Node();
		for(int i=0 ; i<N ; ++i){
			scanf("%d",&board[i]);
			Insert(root,board[i],1);
		}
		long long maxn = 0;
		for(int i=0 ; i<N ; ++i){
			Insert(root,board[i],-1);
			for(int j=i+1 ; j<N ; ++j){
				Insert(root,board[j],-1);
				long long t = (board[i]+board[j])^(long long)Judge(root,board[i]+board[j]);
				if(t > maxn)maxn = t;
				Insert(root,board[j],1);
			}
			Insert(root,board[i],1);
		}
		printf("%lld
",maxn);
		Del(root);
	}
	
	return 0;
}