GYM102391 2019-2020 XX Open Cup, Grand Prix of Korea 题解
jiangly
·
·
个人记录
A. 6789
模拟。
B. Bigger Sokoban 40k
观察下图：
.....#..
.##P.##.
.#.BBSS.
.#.BBSS.
.#....#.
.######.
........
玩家想要将箱子向右推，就不得不绕过整个网格。把尽可能多这样的模板连成一个环即可。
C. Cleaning
先求出所有的强连通分量并按拓扑序排序。
性质 1 按拓扑序依次加入所有强连通分量，在任意时刻所形成的图形都是若干个不相邻的矩形。
证明 若某个图形 S 不是矩形，则 S 外一定存在一个小格与 S 的至少两条边相邻，因此这个小格向 S 有至少一条边，与拓扑序相矛盾。
考虑在按拓扑序加入的过程中维护图的变化。在维护的过程中我们不保证图形是若干个不相邻的矩形，而可以是若干个矩形并排
当加入一个强连通分量 C 后，进行以下操作：
- 从 C 内部的所有矩形向 C 连边 (内部的矩形指 “包含 C 的最小矩形” 内的所有矩形)，如下图。有边的原因和 性质 1 类似。
- 处理上下左右四个方向的矩形，以上方为例。将上方紧贴着的所有矩形合并，并向 C 连边，如下图。注意如果所有矩形的下边界都是
D 则不连边。
要证明最后建出来的图和原图等价，我们需要证明以下性质：
性质 2 在任意时刻，对于并排的若干个矩形和任意垂直于并排方向的方向 (如果左右并排则为上下方向，反之亦然；如果是单个矩形则可以是任意方向)，要么矩形内的所有小格都能从该方向离开矩形，要么都不能。
证明 我们对于上文的几种情况分别归纳证明：
- 强连通分量 C 和其内部的矩形合并而形成的矩形。以上方为例。
- 若上边界的所有小格都在 C 内，如果所有小格都是
U，则都不能从上方离开；否则因为强连通，所有小格都能从上方离开。不在 C 内的小格可以先到 C 然后离开。
- 若上边界有一些小格在强连通分量外，设为矩形 R。若 R 能从上方离开但 C 不能，则 C 上边界的所有小格都是
U。因此从上边界的某个格子，可以任意左右移动，从而进入 R，与拓扑序矛盾。
-
容易发现最后建出的图是一棵树，且一个点的儿子被连成了几条链。在这个图上的必经点计数非常简单：即从起点跳到深度等于终点的祖先，它们一定有同一个父亲，再检查这两个点是否被一条链相连即可。
时间复杂度 O(NM\alpha(NM)+Q\log NM)。
D. Container
首先可以只考虑 2 的移动，因为当所有的 2 都复原之后，1 自然也复原了。把 s 和 t 中的 2 一一匹配后，设它们之间的距离为 d_1,\ldots,d_m，其中 m 是 2 的个数。则我们能得到一个答案的下界：\sum_{i=1}^d(\lfloor d _i/2\rfloor\cdot (C+4)+(d_i\bmod 2)\cdot(C+3))+(逆序对数)。这是因为我们可以通过翻转 112 (或 211) 来使一个 2 移动两步，通过翻转 12 (或 21) 来使一个 2 移动一步。而每有一个逆序对，就需要翻转一次 122 (或 221)，从而额外产生 1 的代价。上式的最小值可以用 O(N^2) 的 DP 求解。可以证明这个下界能够取到，并且可以用拓扑排序构造方案。时间复杂度 O(N^2)。
E. Dead Cacti Society
二分答案后 DP。时间复杂度 O((N+M)\log C)。
F. Hilbert's Hotel
前两种操作平凡。第三种操作只需从后往前找到所在的块并二分即可。时间复杂度 O(Q\log C)。
G. Lexicographically Minimum Walk
首先只保留能到达 T 的点，如果 S 不能到达 T 则无解。从 S 开始，每次贪心走 c 最小的边，如果在到达 T 之前出现环则会一直沿着环走。否则第一次到达 T 时的路径就是答案。时间复杂度 O(N+M)。
H. Maximizer
最大值显然能够在 [1,2,\ldots,N] 和 [N,N-1,\ldots,1] 取到。
当 N 是偶数时，取到最大值当且仅当每对 (a_i,b_i) 都由一个 \le N/2 的数和 >N/2 的数组成。证明：充分性显然；必要性：不妨设有一对 \le N/2 的，则必有另一对 >N/2 的，把两对数中的 a 交换后答案严格增加。
当 N 是奇数时，条件略有不同：每对 (a_i,b_i) 都由一个 \le (N+1)/2 和一个 \ge (N+1)/2 的数组成。证明类似。
有了上述定理，就可以把问题转化为从一个 01 序列变成另一个 01 序列的最小交换次数。把相同的数按顺序编号，又可以转化成逆序对数。用树状数组计算即可。时间复杂度 O(N\log N)。当然，只有 01 的情况，最小的交换次数就是两个数组对应的 1 的位置的差的绝对值之和，这样就能做到 O(N)。
I. Minimum Diameter Spanning Tree
枚举直径中点所在的边 (u,v)，我们想要最小化中点到所有点的最大距离。假设固定了 u 和 v 子树内分别的最远点 far_u 和 far_v，则每个点只需要满足 dis(x,u)\le dis(far_u,u) 或 dis(x,v)\le dis(far_v,v)。枚举 far_u，则 far_v 一定是 dis(x,u)>dis(far_u,u) 的点中 dis(x,v) 最大的点 x，这个可以对每个点的距离数组排序后均摊 O(1) 计算。时间复杂度 O(N^3)。
J. Parklife
答案显然是凸函数。由于给定的区间不相交，可以把它们建成一棵树。设 f(u,i) 表示 u 的子树内最多覆盖 i 层的最大价值。DP 的转移很简单：所有子树相加，并与 [0,V_u] 卷积。长链剖分，用 std::multiset 维护差分数组即可。时间复杂度 O(N\log N)。
K. Wind of Change
解法一 对两棵树点分治，分别枚举 i 在两棵点分树上的祖先 a_1,a_2，在这两个点的子树中找到 j\ne i 且 dis(T_1,a_1,j) 和 dis(T_2,a_2,j) 最大的点 j 即可。这样的点也可以用类似的方法对每对 (a_1,a_2) 预处理出来。为了避免排序或哈希，我们可以枚举 a_1，然后 DFS 它的子树，对子树中的每个点枚举 a_2，求出最近点，再次 DFS 统计答案。时间复杂度 O(N\log^2N)，空间复杂度为 ST 表 O(N\log N)。
解法二 对 T_1 点分治，求出在 T_2 上的虚树然后 DP。时间复杂度 O(N\log^2N)，也可离线基数排序优化成 O(N\log N)。