Chip Factory Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 4414 Accepted Submission(s): 1954 ...
Chip Factory
Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 4414 Accepted Submission(s):
1954
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; }
