9
在审核作弊时，我发现很多人在“大大和2”这题使用了以下的乱搞做法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
乱搞做法 1：部分选择
* 指定一个数 lll（lll 在 100100100 以内）。
* 对于每个 iii，暴力判断所有 j(i≤j≤min{i+l,n})j(i\le j\le \min\{i+l,n\})j(i≤j≤min{i+l,n}) 是否满足 ∑k=ijAk≤maxk=ijAk\sum_{k=i}^j A_k\le \max_{k=i}^j A_k∑k=ij Ak ≤maxk=ij Ak 。
时间复杂度 O(nl)O(nl)O(nl)。
hack：
显然，我们只需要保证每个不符合题意的数的长度大于 lll 即可。
那么我们可以设计这样的数据：
将整个数据分为 mmm 段，每段的区间为 [k1,k2),[k2,k3),[k3,k4),...[km−1,km),[km,km][k_1,k_2),[k_2,k_3),[k_3,k_4),...[k_{m-1},k_{m}),[k_{m},k_{m}][k1 ,k2 ),[k2 ,k3 ),[k3 ,k4 ),...[km−1 ,km ),[km ,km ]。
然后我们将每段的第一个元素设置成任意一个大于前面一段除了第一个元素的所有元素之和的相反数，即 Akx>−∑i=kx−1kx−1AiA_{k_x}\gt -\sum_{i=k_{x-1}}^{k_{x}-1} A_iAkx >−∑i=kx−1 kx −1 Ai ，将后面的元素设置成任意负数，但是需要保证它们的和的相反数小于等于第一个元素，即 −∑i=kx+1kx+1−1≤Akx-\sum_{i={k_x+1}}^{k_{x+1}-1}\le A_{k_x}−∑i=kx +1kx+1 −1 ≤Akx 。
显然，这样所有段内都不会出现不符合题意的，而所有不符合题意的区间只能在段之间。
我们只需要保证每个段的长度大于 lll 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
乱搞做法 2：最大子段和 + ？？分治
* 求出以 iii 结尾的最大子段和。
* 当 Ai>0A_i\gt 0Ai >0 且最大子段和 >0\gt 0>0 时，返回 NO。
注意到在官方数据下，WA 的只有小数据，所以套个小数据暴力即可。
时间复杂度 O(n),O(n2)O(n),O(n^2)O(n),O(n2)。
毫无逻辑，但是能过。
经过对拍，我发现分段也可以解决这个问题。
将整个数据分为 mmm 段，每段的区间为 [k1,k2),[k2,k3),[k3,k4),...[km−1,km),[km,km][k_1,k_2),[k_2,k_3),[k_3,k_4),...[k_{m-1},k_{m}),[k_{m},k_{m}][k1 ,k2 ),[k2 ,k3 ),[k3 ,k4 ),...[km−1 ,km ),[km ,km ]。
然后我们将每段的第一个元素设置成前面一段除了第一个元素的所有元素之和，即 Akx=−∑i=kx−1kx−1AiA_{k_x}= -\sum_{i=k_{x-1}}^{k_{x}-1} A_iAkx =−∑i=kx−1 kx −1 Ai ，将后面的元素设置成任意负数，但是需要保证它们的和的相反数小于第一个元素，即 −∑i=kx+1kx+1−1<Akx-\sum_{i={k_x+1}}^{k_{x+1}-1}\lt A_{k_x}−∑i=kx +1kx+1 −1 <Akx 。
generator:
output:
做法 1 全部输出 YES，做法 2 全部输出 NO。
有帮助，赞一个