P16353 「Diligent-OI R3 A」说好不哭Link: https://www.luogu.com.cn/problem/P16353题目描述小 C 想知道是否存在一个长度为n nn的整数序列满足最大非空子段和为x xx最小非空子段和为y yy。若存在输出YES否则输出NO。请注意若序列b bb可以通过将序列a aa分别在前面和后面删除若干个元素可以为 0 个得到则定义b bb是a aa的子段。输入格式本题有多组测试数据。输入的第一行包含一个整数T TT表示测试数据的组数。接下来包含T TT组数据对于每组数据输入一行包含三个整数n , x , y n,x,yn,x,y。输出格式对于每组数据输出一行YES或NO表示是否存在满足条件的序列。输入输出样例 #1输入 #17 5 5 0 2 3 1 2 5 3 1 5 -1 3 -1 -2 3 -1 -3 4 3 -4输出 #1YES YES NO NO NO YES YES说明/提示【样例解释】第一组数据可构造出{ 1 , 2 , 1 , 1 , 0 } \{1,2,1,1,0\}{1,2,1,1,0}。第二组数据可构造出{ 2 , 1 } \{2,1\}{2,1}。可以证明第三、四、五组数据无法构造出满足题意的序列。第六组数据可构造出{ − 1 , − 1 , − 1 } \{-1,-1,-1\}{−1,−1,−1}。第七组数据可构造出{ 1 , 2 , − 2 , − 2 } \{1,2,-2,-2\}{1,2,−2,−2}。【数据范围】测试点编号分值T ≤ T \leT≤n ≤ n \len≤∣ x ∣ ≤ \vert x\vert \le∣x∣≤∣ y ∣ ≤ \vert y\vert \le∣y∣≤特殊性质1 1110 101010 5 10^51051 1110 9 10^910910 9 10^9109无2 2220 202010 10105 555 555 55有3 3320 202010 5 10^51052 2210 9 10^910910 9 10^9109无4 4420 2020^10 9 10^9109^^有5 5530 3030^^^^无特殊性质x , y x,yx,y均为非负整数。对于所有数据保证1 ≤ T ≤ 10 5 1 \le T \le 10^51≤T≤1051 ≤ n ≤ 10 9 1\le n\le 10^91≤n≤109− 10 9 ≤ y ≤ x ≤ 10 9 -10^{9}\le y \le x\le 10^{9}−109≤y≤x≤109。Solution1. 题意输入三个数n , x , y n,x,yn,x,y判断是否存在一个长度为n nn的整数序列满足最大非空子段和为x xx最小非空子段和为y yy。2. 分析比较入门的构造类题目。按n nn的大小以及x , y x, yx,y的符号进行分类。1当n 1 n 1n1时序列只有一个元素a 1 a_1a1​。此时最大非空子段和与最小非空子段和都等于a 1 a_1a1​。此时充要条件直接就是x y xyxy。2当n ≥ 2 n \ge 2n≥2时要判断是否存在这样的子段根据x , y x, yx,y的符号分为三种情况。x ≥ 0 x \ge 0x≥0且y ≤ 0 y \le 0y≤0此时令序列为{ x , y , 0 , 0 , … , 0 } \{x, y, 0, 0, \dots, 0\}{x,y,0,0,…,0}。如此一来由于y ≤ 0 ≤ x y \le 0 \le xy≤0≤x任意子段和必然落在[ y , x ] [y, x][y,x]区间内。包含x xx的子段最大值为x xx包含y yy的子段最小值为y yy。中间的0 00不会改变最值。x ≥ y ≥ 0 x \ge y\ge 0x≥y≥0此时所有子段和均为正说明序列中不能有非正数否则会出现≤ 0 \le 0≤0的子段和与最小值为正矛盾。对于全正序列最大子段和一定是整个序列的总和加正数只会变大。最小子段和一定是最小的单个元素任意更长子段和都大于其中任一元素。因此必须满足总和为x xx且每个元素≥ y \ge y≥y。即x ≥ n ⋅ y x \ge n \cdot yx≥n⋅y。此时的充要条件是x ≥ n y x\ge nyx≥ny。构造方法是a 1 x − ( n − 1 ) y a_1 x - (n-1)ya1​x−(n−1)y其余a i y a_i yai​y。由条件知a 1 ≥ y a_1 \ge ya1​≥y所有元素为正满足题意。x 0 x 0x0此时必有y ≤ x 0 y \le x 0y≤x0全负情况此时所有子段和均为负说明序列中不能有非负数。对于全负序列最小子段和一定是整个序列的总和加负数只会变小最大子段和一定是最大的单个元素即绝对值最小的负数。因此必须满足总和为y yy且每个元素≤ x \le x≤x。即y ≤ n ⋅ x y \le n \cdot xy≤n⋅x。此时的充要条件是y ≤ n x y\le nxy≤nx。构造方法是a 1 y − ( n − 1 ) x a_1 y - (n-1)xa1​y−(n−1)x其余a i x a_i xai​x。由条件知a 1 ≤ x a_1 \le xa1​≤x所有元素为负满足题意。汇总以上结果我们直接上伪代码。伪代码对每组数据( n , x , y ) (n, x, y)(n,x,y)若n 1判断是不是x y若n 2若x 0 and y 0直接输出YES若x 0 and y 0判断x n * y若x 0判断y n * x最后单组数据直接就是O ( 1 ) O(1)O(1)的常数复杂度了。3. 代码C#usingSystem;classP16353{staticvoidSolve(){stringlineConsole.ReadLine();intTConvert.ToInt32(line);while(T--0){string[]inputsConsole.ReadLine().Split();longnlong.Parse(inputs[0]);longxlong.Parse(inputs[1]);longylong.Parse(inputs[2]);boolokfalse;if(n1){ok(xy);}else{if(x0y0){oktrue;}elseif(x0y0){ok(xn*y);}else{ok(yn*x);}}Console.WriteLine(ok?YES:NO);}}staticvoidMain(){Solve();}}C#includebits/stdc.husingnamespacestd;usinglllonglong;voidsolve(){intT;if(!(cinT))return;while(T--){ll n,x,y;cinnxy;boolokfalse;if(n1){ok(xy);}else{if(x0y0){oktrue;}elseif(x0y0){ok(xn*y);}else{ok(yn*x);}}cout(ok?YES\n:NO\n);}}intmain(){solve();return0;}