HDOJ 2058 The sum problem

这题说难也难,说不难也不难,就是特别容易超时。

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2058

思路:

暴力肯定不行,这题要结合数学公式,多项式的和,但是必须的从序列长度d如何,若从起始值入手,一样会TLE。
其次要注意:题目有这么一句话:
print a blank line after each test case.
结果我考虑复杂了,以为最后一组数据不能有空行,搞的一直PE。 [s:3]
先给出一个纯暴力的TLE的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 // Author: Tanky Woo
// HDOJ 2058
 
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int sum;
int N, M;
int main()
{
	while(scanf("%d %d", &N, &M) && (M||N))
	{
		for(int i=1; i<=M && i<=N; ++i)
		{
			sum = 0;
			for(int j=i; j<=M && i<=N; ++j)
			{
				if(sum<M)
					sum += j;
				if(sum == M)
				{
					printf("[%d,%d]\n", i, j);
					break;
				}
				if(sum > M)
					break;
			}
		}
		printf("\n");
	}
	return 0;
}

下面这个虽然优化了,但是仍然TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 #include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int sum;
int N, M;
int main()
{
	int flag = 0;
	while(scanf("%d %d", &N, &M) && (M||N))
	{
		if(flag)
			printf("\n");
		flag = 1;
		for(int i=0; i<=M; ++i)
		{
			// 起始a+1..a+d
			double temp = sqrt(double((2*i+1)*(2*i+1)+8*M))/2.0 - 0.5;
			if(fabs(temp-(int)temp) < 1e-6)
			{
				printf("[%d,%d]\n", i+1,(int)temp);
			}
		}
	}
	return 0;
}

上面这个方法,结合了数学公式。但是仍然超时,这是因为N和M都太大了。
观察a+1,a+2…a+d
全部相加等于M
即(a+1+a+d)*d/2 = M
这里d是平方,我们可以从长度d入手,这样就能把范围由M转换成M^1/2 [s:20]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 // Accepted 2058 15MS 212K 426 B C++ Tanky Woo 
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int N, M;
int main()
{
	int flag = 0;
	while(scanf("%d %d", &N, &M) && (M||N))
	{
		int i;
		int len = int(sqrt(M*2.0));  // ①
		for(i=len; i>=1; --i)
		{
			int temp = M-(i*i+i)/2;   // ②
			if(temp%i == 0)
				printf("[%d,%d]\n", temp/i+1, temp/i+i);
		}
		printf("\n");
	}
	return 0;
}

这里把①和②解释下:
①:当a+1,a+2…a+3相加等于M时,即
(a+1+a+d)*d/2 = M
而a最小是0,所以(d+1)*d/2=M时d去最大值,就是这步把时间复杂度减小的。
d就是sqrt(2*M)

②:(a+1+a+d)*d/2 = M
所以a*d + (d+1)*d/2 = M(先前漏掉了d。经syx兄提醒,已改正)
所以要使等式成立,M-(d+1)/2必须是d的倍数。

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 2058 The sum problem》有4个想法

  1. ②:(a+1+a+d)*d/2 = M
    所以a*d + (d+1)/2 = M
    所以要使等式成立,M-(d+1)/2必须是d的倍数。

    写漏了一个d!

    a*d + (d+1)*d/2 = M

发表评论

电子邮件地址不会被公开。 必填项已用*标注