首页 > ACM题库 > HDU-杭电 > hdu 2305 WorstWeather Ever-分治-[解题报告]C++
2014
01-05

hdu 2305 WorstWeather Ever-分治-[解题报告]C++

WorstWeather Ever

问题描述 :

"Man, this year has the worst weather ever!", David said as he sat crouched in the small cave where we had sought shelter from yet another sudden rainstorm.
"Nuh-uh!", Diana immediately replied in her traditional know-it-all manner.
"Is too!", David countered cunningly. Terrific. Not only were we stuck in this cave, now we would have to listen to those two nagging for at least an hour. It was time to cut this discussion short.
"Big nuh-uh. In fact, 93 years ago it had already rained five times as much by this time of year."
"Duh", David capitulated, "so it’s the worst weather in 93 years then."
"Nuh-uh, this is actually the worst weather in 23 years.", Diana again broke in.
"Yeah, well, whatever", David sighed, "Who cares anyway?".
Well, dear contestants, you care, don’t you?
Your task is to, given information about the amount of rain during different years in the history of the universe, and a series of statements in the form "Year X had the most rain since year Y", determine whether these are true, might be true, or are false. We say that such a statement is true if:

The amount of rain during these two years and all years between them is known.

It rained at most as much during year X as it did during year Y.

For every year Z satisfying Y < Z < X, the amount of rain during year Z was less than the amount of rain during year X.

We say that such a statement might be true if there is an assignment of amounts of rain to years for which there is no information, such that the statement becomes true. We say that the statement is false otherwise.

输入:

The input will consist of several test cases, each consisting of two parts.
The first part begins with an integer 1 <= n <= 50000, indicating the number of different years for which there is information. Next follow n lines. The ith of these contains two integers -109 <= yi <= 109 and 1 <= ri <= 109 indicating that there was ri millilitres of rain during year yi (note that the amount of rain during a year can be any nonnegative integer, the limitation on ri is just a limitation on the input). You may assume that yi < yi+1 for 1 <= i < n.
The second part of a test case starts with an integer 1 <= m <= 10000, indicating the number of queries to process. The following m lines each contain two integers -109 <= Y < X <= 109 indicating two years.
There is a blank line between test cases. The input is terminated by a case where n = 0 and m = 0. This case should not be processed.
Technical note: Due to the size of the input, the use of cin/cout in C++ might be too slow in this problem. Use scanf/printf instead. In Java, make sure that both input and output is buffered.

输出:

The input will consist of several test cases, each consisting of two parts.
The first part begins with an integer 1 <= n <= 50000, indicating the number of different years for which there is information. Next follow n lines. The ith of these contains two integers -109 <= yi <= 109 and 1 <= ri <= 109 indicating that there was ri millilitres of rain during year yi (note that the amount of rain during a year can be any nonnegative integer, the limitation on ri is just a limitation on the input). You may assume that yi < yi+1 for 1 <= i < n.
The second part of a test case starts with an integer 1 <= m <= 10000, indicating the number of queries to process. The following m lines each contain two integers -109 <= Y < X <= 109 indicating two years.
There is a blank line between test cases. The input is terminated by a case where n = 0 and m = 0. This case should not be processed.
Technical note: Due to the size of the input, the use of cin/cout in C++ might be too slow in this problem. Use scanf/printf instead. In Java, make sure that both input and output is buffered.

样例输入:

4
2002 4920
2003 5901
2004 2832
2005 3890
2
2002 2005
2003 2005

3
1985 5782
1995 3048
2005 4890
2
1985 2005
2005 2015

0
0

样例输出:

false
true

maybe
maybe

//BZOJ1067; WorstWeather Ever (SCOI2007); RMQ-ST
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
#define N 100000
#define LOGN 18

int n, st[LOGN + 1][N + 1], q, x, y, d[N + 1], a[N + 1], ans, logn, Log[N + 1];

int query(int l, int r)
{
	if (l > r) return INT_MIN;
	int len = Log[r - l + 1];
	return std::max(st[len][l], st[len][r - (1 << len) + 1]);
}

void build()
{
	logn = Log[n];
	for (int i = 0; i <= n; ++i) st[0][i] = a[i];
	for (int i = 1; i <= logn; ++i)
		for (int j = 1; j <= n - (1 << i) + 1; ++j)
			st[i][j] = std::max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	
}
//lower_bound returns the first elements not less than x (>=)
inline int getpos(int x)
{ return std::lower_bound(d + 1, d + n + 1, x) - d; }

int main()
{
	for (int i = 1, j = 1, k = -1; i <= N; ++i)
		if (i == j) Log[i] = ++k, j <<= 1;
		else Log[i] = k;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d", d + i, a + i);
	scanf("%d", &q);
	build();
	while (q--)
	{
		scanf("%d%d", &x, &y);
		int l = getpos(x), r = getpos(y), m;
		bool lx = l <= n && d[l] == x, rx = r <= n && d[r] == y;
		if (!rx) --r;
		if (lx)
			if (rx)
			{
				m = query(l + 1, r - 1);
				if (a[l] < a[r]) ans = 0;
				else
					if (m < a[r])
						if (r - l == y - x) ans = 1;
						else ans = -1;
					else ans = 0;
			}
			else
			{
				m = query(l + 1, r);
				if (m < a[l]) ans = -1;
				else ans = 0;
			}
		else
			if (rx)
			{
				m = query(l, r - 1);
				if (m < a[r]) ans = -1;
				else ans = 0;
			}
			else ans = -1;
		if (ans == 1) printf("true\n");
		else if (!ans) printf("false\n");
		else printf("maybe\n");
	}
	return 0;
}

解题转自:http://blog.csdn.net/huzecong/article/details/8563362


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

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

  3. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n