题解——ATCoder AtCoder Grand Contest 017 B

题面

B - Moderate Differences

Time limit : 2sec / Memory limit : 256MB

Score : 400 points

Problem Statement

There are N squares in a row. The leftmost square contains the integer A, and the rightmost contains the integer B. The other squares are empty.

Aohashi would like to fill the empty squares with integers so that the following condition is satisfied:

For any two adjacent squares, the (absolute) difference of the two integers in those squares is between C and D (inclusive).

As long as the condition is satisfied, it is allowed to use arbitrarily large or small integers to fill the squares. Determine whether it is possible to fill the squares under the condition.

Constraints

( 3≤N≤500000 )
( 0≤A≤10^{9} )
( 0≤B≤10^{9} )
( 0≤C≤D≤10^{9} )
All input values are integers.

Input

Input is given from Standard Input in the following format:

N A B C D

Output

Print YES if it is possible to fill the squares under the condition; print NO otherwise.

Sample Input 1

Copy

5 1 5 2 4

Sample Output 1

Copy

YES

For example, fill the squares with the following integers: 1, −1, 3, 7, 5, from left to right.

Sample Input 2

Copy

4 7 6 4 5

Sample Output 2

Copy

NO

Sample Input 3

Copy

48792 105960835 681218449 90629745 90632170

Sample Output 3

Copy

NO

Sample Input 4

Copy

491995 412925347 825318103 59999126 59999339

Sample Output 4

Copy

YES

题面大意（取自__stdcall）

有N个格子排成一排，最左边的里面写了数字A，最右边的写了数字B，中间的格子都是空的。你需要在中间的每个格子里填上一个数字，使得这个序列中，任意相邻两个数的差的绝对值在[C,D]之间。问是否存在这样一种可行的填数方案，输出YES或者NO。

题解

本题数据范围较大，显然直接暴力会出现TLE的惨案

因为输入数据量不多，显然可以考虑利用合理的构造解决这个问题

那么如何构造呢？

我首先考虑了构造一组加减，使得A的数字可以被继承到B旁边，在继承的过程中将A和B的值之间差的绝对值缩小到( left [ C ,D ight ] )，但是这个思路虽然想起来非常自然却不是很好实现

我们需要更加优美的解决方案

首先考虑题目的条件，题目条件显然是在指要填数，使得每个数都满足 ( C le left | x_{i+1} - x_{i} ight | le D,i in left [ 2,n ight ] )

那么观察这个简单的式子 ( x_{i+1}-x_{i} )

我们易得( sum (x_{i+1}-x_{i}) = x_{i}-x_{1} )，即( B-A )

观察到这一重要性质之后，不难发现我们的解一定与( B-A )有关

于是我们考虑一个简化的问题

有N个格子排成一排，最左边的里面写了数字A，最右边的写了数字B，中间的格子都是空的。你需要在中间的每个格子里填上一个数字，使得这个序列中，任意相邻两个数的差的绝对值在[0,D]之间。问是否存在这样一种可行的填数方案，输出YES或者NO。

这个问题失去了C的下界，是不是很好解决？

我们可以很容易的计算出( B-A )，所以只要在A到B的空间中，每个增加D或不增加，存在任意一个方案可以使最终( x_{n}-x_{n-1} )的值小于D即可

由此，只要让原问题变得无下限失去下限，问题就很好解决了呢

所以我们可以再考虑一种简单情况，如果所有的决策如果要改变大小C的值都只能加C，那么如何让这个问题失去下限？

很简单，把每个都减去C就好了

但问题是我们现在不知道到底这个决策中有多少个是+C，有多少个是-减c啊QWQ

这个时候就要枚举了

我们进行一些浅显的数学运算

假设现在存在( K )个满足条件( C le x_{i+1}-x_{i} le D )的式子，则因为总共要满足( n-1 )个连续的条件，所以一定存在( n-K-1 )个满足 ( -D le x_{i+1}-x_{i} le -C )的式子

由于( sum (x_{i+1}-x_{i}) = x_{i}-x_{1} = B-A )，我们把这些式子加和，可以得到

( K*C-(n-K-1)*d le B-A le K*D-(n-k-1)*C )的结论

我们只需要枚举K计算有无方案即可

扔代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
long long n,a,b,c,d;
int main(){
    while(scanf("%lld",&n)==1){
    scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
    for(int i=0;i<=n-1;i++){
        if((b-a)>=(i*c-(n-i-1)*d)&&(b-a)<=(i*d-(n-i-1)*c)){
            printf("YES");
            return 0;
            }
        }
    }
    printf("NO");
    return 0;    
}