2000

1132F DP 字符串

题意:给定一个长度为 $n$ 的字符串 $s$,连续一段相同的字符可以一次消除。问最少需要消除多少次才能将整个字符串消除掉。

令$d(i, j)$ 表示 $s(i, j)$ 最少的消除次数,答案是 $d(0, n - 1)$。

$$\displaystyle d(i, j) = \min \{ 1 + d(i + 1, j), \min_{i+1 \le k \le j}^{s(i)=s(k)} \{ d(i + 1, k - 1) + d(k, j) \} \}$$

前者意义是 $s(i)$ 单独消除;后者意义是,因为 $s(i)$ 和 $s(k)$ 相同,所以消除了 $s(i+1, k -1)$ 后,消除 $s(k)$ 的同时可以将 $s(i)$ 也给删掉,也可以这样想,在最优的解法里,每一个长度大于1的连续消除串 $t$,除了 $t$ 最末尾的那个字符以外,其余字符都是由于删除了后一个字符(位置是上式的 $k$)而同时将自己(位置是上式的 $i$)删除。

时间 $O(n^3)$,空间 $O(n^2)$。

1800

1152C 数论 公倍数

题意:给定正整数 $a, b$(不妨设 $a \le b$),求在 $\text{lcm}(a + k, b + k)$ 尽量小的情况下,最小的非负整数 $k$。

$$\text{lcm}(a + k, b + k) = \frac{(a + k)(b + k)}{\gcd(a + k, b + k)}$$

由辗转相减 $\gcd(a + k, b + k) = \gcd(b + k, b - a)$,因此只要枚举 $b - a$ 的因子 $d$,再用 $d$ 来生成 $k$ 就行了。具体就是

$$d | (a+k) \Rightarrow (a + k) \text{ mod } d = 0 \Rightarrow k = (d - a \text{ mod } d) \text{ mod } d$$

时间 $O(\sqrt{b - a})$,空间 $O(1)$。

1153D 贪心 树

题意:$n$ 个点的树,每个点有个数字。非叶子节点有两个属性,若为 Max 则将孩子上的数字取 max 作为该节点的数字;Min 同理。该树有 $k$ 个叶子,你需要给叶子填入一个 1 到 $k$ 的数字,且每个数字只能用一次,最终使得根的值最大(根一定是 Max)。

假如我们要判断根是否能得到数字 $x$ ,只需判断是否存在一种方案,将 $x - 1$ 个叶子赋值为0,$k - x + 1$ 个叶子赋值为 1,使得根最终为 1。那么现在问题可以转化为,将叶子的 1 尽量减少,1 越少,$x$ 越大。

令 $d_x$ 表示节点 $x$ 在整个子树里,能得到的最少的 1。则对于叶子节点,$d = 1$。对于 Min 节点,$d_x = \sum_y d_y$;对于 Max 节点,$d_x = \min d_y$。答案是 $k - d_{root} + 1$。

时间 $O(n)$,空间 $O(n)$。

1700

1119D 二分 区间求交

题意:$n$ 个整数 $\{s_i\}$,$q$ 次询问,每次询问给出整数 $l, r$,求整数集合 $\{w | w \in [s_i + l, s_i + r]\}$ 的大小。

令 $w = r - l + 1$。若大小相邻的两数$s_i, s_j$的差$|s_i - s_j| < w$,那么对答案的贡献显然是 $|s_i - s_j|$。否则贡献是 $w$。因此将 $n - 1$ 个差 $|s_i - s_j|$ 求出来,然后排序,然后询问时二分即可。

时间 $O((n + q) \log n)$,空间 $O(n)$。

欢迎留言>_<

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据