HDu 4666:Hyperspace(最も遠いマンハッタン距離+STLで使用)
13846 ワード
Hyperspace
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1023 Accepted Submission(s): 492
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.
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 × 10
7). 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
Sample Output
0
746
0
1456
1456
1456
0
2512
5571
8922
Source
2013 Multi-University Training Contest 7
Recommend
zhuyuanchen520 | We have carefully selected several similar problems for you:
4822
4821
4820
4819
4818
最大マンハッタン距離+STLライブラリで使用します.
問題は、qとnが既知であり、qは要求の数であり、nは平面点の次元数であることを意味する.次にq行要求を入力し、各行要求は2つの部分からなり、それぞれ命令odと操作数であり、od=0は加入点を表し、od 1は削除点を表す.od=0の場合、後にn個の整数があり、n次元点のn個の座標値を表す.od=1の場合、削除点を表し、現在存在するいくつかの点を削除するのではなく、q番目の命令が加わった点を削除します.例えばコマンド「1 5」は、5行目のコマンドが加わった点を削除することを示す.
最も遠いマンハッタンの距離がどのように求める筒靴がここを見ることができることを知りません:最大マンハッタン距離
実は絶対値を取り除いて、シフトして、それから法則を発見します.いくつかの例を探して演算してみれば分かりやすい.
マンハッタンから最も遠い距離の入門問題を見てみましょう.poj 2926:Requirements(最も遠いマンハッタン距離、入門問題)
削除操作があるので、直接配列を使うのは面倒ですが、STLのマッピングテーブルmapと集合setを使うと便利です.もともと1本の類似の問題を探して、直接私の書いたテンプレートをカバーしたことがあるだけで、結局このような1本を見つけてSTLの問題を使わなければならなくて、とても仕方がないことを表して、機を借りてSTLに熟知しているようにしましょう.私は他の人のコードを参照して書いたことを認めます.
参考ブログ:HDU 4666 Hyperspace
コード:
Freecode : www.cnblogs.com/yym2013
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1023 Accepted Submission(s): 492
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.
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 × 10
7). 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 -2516Sample Output
0
746
0
1456
1456
1456
0
2512
5571
8922
Source
2013 Multi-University Training Contest 7
Recommend
zhuyuanchen520 | We have carefully selected several similar problems for you:
4822
4821
4820
4819
4818
最大マンハッタン距離+STLライブラリで使用します.
問題は、qとnが既知であり、qは要求の数であり、nは平面点の次元数であることを意味する.次にq行要求を入力し、各行要求は2つの部分からなり、それぞれ命令odと操作数であり、od=0は加入点を表し、od 1は削除点を表す.od=0の場合、後にn個の整数があり、n次元点のn個の座標値を表す.od=1の場合、削除点を表し、現在存在するいくつかの点を削除するのではなく、q番目の命令が加わった点を削除します.例えばコマンド「1 5」は、5行目のコマンドが加わった点を削除することを示す.
最も遠いマンハッタンの距離がどのように求める筒靴がここを見ることができることを知りません:最大マンハッタン距離
実は絶対値を取り除いて、シフトして、それから法則を発見します.いくつかの例を探して演算してみれば分かりやすい.
マンハッタンから最も遠い距離の入門問題を見てみましょう.poj 2926:Requirements(最も遠いマンハッタン距離、入門問題)
削除操作があるので、直接配列を使うのは面倒ですが、STLのマッピングテーブルmapと集合setを使うと便利です.もともと1本の類似の問題を探して、直接私の書いたテンプレートをカバーしたことがあるだけで、結局このような1本を見つけてSTLの問題を使わなければならなくて、とても仕方がないことを表して、機を借りてSTLに熟知しているようにしましょう.私は他の人のコードを参照して書いたことを認めます.
参考ブログ:HDU 4666 Hyperspace
コード:
1 #include <iostream>
2 #include <iomanip>
3 #include <stdio.h>
4 #include <map>
5 #include <set>
6 using namespace std; 7 int main() 8 { 9 int i,j,k,q,dem; 10 while(scanf("%d%d",&q,&dem)!=EOF){ 11 multiset <int> s[20]; //
12 multiset <int>::iterator it1,it2; 13 map <int,int> m[20]; //
14 int a[6]; 15 for(i=1;i<=q;i++){ 16 int od; 17 scanf("%d",&od); 18 if(od==0){ //
19 for(j=0;j<dem;j++) 20 scanf("%d",&a[j]); 21 for(j=0;j<(1<<(dem-1));j++){ //
22 int sum = 0; 23 for(k=0;k<5;k++){ // ， 4 24 //
25 int t = j & 1<<k; //1 +，0 -
26 if(t) sum+=a[k]; 27 else sum-=a[k]; 28 } 29 s[j].insert(sum); 30 m[j][i] = sum; 31 } 32 } 33 else{ //
34 int t; 35 scanf("%d",&t); 36 for(j=0;j<(1<<(dem-1));j++){ 37 if(m[j].size()>0){ 38 s[j].erase(s[j].find(m[j][t])); 39 m[j].erase(t); 40 } 41 } 42 } 43 int Max = 0; 44 for(j=0;j<(1<<(dem-1));j++){ 45 if(s[j].size()>0){ 46 it1 = s[j].begin(); 47 it2 = s[j].end(); 48 it2--; 49 Max = *it2-*it1 > Max? *it2-*it1 : Max; 50 } 51 } 52 printf("%d
",Max); 53 } 54 } 55 return 0; 56 }Freecode : www.cnblogs.com/yym2013