Codeforces Round #551 (Div. 2) 解题报告

题目链接:Codeforces Round #551 (Div. 2)

好久不打又变菜了==

A- Serval and Bus

对于每个车枚举它会在哪些时刻出现,标进vis数组。

B – Serval and Toy Bricks

按照$a_{ij} = \min \{ r_i, c_j \} $构造。

C – Serval and Parenthesis Sequence

对于$s$的所有严格前缀,满足左括号数恒大于右括号数。运用贪心的思想,使得前缀中的左括号数量尽可能地大,也就是优先排左括号在前面。我们注意到$n$为奇数的时候肯定是无解的,$n$为偶数的时候左括号和右括号各有$\frac{n}{2}$个,按照此规则可以构造出完整的$s$。最终还需要检查一下括号匹配是否合法,是否有严格前缀正好可以合法匹配的情况。

D – Serval and Rooted Tree

首先考虑$\min$操作,假设$u$的所有子树的值的集合是$\{ 2,5,6 \}$,那么对$u$节点取$\min$之后得到$2$,$5,6$被损失掉了。我们发现只要又$\min$操作就会损失一些比决策结果更大的数,这对我们是不利的——因为我们总希望每个被决策出来的值尽量地大,这就需要我们少损失一些比较大的数。考虑$\max$操作,选择损失掉最少的子树。dfs后最终根节点的值就是所有损失掉的比较大的数,例如总共8个数,损失3个数,即损失了6、7、8。所以用$k$减去所有损失就是答案。

E, F

待填坑。

说点什么

avatar
50
  Subscribe  
提醒