Educational Codeforces Round 147

离校队选拔还不知道有多久，还是准备起来吧，之前太摆了

Source

Codeforces Global Round 23

A - Matching

朴实无华的组合题，但是第一发忘记删调试了，喜提 penalty

Code

1821 A

B - Sort the Subarray

我们找到第一处和最后一处 $a_i \neq a’_i$ 的位置 $l_0, r_0$，可知 $[l_0, r_0]$ 一定是符合要求的一个 subarray

接下来两边扩展即可

Code

1821 B

C - Tear It Apart

我们总能将一段长度为 $l$ 的区间每次砍掉一半的元素，因此将一个区间完全删掉所需最小次数为 $1+\log_2 l$

枚举保留哪种字母，该字母将原来的字符串分割为一些子串。保留该字母的答案即为 $1+\log_2 l_{\max}$，其中 $l_{\max}$ 为最长子串长度

Code

1821 C

D - Black Cells

注意到，只有长度为 1 的区间才可能不会被反转。区间长度大于 1 的我们一定会选择将其反转

打比赛时候的思路是先反转开头 $k$ 个，然后将已反转的长度为 1 的区间逐个取消反转，同时末端点向后拓展。但实现非常丑陋，根本不知道哪组数据出错，调到最后心态爆炸了

像 editorial 一样写成明了的数学表达式才是好文明

Code

1821 D

Warnings

提交之前记得删掉调试语句！！！