Codeforces Round 646 (Div.2)

Posted on 2022-02-01 Edited on 2022-02-20

感受下来也就 $F$ 比较神仙, 发现自己对结论题更熟练了, $C$ 的结论直接秒掉, 但是真心觉得不难想.

觉得可以开始考虑 $\text{vp}$ $\text{div1}$ 了.

$\color{green}{\text{[EASY]}}$

其实做这题反应慢了, 看到了 $n$ 是 $1000$ , 询问次数是 $12$ 果断就应该猜想是二分.

不难发现, 二分肯定是找到最大值的下标, 这样除了最大值所在的集合, 其他的答案都是这个最大值.

最后一次询问询问最大值以外的集合就好了.

$\color{green}{\text{[EASY]}}$

这题比 $D$ 还显然.

首先考虑一个节点, 显然它子树里面的操作都可以由它的祖先来完成, 所以如果它的祖先里面有比它更便宜的, 那这个节点也就废了.

意识到这点之后贪心即可.

$\color{blue}{\text{[NORMAL]}}$

考的时候怎么可能想的出来这种神仙题嘛, 思维性太强了.

首先注意到一个操作的实质是把一个字母先前移动任意位值, 所以只要 $s$ 和 $t$ 中各个字母出现的次数相同, 就肯定有解.

我们要最小化选择的字符, 考虑 $dp$ , 设 $f_{i,j}$ 表示 $s$ 长度为 $i$ 的前缀加上后面若干个字母, 等于 $t$ 长度为 $j$ 的前缀的最小花费, 这里要求 $i \leqslant j$ , 那么答案即为 $f_{n,n}$ .

转移如下:

可以不让 $s_i$ 和 $t_j$ 匹配, 而是把 $s_i$ 向前移动, 花费 $1$ , 转移为 $f_{i,j} = f_{i-1,j}+1$ .
如果 $s_i = t_j$ , 那么可以直接令二者匹配, 转移为 $f_{i,j} = f_{i-1,j-1}$ .
如果 $i$ 后面的字符有多的 $t_j$ , 那么可以从 $i$ 后面抽出一个等于 $t_j$ 的字符放到这里与 $t_j$ 匹配, 转移为 $f_{i,j} = f_{i,j-1}$ , 需要注意的是, 这条转移会在之后的一次第一条转移被计算贡献, 所以这里不增加贡献.

三种转移取最小值, 时间复杂度 $\mathcal{O}(n^2)$ .