Blog·Tanky WooABOUTRSS

HDOJ 2058 The sum problem

31 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

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

题目地址:

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

思路:

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

 // Author: Tanky Woo
// HDOJ 2058

#include 
#include 
#include 
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)
                    break;
            }
        }
        printf("\n");
    }
    return 0;
} 

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

 #include 
#include 
#include 
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]

 // Accepted 2058 15MS 212K 426 B C++ Tanky Woo 
#include 
#include 
#include 
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 所以ad + (d+1)*d/2 = M(先前漏掉了d。经syx兄提醒,已改正) 所以要使等式成立,M-(d+1)/2必须是d的倍数。