| rank | solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 96 | 9 | Ø | . | O | Ø | Ø | O | O | . | O | . | O | . | O |
A
UpSolved by XLor.
求母串 $s$ 和目标串 $t$ 的编辑距离，如果编辑距离不超过 $k$ 输出方案，否则输出不存在。
注意到本题，串长为 $10^6$ 但是 $k$ 只有 $1000$，因此 DP 时的复杂度尽量来自 $k$。
观察到结论：每次修改操作完成后，都会向后贪心地匹配。
假设母串匹配到位置 $x$，目标串匹配到 $y$，显然 $|x-y| \le k$。
因为，替换字符不会改变位置差，插入一个字符和删除字符只会导致位置 $+1$ 或者 $-1$。
因此，我们令 $f(i,j)$ 表示操作了 $i$ 次，位置差为 $j$ $(-i \le j \le i)$ 时，最大的匹配位置。
替换字符：将 $s[f(i, j) + 1]$ 替换为 $t[f(i, j) + 1 + j]$，$f(i, j) \to f(i+1, j)$；
插入字符：在 $f(i, j)$ 位置之后插入字符 $t[f(i, j) + 1 + j]$，$f(i, j) \to f(i + 1, j + 1)$；
删除字符：删除 $f(i, j) + 1$ 处的字符，$f(i, j) \to f(i + 1, j - 1)$。
注意：特判完全不需要修改的情况。
C
Solved by XLor and miaojie.
对于树，我们选所有叶子是最优的。
对于环，只能选 $3$ 个点。
基环树，环上至多选 $2$ 个连续的孤立点。
D
UpSolved by czswez.
竞赛图 SCC 缩点后，是一个链状的 DAG，每个点会向所有后缀连边。
SCC 缩点后，设置正向边边权为 $0$，反向边边权为权值本身。
从终点往起点跑一条最短路，将最短路经过的反边翻一下，就能产生一个大环。
E
UpSolved by XLor and czswez.
对于每个树，发射角度的正切值是一个区间，把区间解出来即可。
注意：本题二分时有很大的精度误差，输出的又是正切值。
F
Solved by XLor.
在 $26$ 进制下加 $1$，至多 $26$ 次个位一定会出现想要的数字。
G
Solved by XLor and czswez.
求环上 $k$ 染色后，相邻不同的方案数。令 $f(i)$ 表示大小为 $i$ 的环的方案数，$f(i) = k(k-1)^{i-1} - f(i - 1)$（容斥掉首尾相同的方案数）。
求树上 $k$ 染色后，相邻不同的方案数等于 $k(k-1)^{i-1}$。
仙人掌的结构就是环套树的类似物，圆方树上统计一下即可。
I
Solved by czswez and miaojie.
K
Solved by XLor and miaojie.
对每个线路建一个虚点，线路之间有交集的话，连一条长度为 $1$ 的边。
将删除倒过来变成加入，每次 Floyd 即可。
M
Solved by XLor.
将数组按权值排序后，注意到连续的一段的差距比较小一定比较优，那么可以首先二分出最多能保留多少个人。
但是，有可能会出现答案不是一个区间的情况，对于这种情况，一定是区间最左边那个数往左移动了一些，与整体区间分离，在二分标记一下即可。