数据加载中……

TJU_OI 1090 战地统计系统(War Field Statistical System)

1090.  战地统计系统(War Field Statistical System)

输入文件名:c.in     输出文件名:c.out 提交  讨论  运行状况 

2050年,人类与外星人之间的战争已趋于白热化。就在这时,人类发明出一种超级武器,这种武器能够同时对相邻的多个目标进行攻击。凡是防御力小于或等于 这种武器攻击力的外星人遭到它的攻击,就会被消灭。然而,拥有超级武器是远远不够的,人们还需要一个战地统计系统时刻反馈外星人部队的信息。这个艰巨的任 务落在你的身上。请你尽快设计出这样一套系统。

这套系统需要具备能够处理如下2类信息的能力:

    1.外星人向[x1,x2]内的每个位置增援一支防御力为v的部队。

    2.人类使用超级武器对[x1,x2]内的所有位置进行一次攻击力为v的打击。系统需要返回在这次攻击中被消灭的外星人个数。

注:防御力为i的外星人部队由i个外星人组成,其中第j个外星人的防御力为j。

输入格式

从文件c.in第一行读入n,m。其中n表示有n个位置,m表示有m条信息。

以下有m行,每行有4个整数k,x1,x2,v用来描述一条信息 。k表示这条信息属于第k类。x1,x2,v为相应信息的参数。k=1 or 2。

注:你可以认为最初的所有位置都没有外星人存在。

规模:0<n≤1000;0<x1≤x2≤n;0<v≤1000;0<m≤2000

输出格式

结果输出到文件c.out。按顺序输出需要返回的信息。

输入样例

3 5
1 1 3 4
2 1 2 3
1 1 2 2
1 2 3 1
2 2 3 5

输出样例

6
9

样例说明

输入样例   对应输出     输出样例
3 5 无 6
1 1 3 4 无 9
2 1 2 3 6
1 1 2 2 无
1 2 3 1 无
2 2 3 5 9

题目来源OIBH 信息学练习赛 #6

题目标签

二维(1)   线段树(1)  

这个题目的标签是二维+线段树,我估计有些哥们真的用二维线段树来做了,查看了一下后面的代码,发现大多数的人的代码都超过2k,有的还达到s四五k之多.
我的思路是把这个题目转化成矩形切割来做,x,y,v三个参数以及默认的一个初始值代表了一个矩形区域,左下角(x1,y1)=(x,1),右上角(x2,y2)=(y,v);
切割的大体方法是从USACO上的一个题目学来的,类似木块上浮,从第一个矩形一直浮到最上面的矩形,每碰到一个遮盖的矩形就分裂当前矩形,在上浮的过程中计算出每次询问的答案.
如果你对矩形切割很了解,相信我的代码还是比较容易理解的.

 1 #include<iostream>
 2 using namespace std;
 3 const int MAXM=3000+100;
 4 struct rect
 5 {
 6   int x1,y1,x2,y2;
 7   rect(){};
 8   rect(int x1,int y1,int x2,int y2) : x1(x1),y1(y1),x2(x2),y2(y2) {}
 9 }temp,q[MAXM];
10 
11 int pos[MAXM],cp=0,ans[MAXM],n,m;
12 bool mark[MAXM];
13 
14 inline bool is_parted(rect& a,rect& b)
15 {
16   return (a.x2<b.x1 || a.x1>b.x2 || a.y2<b.y1 || a.y1>b.y2);
17 
18 
19 void Cut(int p,rect cur)
20 {
21   if (p>cp) return;
22   while ( p<=cp && is_parted(cur,q[pos[p]]) ) ++p;
23   if (p>cp) return;
24   rect ques=q[pos[p]];
25   int area=(cur.y2-cur.y1+1)*(cur.x2-cur.x1+1);
26   if (cur.x1<ques.x1){ 
27     area-=(ques.x1-cur.x1)*(cur.y2-cur.y1+1);
28     rect temp=cur;
29     cur.x1=ques.x1;
30     temp.x2=ques.x1-1;
31     Cut(p+1,temp);
32   }
33   if (cur.x2>ques.x2){
34     area-=(cur.x2-ques.x2)*(cur.y2-cur.y1+1);
35     rect temp=cur;
36     cur.x2=ques.x2;
37     temp.x1=ques.x2+1;
38     Cut(p+1,temp);
39   }
40   if (cur.y2>ques.y2){
41     area-=(cur.y2-ques.y2)*(cur.x2-cur.x1+1);
42     rect temp=cur;
43     cur.y2=ques.y2;
44     temp.y1=ques.y2+1;
45     Cut(p+1,temp);
46   }
47   if (cur.y1<ques.y1){
48     area-=(ques.y1-cur.y1)*(cur.x2-cur.x1+1);
49     rect temp=cur;
50     cur.y1=ques.y1;
51     temp.y2=ques.y1-1;
52     Cut(p+1,temp);
53   }
54   ans[p]+=area;
55 }
56 
57 int main()
58 {
59   freopen("c.in","r",stdin);
60   freopen("c.out","w",stdout);
61   memset(mark,0,sizeof(mark));
62   cin >> n >> m;
63   for (int i=0;i<m;++i){
64     int k,x,y,v;
65     cin >> k >> x >> y >> v;
66     q[i]=rect(x,1,y,v);
67     if (k==2){
68       mark[i]=1;
69       pos[++cp]=i;
70     }
71   }
72 
73   memset(ans,0,sizeof(ans));
74   int p=1;
75   for (int i=0;i<m;++i){
76     if (mark[i]) { ++p; continue; }
77     Cut(p,q[i]);
78   }
79   for (int i=1;i<=cp;++i) cout << ans[i] << endl;
80  
81   return 0;
82 }
83 

posted on 2009-07-26 20:19 Chen Jiecao 阅读(373) 评论(0)  编辑 收藏 引用 所属分类: TJU_OI


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理