Hyperspace
这个题目把绝对值拆开很巧妙，正确性由不等式 ±x±y<=|x|+|y|保证。为啥用map做呢，只能说请相信我的智商，只是当时有点犯傻。。。
Code#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#define PII make_pair
using namespace std;
const int N=60000;
int q,k,A[N+10][10];
bool del[N+10];
int main()
{
while(scanf("%d%d",&q,&k)!=EOF){
memset(del,0,sizeof(del));
int full=1<<k,all=full-1,op,t=0,num=0;
multimap<int,int,greater<int> > table[full];
multimap<int,int,greater<int> >::iterator p;
for(int time=1;time<=q;time++){
scanf("%d",&op);
if(op==1){scanf("%d",&t);del[t]=1;num--;}else{
num++;
for(int i=0;i<k;i++)scanf("%d",&A[time][i]);
for(int i=0;i<full;i++){
int sum=0;
for(int j=0;j<k;j++)
sum+=A[time][j]*(((i>>j)&1)?1:-1);
table[i].insert(PII(sum,time));
}
}
int ans=0;
if(num==0||num==1)printf("0
");else{
for(int i=0;i<(full>>1);i++){
int a,b;
p=table[i].begin();
while(del[p->second])
{table[i].erase(p);p=table[i].begin();}
a=p->first;
p=table[all-i].begin();
while(del[p->second])
{table[all-i].erase(p);p=table[all-i].begin();}
b=p->first;
ans=max(ans,a+b);
}
printf("%d
",ans);
}
}
}
return 0;
}
后来写了一个堆版本的，不知道为什么RE。
Code#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define PII make_pair
using namespace std;
typedef pair<int,int> HeapNode;
const int N=60000;
int q,k,A[N][5];
bool del[N+10];
int main()
{
while(scanf("%d%d",&q,&k)!=EOF){
memset(del,0,sizeof(del));
int full=1<<k,all=full-1,op,t=0,num=0;
priority_queue< HeapNode,vector<HeapNode>,less<HeapNode> > table[all];
for(int time=1;time<=q;time++){
scanf("%d",&op);
if(op==1){scanf("%d",&t);del[t]=1;num--;}else{
num++;
for(int i=0;i<k;i++)scanf("%d",&A[time][i]);
for(int i=0;i<full;i++){
int sum=0;
for(int j=0;j<k;j++)
sum+=A[time][j]*(((i>>j)&1)?1:-1);
table[i].push(PII(sum,time));
}
}
int ans=0;
if(num==0||num==1)printf("0
");else{
for(int i=0;i<(full>>1);i++){
while(del[table[i ].top().second])table[i ].pop();
while(del[table[all-i].top().second])table[all-i].pop();
int a=table[i].top().first,b=table[all-i].top().first,
ans=max(ans,a+b);
}
printf("%d
",ans);
}
}
}
return 0;
}
Backup Plan
题目说要求只坏一台，想明白只要设计出输出的前两列这个题就随便搞了，平均分分就行了。
