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.
所有环边连向一个虚拟的油漆,跑一下最大匹配。