Codeforces Round #715 (Div. 2) ABCDE 题解

这场感觉自己状态还可以。ABCE都是一发就过了。不过C题的DP想的时间稍微有点长就是了。

A. Average Height

题意

如果两个人的身高加起来能被2整除，则这两个人很上镜。现在给你$n$个人，问怎么排列，使相邻的人里面上镜的人尽可能多。

题解

奇数排一起，偶数排一起。

代码

B. TMT Document

题意

给你一个只包含M和T两种字母的串。问你整个串能不能写成若干个TMT的子序列。

题解

贪心。首先统计M的个数count_m。首先标记前count_m个T为第一个T。剩下的标记为第三个T。
扫描一次，如果遇到第一个T就count_first++。如果遇到M就count_first--;count_m--;count_last++;。如果遇到第三个T就count_last--。
过程中三个count都不能小于0。且最终这三个数都得是0。

代码

C. The Sports Festival

就是一个常见的在以区间为状态的DP。排完序后，就是看一段区间里面最小的和是多少就完事了。

D. Binary Literature

简单构造题。几乎一秒可以证明题目有解。而且基于证明几乎立刻可以给出解法。当时比赛的时候脑子抽了，没搞最长公共子序列。然后下来想了想，其实直接基于0和1的数目暴力做更简单。

E. Almost Sorted

其实没啥复杂的，主要分两部分，一部分是预处理长度为$n$的排列中所有的可能。第二部分是根据这个所有的排列，构造结果。逻辑比较绕，多想一会儿就能有。