Chip Factory
Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1842 Accepted Submission(s): 833
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 are three different integers between and . 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 , indicating the number of chips produced today. The next line has integers , separated with single space, indicating serial number of each chip.
There are at most testcases with
3
1 2 3
3
100 200 300
题意:给你n个整型数(n<=1e3),现在可以从其中选出s1,s2,s3三个数字,要求求出(s1+s2)^s3的最大值,至多
1e3组测试数据。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#define MM(a,b) memset(a,b,sizeof(a));
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
#define CT continue
#define SC scanf
const int N=1e3+10; int ch[40*N][3];
int a[N],sz,num[40*N],val[40*N];
bitset<32> v; void add(int k)
{
int p=0;
for(int i=30;i>=0;i--){
int id=v[i];
if(ch[p][id]==-1) ch[p][id]=++sz;
p=ch[p][id];
num[p]+=k;
}
if(k!=-1) val[p]=v.to_ullong();//返回bitset的值
} int query()
{
int p=0;
for(int i=30;i>=0;i--){
int id=v[i],ano=ch[p][!id];
if(ano!=-1&&num[ano]!=0) p=ano;
else p=ch[p][id];
}
return val[p];
} int main()
{
int cas,n;
SC("%d",&cas);
while(cas--){
MM(ch,-1);MM(num,0);sz=0;
SC("%d",&n);
for(int i=1;i<=n;i++){
SC("%d",&a[i]);
v=a[i];
add(1);
} int ans=0;
for(int i=1;i<=n;i++){
v=a[i];add(-1);
for(int j=i+1;j<=n;j++){
v=a[j];add(-1);
v=a[i]+a[j];
ans=max(ans,(a[i]+a[j])^query());
v=a[j];add(1);
}
v=a[i];add(1);
}
printf("%d\n",ans);
}
return 0;
}
错因:刚开始想到的是枚举下s1+s2,然后,,插入s3,,,但是发现根本处理不了重合的情况,,,。。
解答:其实先依次添加元素建好字典树后,,可以n^2的枚举s1+s2,同时在字典树中抹去这两个元素,
这时再插入s3,,每次操作完成后都将s1,s2再添加进去。。