首页 > ACM题库 > HDU-杭电 > hdu 2352 Verdis Quo-树状数组[解题报告]C++
2014
01-05

hdu 2352 Verdis Quo-树状数组[解题报告]C++

Verdis Quo

问题描述 :

The Romans used letters from their Latin alphabet to represent each of the seven numerals in their number system. The list below shows which
letters they used and what numeric value each of those letters represents:

I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

Using these seven numerals, any desired number can be formed by following the two basic additive and subtractive rules. To form a number using
the additive rule the Roman numerals are simply written from left to right in descending order, and the value of each roman numeral is added
together. For example, the number MMCLVII has the value 1000 + 1000 + 100 + 50 + 5 + 1 + 1 = 2157. Using the addition rule alone could lead to
very long strings of letters, so the subtraction rule was invented as a result. Using this rule, a smaller Roman numeral to the left of a larger one is
subtracted from the total. In other words, the number MCMXIV is interpreted as 1000 – 100 + 1000 + 10 – 1 + 5 = 1914.

Over time the Roman number writing system became more standardized and several additional rules were developed. The additional rules used today
are:

1. The I, X, or C Roman numerals may only be repeated up to three times in succession. In other words, the number 4 must be represented as IV
and not as IIII.
2. The V, L, or D numerals may never be repeated in succession, and the M numeral may be repeated as many 2. times as necessary.
3. Only one smaller numeral can be placed to the left of another. For example, the number 18 is represented as XVIII but not as XIIX.
4. Only the I, X, or C can be used as subtractive numerals.
5. A subtractive I can only be used to the left of a V or X. Likewise a X can only appear to the left of a L or C, and a C can only be used to the
left of a D or M. For example, 49 must be written as XLIX and not as IL.

Your goal is to write a program which converts Roman numbers to base 10 integers.

输入:

The input to this problem will consist of the following:

A line with a single integer "N" (1 ≤ N ≤ 1000), where N indicates how many Roman numbers are to be converted.
A series of N lines of input with each line containing one Roman number. Each Roman number will be in the range of 1 to 10,000 (inclusive)
and will obey all of the rules laid out in the problem’s introduction.

输出:

The input to this problem will consist of the following:

A line with a single integer "N" (1 ≤ N ≤ 1000), where N indicates how many Roman numbers are to be converted.
A series of N lines of input with each line containing one Roman number. Each Roman number will be in the range of 1 to 10,000 (inclusive)
and will obey all of the rules laid out in the problem’s introduction.

样例输入:

3
IX
MMDCII
DXII

样例输出:

9
2602
512


题意:
给你n个星星的坐标,每个星星都有一个level,这个level只在星星左下方的星星的个数,包括边界,不包括它本身。。。

因为题目中是先按y从小到大,再按x从小到大排列,所以我们只需要考虑x从下到上就可以了,每次加入一个星星都计算sum(x)就是这颗星星的level,然后更新每个位置的值。
因为x可能为0,所以我们都把x+1。。

#include"stdio.h"
#include"string.h"
#define N 33000
int a[N];
int bit(int x)
{
	return x&(-x);
}
int sum(int x)
{
	int i;
	int ans=0;
	for(i=x;i>0;i-=bit(i))
		ans+=a[i];
	return ans;
}
void add(int x)
{
	int i;
	for(i=x;i<N;i+=bit(i))
		a[i]++;
}
int main()
{
	int i;
	int n;
	int A[N/2];
	while(scanf("%d",&n)!=-1)
	{
		memset(a,0,sizeof(a));
		memset(A,0,sizeof(A));
		int x,y;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			x++;
			A[sum(x)]++;
			add(x);
		}
		for(i=0;i<n;i++)
			printf("%d\n",A[i]);
	}
	return 0;
}
	

 


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。