SWERC 2020

· · 个人记录

在学校开的，回家路上耽误了点时间，就造成了赛后 6s 过 J 的惨案。我谔谔。

A B C D E F G H I J K L M
+ - + + + + +2 +2 + *1 + +1 +2
0:09 0:44 0:52 0:11 0:25 2:11 1:08 1:18 0:34 3:34 4:10

A.Gratitude

模拟。

B. Rule 110

C. Safe Distance

二分答案。设二分的值是 x，把距离不超过 2x 的点之间连边，同时每个点和距离不超过 x 的边界连边，看一下有没有从左上边界到右下边界的路径，如果有说明答案 \ge x。

D. Jogging

设 0 到 u 的距离为 \mathrm{dis}(u)。显然一条边 (u,v) 能被用到当且仅当 2\cdot \min\{\mathrm{dis}(u),\mathrm{dis}(v)\}<U。

E. Cakes

模拟。

F. Mentors

先令 R\leftarrow N-R+1，并把条件改成父亲编号大于儿子。先 DP 出 n 个点的二叉树个数 f_n。设 g_n 为 n 个点且顶点 R 是叶子的二叉树个数，显然有

g_R=f_R\\ g_n=f_n-\sum_{j=2}^{n-R+1}g_{n-j+1}\cdot f_j\cdot {n-R\choose j-1},n>R

G. Decoration

建出基环树后 DFS 一遍。

H. Figurines

可持久化线段树模板题。

I. Emails

每轮会把距离 =2 的点对连边，因此若图的直径是 D，则 E=\lceil\log_2D\rceil。图的直径不好求，但由于输出 E 或 E+1 均可，只需要任意一个起点求出最短路的最大值 L，则 L\le D\le 2L，输出 \lceil\log_2 L\rceil+1 即可。

J. Daisy’s Mazes

对所有可能的 (u,v,c) 求出当前牌堆顶是 c（c=C 表示牌堆为空）且不能取走时，能否从 u 走到 v 且最后牌堆和初始时相同。再对所有可能的 (u,c) 求出当前牌堆顶是 c 且不能取走时，能否从 u 走到终点。求答案也类似，但由于要最小化初始的牌数，应该对所有 (u,c) 求出当前牌堆顶是 c 且能从 u 走到终点的条件下最少的牌数。这可以用 0-1 BFS 求出。

K. Unique Activities

可以用后缀自动机，但实际上二分答案 + 哈希更简单。

L. Restaurants

魔改版的稳定婚姻问题。

M. Fantasmagorie

显然这个形状就是环套环。我们可以从两个状态开始都变成最外层一圈一圈的样子，如下图，最后再拼起来。

.......
.#####.
.#...#.
.#...#.
.#...#.
.#####.
.......

变成这样也很简单，直接从外往里处理就行。但注意每次必须要从中间的某个格子扩展，且不能形成题目不允许的交叉状。一个方法是每次取能扩展的格子中到边界的距离最远的。