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 个商品，商品价格分别为 a1,a2,…,an.
接着给出 m 个优惠卷，对于第 i 个优惠卷，可以免费购买第 qi 贵的商品，问对于每一个优惠卷，最少需要多少钱才能买到所有商品
这题只需要对 a 数组排序，先统计出商品的总价格 sum，对于每个优惠卷，只需要用 sum 减去第 qi 大商品的价格即可
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≤c≤25)
由上可知，dp[1][n][26] 即为答案.
总时间复杂度为: O(n3∗26)
复杂度不是特别优秀…其实也有 O(n3) 的做法，不过 cf 的评测姬比较优秀，我这个做法也能通过
AC代码: F.cpp
G
To be continued…