Educational Codeforces Round 111 ABCD 题解 (Java/C++)

A. Find The Array

题解

贪心即可。按1，3，5，7……排即可，只要和大于s就停止。

代码

Java

C++

B. Maximum Cost Deletion

题解

首先，a的值不影响结果。因为最终结果里，a的部分一定是$a\cdot n$。于是问题就变成了b出现多少次。那么显然，如果b>0，我们就会希望拆成尽可能多的子串；如果b<0，我们就希望拆成尽可能少的子串。

对于b<0的情况，我们只需要统计出1和0分别有多少个连续的段即可，分别记为c1和c0。再记$c=\min{(c0,c1)}$。这种情况，需要操作c+1次。比如100111，c0=1，c1=2，c=1。需要操作2次，第一次拿掉0，第二次拿掉剩下的1。

最终的结果是$\min{[a\cdot n + b\cdot n, a\cdot n + b\cdot (c+1)]}$。

代码

Java

C++

C. Manhattan Subarrays

题解

首先，对于$d(p, r) = d(p, q) + d(q, r)$，我们可以认为，q点其实是再p和r之间。因此其实不妨设p<q<r。
当$a_p\leq a_q \leq a_r$ 时：$a_r-a_p+r-p=a_q-a_p+q-p+a_r-a_q+r-q$，这个等式是恒成立的。因此单增是不行的。
当$a_p\geq a_q \geq a_r$ 时：$a_p-a_r+r-p=a_p-a_q+q-p+a_q-a_r+r-q$，这个等式是恒成立的。因此减是不行的。

我们考虑构造这样一个串[a,b,c,d,e,...]，使得这个串是好的。我们依次构建：
不妨设b>a，于是有b>c。
接着我们可以发现d不能小于c，否则b,c,d会单调下降。d也不能大于b，否则a,b,d单调递增。于是b>d>c。
接着我们试着考虑e，显然立刻有b>e>c。同时我们注意到e不能大于d，否则c,d,e单增。e也不能小于d，否则b,d,e单减。因此不存在e。
综上子串的长度最多为4。

显然，长度为1和长度为2的子串一定满足要求。长度为3的子串只需要验证一下单调性即可。对于长度为4的子串，我们只需要验证一下a，d的值处于b和c之间即可。

代码

Java

C++

D. Excellent Arrays

这个题目首先需要发现其实$F(a)=\left\lfloor \frac{m}{2} \right\rfloor \cdot \left\lceil \frac{m}{2} \right\rceil$。
接着其实不难想到对于同一个排列，其可能性得数目只受其中两个特殊得元素的位置决定。于是可以得出一种$O(n^2)$的做法。
最后再通过一系列的变形和拆分来降低时间复杂度即可。