Stars
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 27333 | Accepted: 11958 |
Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
5 1 1 5 1 7 1 3 3 5 5
Sample Output
1 2 1 1 0
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
题意:
有N(1到15000)颗星星,给出每颗星星的x,y(0到32000)坐标。星星以y的递增顺序输入,如果y相等就以x递增的顺序输入。每颗星星都有一个等级,这个等级数是这颗星星左下位置的星星数量,最终统计每一层等级(0到N-1)的数量。
思路:
有一个关键的条件,星星以y的递增顺序输入,如果y相等就以x递增的顺序输入。这样的话,就是说明每输入一颗星星A,这个星星A一定是最高的,但是不一定是最右边的,在以后的每次输入中,不会再有一颗星星B会出现在这颗星星A的左下位置处,因为星星B一定要比A高,但是比A高不一定会在A的右边,但是无论B在左边还是右边,可以确定的一定是B肯定要比A高,那么就可以确定以后的每一颗星星B都不会出现在A的左下位置处,这就说明A的等级不会因为后面出现的星星而改变。
所以,先找出全部星星x坐标的最小值min和最大值max,以[min,max]为界来建立线段树。每次输入一颗星星之前,先统计在[min,x]中有几颗星星,这个星星数就是它的等级数,统计之后再插入这颗星星的x坐标于线段树中。
AC:
#include<stdio.h> #include<string.h> #define M (32000+5) //易错点 typedef struct { int l; int r; int sum; }node; node no[M*4]; int x[M],y[M]; int fin[M],t; void build(int from,int to,int i) { int mid=(from+to)/2; no[i].l=from; no[i].r=to; no[i].sum=0; if(from==to) return; build(from,mid,2*i); build(mid+1,to,2*i+1); } void add(int i,int a) { int mid=(no[i].l+no[i].r)/2; if(no[i].l==no[i].r) { no[i].sum++; return; } if(a<=mid) add(2*i,a); if(a>=mid+1) add(2*i+1,a); no[i].sum=no[2*i].sum+no[2*i+1].sum; } void find(int from,int to,int i) { int mid=(no[i].l+no[i].r)/2; if(from==no[i].l&&to==no[i].r) { t+=no[i].sum; return; } if(from>=mid+1) find(from,to,2*i+1); if(to<=mid) find(from,to,2*i); if(from<=mid&&to>=mid+1) { find(from,mid,2*i); find(mid+1,to,2*i+1); } } int main() { int n; int min,max; while(scanf("%d",&n)!=EOF) { min=M,max=-1; for(int i=1;i<=n;i++) { scanf("%d%d",&x[i],&y[i]); if(x[i]>max) max=x[i]; if(x[i]<min) min=x[i]; } build(min,max,1); memset(fin,0,sizeof(fin)); for(int i=1;i<=n;i++) { t=0; find(min,x[i],1); fin[t]++; add(1,x[i]); } for(int i=0;i<=n-1;i++) printf("%d\n",fin[i]); } return 0; }
总结:
1.题目是多输入;
2.RE了N次,是因为#define M (32000+5)。一开始写成了#define M 32000+5,因为后面数组的大小是M*4,这样的话就是32000+5*4。而事实上我想要的结果是(32000+5)*4,所以要加括号。要细心。
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
绘制太阳系行星轨道2D平面图,数据库中包含了行星数据,但是数据来源于百度搜集,不够精确
star manual is a manual for cmg software
Stars1
Stars2
以每个星星为中心,得到可以罩住它的矩形的左下角的范围,这些范围内的点增加星星亮度,由于落在框上的点不算,框不一定要整数起点,可另左下落在框上算。求亮度和最大的点即可。...每次用线段树更新和求最大值。
视觉测量(V-STARS摄影测量系统) 立体视觉是由多幅图像(一般2幅)获取物体三维几何信息的方法
stars
按stars排序的论文-代码实现列表,每周更新
m3u8合并器 by stars-one.zip
StarCabinet, 开源的跨平台Github Stars管理分析工具
Baseball Stars 2 (USA) wiiware wad 格式wii 专用,可以放到SD卡内进行安装
Atom-atom-package-diff.zip,安装的Atom软件包与APM Stars之间的差异原子包差异,atom是一个用web技术构建的开源文本编辑器。
Android Five Stars Library Android Five Stars Library is a small library that helps developers add a "Rate My App" dialog to their applications. It's called "Five Stars" because the dialog has a ...
在Github中stars数最多的Go Web框架集合
当前版本的STARS是基于从数字到Numpy的重构。 此版本应可在以下平台上使用 Linux 视窗 苹果电脑 安装 使用Conda(所有平台) git clone https://github.com/sjsrey/stars.git 安装 conda create -n stars python...
上传一个用vc制作的闪闪的红星,能够自定义背景和闪烁速度。你们可以
Radio Stars
CMG-STARS使用指南适用于初学者,是PDF文件,英语也比较容易看懂。
city of stars.docx