题解十七：P16353 「Diligent-OI R3 A」说好不哭

· · 题解

【LGR-280-Div.2】洛谷 4 月月赛 III & Diligent-OI Round 3-P16353 「Diligent-OI R3 A」说好不哭。

## 思路 首先特判 $n=1$ 的情况。此时若 $x=y$ 输出为 `YES`，否则为 `NO`。 然后，我们根据 $x$、$y$ 的正负来讨论。分成 $4$ 种情况： ### 第一种：$x \ge y>0$，即 $x$、$y$ 均为正数 将满足条件的整数序列定义为 $Z$，子段和为 $x$ 的非空子段定义为 $X$，子段和为 $y$ 的非空子段定义为 $Y$。 首先，因为最小的 $y$ 都是正数，$Z$ 中所有元素一定全是正数。 此时，$Y$ 中一定只有一个元素，并且是 $Z$ 中最小的元素。（因为如果 $Y$ 中不止有一个元素，那么 $y$ 的值就是 $Y$ 中所有元素的和，则此时 $Y$ 中任意单个元素都小于 $y$，与 $y$ 作为最小子段和冲突。） 同理可证明，$X$ 一定包含了 $Z$ 的所有元素。 我们假设 $y$ 是固定的，那么合法的 $x$ 的范围是什么？根据我们前面的推断，$x$ 是所有元素之和，那么 $x$ 的最小值也就是每一个元素都最小的时候，即每一个元素都为 $y$ 的情况。 所以，当满足 $x \le y \times n$ 时，符合条件。 ### 第二种：$x=0$ 或 $y=0

如果 x=0，此时 y 一定是一个非正数，令序列第一项为 y，其余项均为 0 即可。

如果 y=0，此时 x 一定是一个非负数，令序列第一项为 x，其余项均为 0 即可。

所以这种情况一定符合条件。

第三种：x>0>y，即 x、y 异号

可以类比第二种，令序列第一项为 x，第二项为 y，其余项均为 0 即可。

所以这种情况也一定符合条件。

第四种：0>x \ge y，即 x、y 均为负数

将 x、y 去绝对值，交换，就变为了第一种情况。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,x,y;
bool work(){
    if(n==1)
        if(x!=y) return false;
        else return true;
    if(x>0 and y<0)
        return true;
    if(y==0 or x==0)
        return true;
    if(x<0){
        y=-y,x=-x;
        swap(x,y);
    }
    if(x<y*n) return false;
    return true;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>x>>y;
        if(!work()) cout<<"NO\n";
        else cout<<"YES\n";
    }
    return 0;
}// 434ms / 788.00KB / 406B C++98 O2
//求赞 QAQ

另外

欢迎接着看看月赛第二题的题解：《题解十八：「Diligent-OI R3 B」天际线》。