AT2665 [AGC017B] Moderate Differences 题解

发布于 2021-05-01  115 次阅读


题意

题目链接

一共有 $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;
}

月流华 岁遗沙 万古吴钩出玉匣