HDU 4666 Hyperspace (最远曼哈顿距离)
2024-10-16 09:39:57
Hyperspace
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 314 Accepted Submission(s): 155
Problem Description
The great Mr.Smith has invented a hyperspace particle generator. The device is very powerful. The device can generate a hyperspace. In the hyperspace, particle may appear and disappear randomly. At the same time a great amount of energy was generated.
However, the device is in test phase, often in a unstable state. Mr.Smith worried that it may cause an explosion while testing it. The energy of the device is related to the maximum manhattan distance among particle.
Particles may appear and disappear any time. Mr.Smith wants to know the maxmium manhattan distance among particles when particle appears or disappears.
However, the device is in test phase, often in a unstable state. Mr.Smith worried that it may cause an explosion while testing it. The energy of the device is related to the maximum manhattan distance among particle.
Particles may appear and disappear any time. Mr.Smith wants to know the maxmium manhattan distance among particles when particle appears or disappears.
Input
The input contains several test cases, terminated by EOF.
In each case: In the first line, there are two integer q(number of particle appear and disappear event, ≤60000) and k(dimensions of the hyperspace that the hyperspace the device generated, ≤5). Then follows q lines. In each line, the first integer ‘od’ represents the event: od = 0 means this is an appear
event. Then follows k integer(with absolute value less then 4 × 107). od = 1 means this is an disappear event. Follows a integer p represents the disappeared particle appeared in the pth event.
In each case: In the first line, there are two integer q(number of particle appear and disappear event, ≤60000) and k(dimensions of the hyperspace that the hyperspace the device generated, ≤5). Then follows q lines. In each line, the first integer ‘od’ represents the event: od = 0 means this is an appear
event. Then follows k integer(with absolute value less then 4 × 107). od = 1 means this is an disappear event. Follows a integer p represents the disappeared particle appeared in the pth event.
Output
Each test case should contains q lines. Each line contains a integer represents the maximum manhattan distance among paticles.
Sample Input
10 2
0 208 403
0 371 -180
1 2
0 1069 -192
0 418 -525
1 5
1 1
0 2754 635
0 -2491 961
0 2954 -2516
0 208 403
0 371 -180
1 2
0 1069 -192
0 418 -525
1 5
1 1
0 2754 635
0 -2491 961
0 2954 -2516
Sample Output
0
746
0
1456
1456
1456
0
2512
5571
8922
746
0
1456
1456
1456
0
2512
5571
8922
Source
Recommend
zhuyuanchen520
题意:给定一些操作(0代表添加一个点,1代表删除一个点),求这些点的最远曼哈顿距离。
可先参考POJ 2926 Requirements:http://poj.org/problem?id=2926
POJ该题思路:
以二维平面为例:
设距离最远的两点为 i, j,可知所求的最大距离必定有以下四种形式之一:
(xi-xj)+(yi-yj), (xj-xi)+(yi-yj), (xi-xj)+(yj-yi), (xj-xi)+(yj-yi) 变形一下,把相同点的坐标放到一起,
即 (xi+yi)-(xj+yj), (-xi+yi)-(-xj+yj), (xi-yi)-(xj-yj), (-xi-yi)-(-xj-yj),可以发现即去绝对值之后把同一点的坐标放在一起,对应坐标符号相同。
假如我们用0表示符号,用1表示正号,那么 (xi+yi) 可以表示为 11。
那么要表示一个维数为 dem 的所有状态,只需要用 0 ~ (2^dem-1) 的所有二进制就可以了。
于是只要对所有的点 (xi,yi),依次计算出 (xi+yi), (xi-yi), (-xi+yi), (-xi-yi)这四种形式,然后把每个点i算出来的这四种情况的最大值、最小值分别记录(更新)到数组 max[] 和 min[] 中,然后枚举每一种去绝对值的组合,组合后的最大值即为 answer。
代码:
#include<iostream>
#include<cstdio>
#include<cstring> using namespace std; const int N=;
const double INF=1e20; int n;
double num[N][],minx[<<],maxx[<<]; int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n)){
for(int i=;i<n;i++)
for(int j=;j<;j++)
scanf("%lf",&num[i][j]);
for(int i=;i<(<<);i++){ //共有(1<<5)种状态,存储每种状态下的最大最小值
minx[i]=INF;
maxx[i]=-INF;
}
double sum;
int tmp;
for(int i=;i<n;i++)
for(int j=;j<(<<);j++){ //枚举每种状态
tmp=j;
sum=;
for(int k=;k<;k++){
if(tmp&)
sum+=num[i][k];
else
sum-=num[i][k];
tmp>>=;
}
if(maxx[j]<sum)
maxx[j]=sum;
if(minx[j]>sum)
minx[j]=sum;
}
double ans=-INF;
for(int i=;i<(<<);i++)
if(maxx[i]-minx[i]>ans)
ans=maxx[i]-minx[i];
printf("%.2f\n",ans);
}
return ;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set> using namespace std; const int N=;
const double INF=1e20; int n,m,num[N][];
//map<int,int,greater<int> > mp[1<<5];
multiset<int> mst[<<];
multiset<int>::iterator it1,it2; int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){
for(int i=;i<(<<);i++)
mst[i].clear();
int od,x;
for(int i=;i<=n;i++){
scanf("%d",&od);
if(od==){
for(int j=;j<m;j++)
scanf("%d",&num[i][j]);
for(int j=;j<(<<m);j++){
int sum=;
for(int k=;k<m;k++){
if(j&(<<k))
sum+=num[i][k];
else
sum-=num[i][k];
}
mst[j].insert(sum);
}
}else{
scanf("%d",&x);
for(int j=;j<(<<m);j++){
int sum=;
for(int k=;k<m;k++){
if(j&(<<k))
sum+=num[x][k];
else
sum-=num[x][k];
}
it1=mst[j].find(sum);
mst[j].erase(it1);
}
}
int ans=;
//map<int,int>::iterator it1,it2;
for(int j=;j<(<<m);j++){
it1=mst[j].end();
it1--;
it2=mst[j].begin();
ans=max(ans,(*it1)-(*it2));
}
printf("%d\n",ans);
}
}
return ;
}
最新文章
- RapidJSON 代码剖析(二):使用 SSE4.2 优化字符串扫描
- linux 内核cache
- 解剖SQLSERVER 第五篇 OrcaMDF里读取Bits类型数据(译)
- springMVC,mybatis配置事务
- HUD 5086 Revenge of Segment Tree(递推)
- urllib3 PoolManager
- Oracle数据类型对应Java类型
- git 秘钥的生成
- Bash算术计算
- WP Super Cache 安装与设置方法
- 智能家居项目(2):项目project框架的搭建
- 【前端攻略】:玩转图片Base64编码(转)
- Python pandas 0.19.1 Intro to Data Structures 数据结构介绍 文档翻译
- 解决phpmyadmin 点击表结构时卡顿、一直加载、打不开的问题
- wpf 研究之道 winform or wpf,u choose who?
- Dynamic attention in tensorflow
- sublime 格式化react插件配置教程 jsfmt配置
- 设置Chrome忽略网站证书错误
- Cloud Native Weekly | 华为云抢先发布Redis5.0,红帽宣布收购混合云提供商 NooBaa
- GPS项目小结