| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 63 | 7 | O | . | . | . | O | O | Ø | . | Ø | O | . | O |
A
Solved by miaojie and XLor (01:07:11).
每次选择一个极大的连通块，全部减一。
考虑时光倒转，随着权值增加，在图上连边。
E
Solved by XLor (01:14:30).
注意到只要二次函数极小值附近的点值有效，将所有关键点抠出来，跑最小费用流。
由于流量都是 $1$，输出每轮增广的费用即可。
F
Solved by ytriayggg (01:51:33).
G
UpSolved by ytriayggg and XLor.
考虑二分直径的长度，令 $dp(u,i)$ 表示子树 $u$ 内选择 $k$ 条边的所有方案中最长边的最小值。$dp$ 合并时只在不超过直径长度时才合并。
I
UpSolved by XLor.
降智题。
首先，观察发现对于每行发射一条光线，第 $1$ 次碰到路径是进入多边形，第 $2$ 次是出来，以此类推。
如果多边形形状很奇怪，那么一定会花费很多输入量，那么最坏情况下就是花费 $4n$ 的输入量，使用 $O(n^2)$ 的算法解决，因此总体的时间复杂度是 $O(\frac{n\sum |s|}{4})$。
L
Solved by XLor (02:02:52).
对于每次询问，不妨令询问串更长，那么就是尽量要在询问串中找到和 $B$ 串的最长公共子序列。
考虑使用序列自动机，令 $dp(i,j)$ 表示 $B$ 串匹配了前 $i$ 个位置，公共子序列长度为 $j$ 的最左端点。