题解 AT2665 【[AGC017B] Moderate Differences】

原题传送门

这题代码应该是蓝题里最短的一道了。

题解区有巨佬用了 \text{O(1)} 的做法，蒟蒻表示并不会。观察一下数据范围，\text{max(n)=5e5} ，可以接受 \text{O(n)} 甚至 \text{O(nlogn)} 的做法。所以直接挑简单的来就好啦。

本文的算法是 \text{O(n)} 的，可能并没有 \text{O(nlogn)} 做法。

这题的输出在众多构造题中是比较简单的。只需要输出是否有合法方案。考场上大家想不出转化可以考虑人品骗分。

任意相邻两个数的差的绝对值在 \text{[C,D]} 之间。

这玩意好像不是很好构造？

如果 \text{C=0} ，题目就变得简单很多了。

那么可不可以尝试把范围通过某种手段转化为 \text{[0,D-C]} 呢？

考虑每个数字相对于前面那个数字变化了多少，列出式子。

其中有的是加有的是减，不妨枚举加的有多少个。因为至少要加 \text{C} ，所以等式两边可以同时减去若干个个 \text{C} ，对于减同理。

这样，加和减的数字范围就变成了 \text{[0,D-C]} ，问题转化为等式左边能否弄出一个范围使得等式右边在这个范围内，贪心构造即可。

时间复杂度 \text{O(n)} 。

Code

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

long long n,a,b,c,d;

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
   //(2*(i+1)-n)*c表示有效的C
    for(int i=0;i<n-1;i++)//枚举加号
        if(b-(2*(i+1)-n)*c <= a+i*(d-c)+d && b-(2*(i+1)-n)*c >= a+(n-2-i)*(c-d)+c)//上下界，至于加D和加C是为了满足题目条件
            return printf("YES"),0;
    printf("NO");
//  fclose(stdin); fclose(stdout);
    return 0;
}

\text{Thank you for your reading!}

您的点赞和评论是对作者最大的支持！