地址：http://acm.split.hdu.edu.cn/showproblem.php?pid=5536
题目：
Chip Factory
Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2044 Accepted Submission(s): 919
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:
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?
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
#include<stdio.h>
int a[];
int max(int ta,int b)
{
if(ta>b)
return ta;
return b;
}
int sc(int ta,int tb,int tc,int ans)
{
return max(ans,(ta+tb)^tc);
}
int main(void)
{
int t,n;
scanf("%d",&t);
while(t--)
{
int ans=;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
for(int k=j+;k<=n;k++)
ans=sc(a[i],a[j],a[k],ans),ans=sc(a[j],a[k],a[i],ans),ans=sc(a[i],a[k],a[j],ans);
printf("%d\n",ans);
}
return ;
}
01trie代码：
#include <stdio.h>
#include <string.h>
struct Trie
{
int root, tot, next[][], cnt[], end[]; inline int Newnode()
{
memset(next[tot], -, sizeof(next[tot]));
cnt[tot] = ;
end[tot] = ;
return tot ++;
} inline void Init()
{
tot = ;
root = Newnode();
} inline void Insert(int x)
{
int p = root;
cnt[p] ++;
for(int i = ; i >= ; i --)
{
int idx = (( << i) & x) ? : ;
if(next[p][idx] == -)
next[p][idx] = Newnode();
p = next[p][idx];
cnt[p] ++;
}
end[p] = x;
} inline void Del(int x)
{
int p = root;
cnt[p] --;
for(int i = ; i >= ; i --)
{
int idx = (( << i) & x) ? : ;
p = next[p][idx];
cnt[p] --;
}
} inline int Search(int x)
{
int p = root;
for(int i = ; i >= ; i --)
{
int idx = (( << i) & x) ? : ;
if(idx == )
{
if(next[p][] != - && cnt[next[p][]])
p = next[p][];
else
p = next[p][];
}
else
{
if(next[p][] != - && cnt[next[p][]])
p = next[p][];
else
p = next[p][];
}
}
return x ^ end[p];
}
}tr;
int max(int ta,int tb)
{
return ta>=tb?ta:tb;
}
int a[];
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,ans=;scanf("%d",&n);
tr.Init();
for(int i=;i<=n;i++)
scanf("%d",&a[i]),tr.Insert(a[i]);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
tr.Del(a[i]),tr.Del(a[j]);
ans=max(ans,tr.Search(a[i]+a[j]));
tr.Insert(a[i]),tr.Insert(a[j]);
}
printf("%d\n",ans);
}
return ;
}