题解 P3910 【纪念邮票】

2018-05-01 13:40:25


这题数据千万别看错,是10e9,不是109!

我们可以枚举这个数列(邮票序列)的长度,然后判断该长度是否有可行解。若有,则输出。

具体看代码注释 贴上代码:

#include <bits/stdc++.h>
using namespace std;
int n,m,len;
int main ()
{
    scanf("%d%d",&n,&m);
    len = sqrt(2 * m) + 10;
    while ((1 + len) * len / 2 >= m) --len;
    ++len;//会多减
    for (int i = len;i > 0;i--)
    {
        if (i % 2) //分奇数偶数讨论
        {
            int mid = m / i;//对于长(项数)为奇数:如果确实存在这个总和为m等差数列的话,
            //那么mid是它中间的数
            if (mid * i != m) continue;//数列存在吗???
            int le = mid - i / 2,ri = mid + i / 2;//计算左右值
            if (le < 0 || ri > n) continue;//千万别超限
            printf("[%d,%d]\n",le,ri);
        }
        else
        {
            int mid = m / i;//对于项数为偶数:mid,mid + 1为数列中间两个数
            if ((m / i * 2 + 1) * (i / 2) != m) continue;//判断
            int le = mid - i / 2 + 1,ri = mid + i / 2;//同上
            if (le < 0 || ri > n) continue;
            printf("[%d,%d]\n",le,ri);
        }
    }
    return 0;
}

最后,它是怎么做到按a的顺序输出的呢?

关键点就在于循环!