Educational Codeforces Round 61 (Rated for Div. 2)
比赛链接: https://codeforces.com/contest/1132
比赛情况: 3/7(384)
被hack数: 1😔
总的来说，这次 edu 场应该还挺适合自己的，不过还是没怎么打好…做 C 题的时候复杂度没算好，T 了好几次，最后因为细节写岔了还被 hack 掉了，D 写了 45 分钟最后也没能调出来，挺可惜的orz
A
A 题是个超多人被 hack 的好题
题意就是给出 $cnt1$ 个 ‘((’, $cnt2$ 个 ‘()’, $cnt3$ 个 ‘)(’, $cnt4$ 个 ‘))‘，问是否能将它们排列成一个合法括号序列
对于 ‘()’ 来说，左右括号可以直接相互匹配，可以不考虑它们
对于 ‘)(’ 来说，我们将 $cnt3$ 个排列在一起，就是 ‘)()(…)(‘，只要前边有一个 ‘((‘，将其中一个 ‘(’ 与之匹配，我们就可以构成一个合法的括号序列
可以将最后一个 ‘)(’ 的 ‘(’ 补回给 ‘((‘，我们只需要再看 ‘((’ 的个数 是否与 ‘))’ 相等，就能判断是否能构成合法括号序列了
AC代码: A.cpp
B
题意就是给定 $n$ 个商品，商品价格分别为 $a_1,a_2,…,a_n$.
接着给出 $m$ 个优惠卷，对于第 $i$ 个优惠卷，可以免费购买第 $q_i$ 贵的商品，问对于每一个优惠卷，最少需要多少钱才能买到所有商品
这题只需要对 $a$ 数组排序，先统计出商品的总价格 $sum$，对于每个优惠卷，只需要用 $sum$ 减去第 $q_i$ 大商品的价格即可
AC代码: B.cpp
C
题意是给定 $q$ 个的染色区间，问从中选择 $q-2$ 个区间，最多有多少个位置能被染色
我们可以预先处理出每一个位置被多少个区间覆盖过，考虑枚举被删除的两个区间，看两个区间的重叠部分有多少个覆盖刚好两次的位置，未重叠部分有多少个覆盖刚好一次的位置，记为 $res$，可以用前缀和来实现这一过程(比赛的时候想太多了，还用了两个树状数组，实际上没这个必要)，用总的答案 $sum$ 减去 $res$ 即为该次枚举的结果
Tips: 比赛的时候考虑区间相对关系的时候，只考虑相离和相交两种，忘记考虑包含的情况…于是就GG了
AC代码: C.cpp
D
还在debug中…😟
E
To be continued…
F
题目给出一个只包含小写字母的字符串，每次允许消除连续相同的一段字符串，问最少需要几次能将字符串完全消除
考虑一个区间 $dp$，$dp[l][r][c]$ 表示 $l$ ~ $r$ 区间全部缩成字符 $c$ 的最少次数，特别定义 $dp[l][r][26]$ 为 $l$ ~ $r$ 区间完全消除的最少次数
枚举中间点 $k$，则有以下状态转移方程:
$dp[l][r][c]=min(dp[l][r][c],dp[l][k][c]+dp[k+1][r][c])$
$dp[l][r][c]=min(dp[l][r][c],dp[l][k][26]+dp[k+1][r][c])$
$dp[l][r][c]=min(dp[l][r][c],dp[l][k][c]+dp[k+1][r][26])$
$dp[l][r][26]=min(dp[l][r][26],dp[l][r][c]+1)(1 \le c \le 25)$
由上可知，$dp[1][n][26]$ 即为答案.
总时间复杂度为: $O(n^3*26)$
复杂度不是特别优秀…其实也有 $O(n^3)$ 的做法，不过 cf 的评测姬比较优秀，我这个做法也能通过
AC代码: F.cpp
G
To be continued…