| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 32 | 11 | O | O | O | Ø | O | O | O | O | . | O | O | O |
A
Solved by Henry.
B
Solved by Henry and XLor.
树形 dp。
每个结点 $u$ 分成 $3$ 个状态，$u$ 被一条拐弯的路径覆盖，$u$ 往上延伸，分成是否允许中断两种。
注意最后两个状态的区别，考虑一种情况， $u$ 是一个路径的最浅端点，儿子 $v$ 也是他的路径最浅端点，这样两条路径需要合并。
转移时，无法进行除法，预处理前后缀和即可。
C
Solved by Henry.
D
UpSolved by XLor.
枚举每个询问的转折点，拆成 $\sum |s|$ 个询问，每个询问点对应正向 Trie 树和反向 Trie 树的一个点对。
从左到右，预处理每个横行的正向 Trie 图状态；从下往上，预处理每个竖列的反向 Trie 图状态。因此，每个点作为一个交点的状态也是一个点点对。
对每个询问，就是在正向的 fail 树上，询问子树内有多少点，在反向 fail 树上也在其子树内。离线所有询问，二维数点即可。
E
Solved by Henry.
F
Solved by Forsaken and Henry.
G
Solved by Forsaken and Henry.
H
Solved by Forsaken.
J
Solved by Forsaken.
dp 一下前 $i$ 个有 $j$ 个石头，最多能用多少个 $1 \times 2$ 的石头。
枚举一下用了多少个石头，讨论一下，可以 $O(1)$ 算出最小花费。
K
Solved by Forsaken, Henry and XLor.
转移是一个矩阵，更新是矩阵的两个对角线分别交换。
L
Solved by Henry and XLor.
所有环边连向一个虚拟的油漆，跑一下最大匹配。