2022 年 10 月做题记录

whk 忙。随缘更新。

10.4

P4600

题目说要求给出字符串中某两个字符串前缀的最长公共的在给出字符串中作为前缀出现过的后缀。

那显然是 fail 树上 LCA。

CF917D

喜提最劣解

观察到我们把原树边的边权赋为 $x$，其他边权赋为 $1$ 后，跑一遍矩阵树，得到一个多项式 $f(x)$，答案就变成了 $[x^k]f(x)$。

显然不能暴力上多项式。那就代 $n$ 个点进 $x$ 里得到 $n$ 个点值然后插出来系数就行了。复杂度 $O(n^4)$。

这题还有神仙组合计数做法，复杂度是 $O(n^2)$ 的，但是还不会。

P5319

比较套路吧。

首先看到 $\prod$，考虑取对数。

然后就变成了最大化 $\frac{\sum_{i=1}^{c}\ln V_i}{c}$ 的形式，考虑分数规划。

二分一个最大值 mid，然后判断能否满足

$$\frac{\sum_{i=1}^{c}\ln V_i}{c} > mid$$

即

$$\sum_{i=1}^{c}\ln V_i - c\cdot mid > 0$$

也就是物品价值变成 $\ln V_i - mid$ 之后的最大价值和。

就是裸的 AC 自动机上 dp。

10.8

CF721C

简单 DAG 上 dp。我现在只会做这种弱智题了。

P4550

简单期望 dp。我现在只会做这种弱智题了。

10.10

P2893

首先显然有一种暴力 dp，但是状态数实在是太多了。

考虑优化状态数！！！（这种时候不要想一些歪门邪道，一定是状态数的问题）

然后便可以观察到 $b$ 中出现的数一定在 $a$ 中出现过。我现在的思维只能支撑我到发现“需要优化状态数”这件事之后才会去找性质。

然后状态就平方了，就做完了。

但是这题还有加强版和更优的解法，还没想。

upd on 2022.10.?：可以反悔贪心，可以 slope trick。