Chip Factory

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

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
 

Sample Output
6 400
 

Source

2015ACM/ICPC亚洲区长春站-重现赛（感谢东北师大） 



思路：

题意就是求最大的  （a[i]+a[j]）^a[k]  的值。最基本的想法就是ijk三重循环遍历求解，但是会TLE。然后我就稍微的修改了一下，把j从i+1开始，k从j+1开始，并且，因为i=1,j=2,k=3和i=1,j=3,k=2和i=2,j=3,k=1和i=2,j=1,k=3和i=3,j=1,k=2和i=3,j=2,k=1都是对应的1、2、3这三个数，那么就不需要遍历这个状态6次，而是只需要遍历到1、2、3这个状态的时候进行三次运算（因为加号有交换律所以重复了一半）。这样就大大的减少了时间，然后就意外的过了。。。。


代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int a[1000+5];

int main()
{
	int num;
	while(scanf("%d",&num)!=EOF)
	{
		while(num--)
		{
			int n;
			scanf("%d",&n);
			for(int i=0;i<n;i++)
			{
				scanf("%d",&a[i]);	
			}
			int maxn=-1;
			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,(a[i]+a[j])^a[k]);
					    maxn=max(maxn,(a[i]+a[k])^a[j]);
					    maxn=max(maxn,(a[j]+a[k])^a[i]);
					}
			printf("%d\n",maxn);
		}
	}
}