| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 37 | 8 | . | O | . | O | O | Ø | . | . | O | . | O | Ø | Ø |
B
Solved by Forsaken.
线性基。
D
Solved by Henry.
假定一辆车堵住 $1$ 号车，求一个时间，取最大值即可。
E
Solved by XLor.
扣出最短路的边，求最小割。
注意加的是单向边。
F
UpSolved by XLor.
给定一个目标串 $s$，你现在只有一个空串去生成目标串，有两个操作，花费 $p$ 在串后面加一个字母，花费 $q$ 从当前串中复制一个子串加入到后面，求构造出 $s$ 的最小花费。
记 $dp[i]$ 表示构造出长度为 $i$ 的前缀的花费，两种转移，$dp[i-1]+p$ 和 $dp[j]+q$，其中 $j$ 满足 $s[j \dots i] $ 是 $s[1 \dots j-1]$ 的子串。
维护指针 $l$ 表示 $s[1 \dots l-1]$ 已经加入到了 SAM 内，以及 $s[l\dots r]$ 出现在 SAM 中的结点 $cur$。
匹配新的字母 $s[r]$ 时，注意保证 SAM 状态包含当前的匹配串，即匹配串长度为 $l$，需满足 $len[link[cur]] \lt l \le len[cur] $。
I
Solved by Henry.
贪心地序列自动机上匹配，判断加入新的字母时，能不能满足限制。
K
Solved by Forsaken.
筛。
L
UpSolved by Forsaken and XLor.
将操作转化为多项式形式，操作 $k$ 等价于给原串卷多项式 $\sum x^{ik}$。
显然，这和操作顺序无关，统计每种操作的次数，多项式 $exp$ 后做卷积即可。
注意到无需真正地去做 $exp$，可以推出组合数系数。