2019 杭电多校训练第 1 场

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$，可以推出组合数系数。