XXI Open Cup named after E.V. Pankratiev. Grand Prix of Wroclaw

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.

将数组按权值排序后,注意到连续的一段的差距比较小一定比较优,那么可以首先二分出最多能保留多少个人。

但是,有可能会出现答案不是一个区间的情况,对于这种情况,一定是区间最左边那个数往左移动了一些,与整体区间分离,在二分标记一下即可。