首页 > ACM题库 > HDU-杭电 > HDU 1541 Stars-树状数组-[解题报告] C++
2013
12-12

HDU 1541 Stars-树状数组-[解题报告] C++

Stars

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

5
1 1
5 1
7 1
3 3
5 5

样例输出:

1
2
1
1
0

 

原题:HDU 1541

题目意思就是说,给你一张star maps,每个star有自己的level,level是这样计算的:(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.)统计这个star左下角star的个数,就是这个star的level。现在要你总计图中level从0到N-1的star分别有多少个?

题目输入描述中明确告诉我们,输入的坐标是按Y的升序、如果Y相等,则按X的升序。所以我们发现我们可以完全忽略Y,只要统计小于本身X的star个数,就是level了。现在我们用一个数组a[]统计X坐标为i的个数(增加一个既a[i]++;);同时对每个star计算的得level。

这样对于X坐标为j的star,他得level为:

level=a[0]+a[1]+a[2]+…+a[j]

如果这样计算的话,每个level最坏时间要用O(m),计算n-1个level,这样要用O(mn)的时间复杂度,对于这题的数据而言,这无疑是无法接受的。我们发现,对于计算level,这是个查询区间问题sum[0,j], 如果没有元素的变更(既数组a是不变的),我们完全可以存储sum[0,k](k=0,2,……),然后对任意给定的查找区间[i,j],都可以方便的用ans=sum[1,j]-sum[1,i-1],当然这只是没有元素改变的情况下的比较优化的解法.那么对于有元素变更的问题是否有更高效的方法呢?这让我们想到的树状数组。

树状数组所针对问题:已知数组a[],元素个数为n,现在更改a中的元素,要求得新的a数组中i到j区间内的和(1<=i<=j<=n).

这题是比较简单和明显的树状数组,我们先不讨论如何实现树状数组。只告诉你树状数组现在有2个操作:

(1)    add(int i,int val) //将第i个元素更改val

(2)    sum(int i) //求前i项和

所以这题我们的伪代码可以如下实现:

for(i=0;i<n;i++)

{

1.    sacnf(x,y);

2.    cnt[sum(x+1)]++;

3.    add(x+1,1);

4.     

}

5.print:cnt[0,n-1];

上面因为树状数组是从1开始计数的,而坐标有可能为0,所以我们统一都加1;sum(x+1)就是计算当前star的level值,所以当前level个数加1;add(x+1,1)操作表示对当前元素更改(既+1);最后打印cnt数组。

树状数组的实现及其思想

那么树状数组是如何实现快速对数组更新和区间求和的呢?

关于树状数组的实现和思想,这个再不细说,参考下面资料:

http://baike.baidu.com/view/1420784.htm

http://www.cnblogs.com/yykkciwei/archive/2009/05/08/1452889.html

代码:

//============================================================================
// Name        : Stars.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN=32010;

int n,c[MAXN],cnt[MAXN];

inline int lowbit(int x)
{
	return x&(-x);
}

void add(int i,int val)
{
	while(i<MAXN)
	{
		c[i]+=val;
		i+=lowbit(i);
	}
}

int sum(int i)
{
	int s=0;
	while(i>0)
	{
		s+=c[i];
		i-=lowbit(i);
	}
	return s;
}

int main() {
	int x,y;
	while(scanf("%d",&n)!=EOF)
	{
		memset(c,0,sizeof(c));
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			cnt[sum(x+1)]++;
			add(x+1,1);

		}
		for(int i=0;i<n;i++)
		{
			printf("%d\n",cnt[i]);
		}
	}
	return 0;
}

 

解题报告转自:http://blog.csdn.net/jiangwentong/article/details/6847168


  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1