题意

题目链接。

一共有 $n$ 个格子，给定两个整数 $A,B$ 分别位于第 $1$ 和第 $n$ 格，中间有 $n-2$ 个空格。询问是否存在一种填数方案满足任意相邻两个数之差的绝对值在 $[C,D]$ 之间。

解析

考虑这 $n$ 个数之间有 $n-1$ 对差，因此题目等价于：

是否存在 $A+\sum\limits^{n-1}_{i=1} x_i=B,x_i\in[-D,-C]\cup[C,D]$。

尝试枚举 $x_i$ 中为正数的数量。假设有 $p$ 个 $x_i$ 为正，则有：

$A+\sum\limits_{i=1}^{p}x_i-\sum\limits_{i=p+1}^{i=n-1}x_i=B,x_i\in[C,D]$。

由于形似 $[0,a]$ 的区间容易求范围，我们考虑设法将 $[C,D]$ 转化为 $[0,D-C]$。将两边式子同时减去 $p$ 个 $C$，再同时加上 $n-1-p$ 个 $C$，又有：

$A+\sum\limits_{i=1}^{p}x_i-\sum\limits_{i=p+1}^{i=n-1}x_i=B+(n-1-2\times p)\times C ,x_i\in[0,D-C]$。

对于这个式子，左边的最大值为 $A+p\times(D-C)$，最小值为 $A-(n-1-p)\times(D-C)$，依次枚举正数的数量后，分别判断变形后的 $B$ 是否在该区间内即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,A,B,C,D,Max,Min;
signed main(){
    scanf("%lld%lld%lld%lld%lld",&n,&A,&B,&C,&D);
    for(int i=0;i<=n-1;i++){
        int tB=B+C*(n-1-2*i);//B 变形
        int Max=A+i*(D-C);//最大值
        int Min=A-(n-1-i)*(D-C);//最小值
        if(tB>=Min&&tB<=Max){//是否在区间内
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}