poj 2352(简单树状数组)

Stars

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 32756 Accepted: 14309

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.
poj 2352(简单树状数组)

For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it">
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

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.

Source

Ural Collegiate Programming Contest 1999

level就是指当前星星的左下方的星星个数。因为y坐标已经排序,则对于每个星星只需要求x坐标前的星星个数了,典型的树状数组求解。因为x可以等于0,所以我把每个x坐标都+1处理。

AC代码:

#include #include #include using namespace std; int n; int c[320005],d[15005]; int lowbit(int x){ return x&-x; } int sum(int x){ int ret=0; while(x>=1){ ret+=c[x]; x-=lowbit(x); } return ret; } void add(int x){ while(x

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:UVA - 11927 Games Are Important (SG)
下一篇:LightOJ 1032 - Fast Bit Calculations (数位dp)
相关文章

对于c/c++中的数组排序及计算平均值和

在c/c++中利用数组名和指针进行排序的

C/C++中多维数组的指针作为函数参数传

C/C++中数组和指针类型的关系的入门教

c/c++中的字符指针数组,指向指针的指针

C/C++数组名与指针区别深入探索

c++之字符数组型的静态成员初始化实例

C++ VS C#(5):数组

C++中的动态多维数组

C++中的动态多维数组

图文推荐
poj 2352(简单树状数组)
ZOJ 3640 Help Me
poj 2352(简单树状数组)
CF 518C(Anya and
poj 2352(简单树状数组)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-09-28 人气:3
本文关键词:
分享到:

相关文章

  • poj-2352-Stars-线段树 2012-02-18

    很裸的单点更新线段树 #include #include #include #include using namespace std; #define maxn 110000 struct list { int l,r; int x; }node[maxn*6]; struct listt { int x,y; bool friend operator x||rr||rr 点击复制链接 与好友分享!回本站首页 您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力 上一

  • POJ 2352 && HDU 1541 Stars (树状数组) 2013-02-04

    一开始想,总感觉是DP,可是最后什么都没想到。还暴力的交了一发。 然后开始写线段树,结果超时。感觉自己线段树的写法有问题。改天再写。先把树状数组的写法贴出来吧。 ~~~~~~~~~~~~~~~~~~~~~~~~ 树状数组不懂的去看刘汝佳的大白书,那个图画得很清楚。 题目大意:星星的坐标以y递增的顺序给出,这些点的左下方的点数代表这个点的级数,问0~N-1的级数有多少个?其实y根本木有用。 题目链接:http://poj.org/problem?id=2352 http://acm.hdu.edu

  • POJ 2352--Stars(树状数组) 2014-01-16

    Stars Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 32738 Accepted: 14298 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 b

  • POJ 1236 Network of Schools(强连通分量) 2015-02-28

    题目地址:POJ 1236 这个题的大意是求最少往多少点发送消息可以使任意一个点都能收到消息和最少增加多少条边可以使图为连通图。对于第一个问题,可以求入度为0的强连通块的块数,因为只有入度为0的强连通块是无法从外界接受信息的,而只要有一个入度的话,那整个连通块就都可以接收到信息。第二个问题则是求入度为0的强连通块与出度为0的强连通块的个数的最大值。 代码如下: #include #include #include #include #include #include #include #incl

  • CodeForces 34C Page Numbers 2012-04-26

    #include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f #pragma comment(linker, "/STACK:16777216") #define eps 1e-6 #define ll long long using namespace std; inline int ReadInt() { char ch = ge

  • UVA 11437 - Triangle Fun 向量几何 2012-05-26

    http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2432 题目大意: 如图,定义三角形ABC,在BC,CA,AB上分别取边D,E,F,使得CD=2BD,AE=2CE,BF=2AF,求三角形PQR的面积。 思路:vcD4KPHA+z8jH87P2RCxFLEbI/bXj1/ix6qOsyLu688fzs/ZQUVLI/bXj1/ix6

  • uva 815 - Flooded!(点名要做的思路题~我觉得方法挺好) 2013-09-09

    #include #include #include #include using namespace std; double a[100000]; double vol[100000]; int m,n; double v1,v2; bool cmp(double aa,double bb) { if(aa>bb) return true; } int main() { int kase=0; while(scanf("%d%d",&m,&n)!=EOF) { kase+

  • HDU 4777 树状数组求区间内 与该区间全互质的数个数 2014-08-13

    题意: 给定n个数的序列 m个询问,问该区间内,与所有区间内数互质的数有多少个 #include #include #include #include #include #define N 200005 using namespace std; vectorprime[N];//prime[i] 是i的所有因子(不包括1) vectoredge[N]; struct query{ int l, r, num; bool operatorl; } }q[N]; int ans[N]; int tr

  • POJ 1062 昂贵的聘礼 2012-01-03

    非常老的题目了,枚举层次dijkstra,G++AC 昂贵的聘礼 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 33747 Accepted: 9652 Description 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了,于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币,便请求酋长降低要求。酋长说:"嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.019 (s). 10 q(s)