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

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


A. Average Height

题意

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

题解

奇数排一起,偶数排一起。

代码

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

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。

代码

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

C. The Sports Festival

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

Codeforces Round #715 The Sports Festival - DP
题解首先对$a$排序。我们可以很容易的发现,任意一天,里面的成员一定是$a$中连续的一段。比如说$(1,2,4,6,7)$。如果我们第一天选了4,那么第二天必然在2,6中选一个。如果第二天选了6,那么第三天必然在2,7中选一个。

D. Binary Literature

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

Codeforces Round #715 Binary Literature - 构造
题解就很简单可以证明,$3n$的串一定可以得到。假设一个$2n$的串是00000,另一个是11111。于是我们可以立刻发现,第三个串无论怎么构造和前面两个串的差异的最大值就是$n$。于是公共部分一定可以拿出$n$个来,剩下小于等于$n$的差异直接补上去就完事。

E. Almost Sorted

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

Codeforces Round #715 Almost Sorted DP+构造
题解我是DP做的。虽然DP完了我发现应该是有什么数学性质。但不重要。总而言之就是通过DP得到长度为$l$的排列,总共有多少“几乎有序”排列。把$n$和$k$不断拆分成子DP。