【Codeforces】1120 Round #543 Div. 1 B-F简要题解_e. the very same munchhausen

作者：小小林熬夜学编程 | 2024-02-06 21:40:34

踩

e. the very same munchhausen

传送门:CF1120

B.Once in a casino

一道贪心坑了好多人啊(包括我)。

首先存在以下情况是无解的：

不考虑 $0 - 1, 9 + 1$ 的合法性，贪心依次让 $1 - (n - 1)$ ，即 $1,b_1-a_1),(2,b_2-(a_2+(b_1-a_1)))$ ( $(i, j)$ 表示将 $a_i,a_{i+1}$ 同时 $+ j$ )。
$a_n$ 是不能单独操作的，若 $a_n\neq b_n$ ，则必然无解。

可以证明除了上面的情况以外一定有解(证明略)：
每次贪心操作最前可以操作的位置，步数一定是最少的。

C.Compress String

SAM DP裸题，不解释。

D.Power Tree

转化一下题目的要求(设叶子结点个数为 $k$ )：，选择 $k$ 个结点，使得每个结点子树内不经过其它选择的结点所能到达的叶结点都是唯一且各不相同的，要求最小化 $\sum C_i$

考虑 $f [i] [0 / 1]$ 表示以 $i$ 为根的子树还剩 $0 / 1$ 个叶子结点没被覆盖的最优答案。

答案即 $f [1] [0]$

如何寻找哪些点可能出现在最优点内呢？似乎可以再DP一遍。

考虑从状态 $g [1] [0]$ 出发进行 $b f s$ (设 $sum_u=\sum \limits_{v\in son_u}f[v][0]$ )：

状态

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/64662