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

A. Find The Array

题解

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

代码

Java

Submission #123581427 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #123618002 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #123582774 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #123617945 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #123584841 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #123617854 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Excellent Arrays

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

Educational Codeforces Round 111 Excellent Arrays 题解 (Java/C++)
题解首先,我们注意一下l和r的值域,$l\leq 1$,$r\geq n$。所以,对于前一半的a,可以让$a[i]=i+1$,对于后一半的a,可以让$a[i]=i-1$。因此显然有$F(a)=\left\lfloor \frac{m}{2} \right\rfloor \cdot \left\lceil \frac{m}{2} \right\rceil$。
点击上面链接,查看具体题解