2023 年 syzx 春季训练 4
phtniit
·
·
个人记录
A: gym104128a
给定长宽为 n * m 的矩阵里，有且仅有一个格子是坑，其他格子分别站立了一只袋鼠。
有一个操作序列 S。
* $U$：表示所有袋鼠向上移动一格，移动以后离开上边沿，或者掉落到坑里的袋鼠将永远消失；
* $D$：表示所有袋鼠向下移动一格，移动以后离开下边沿，或者掉落到坑里的袋鼠将永远消失；
* $L$：表示所有袋鼠向左移动一格，移动以后离开左边沿，或者掉落到坑里的袋鼠将永远消失；
* $R$：表示所有袋鼠向右移动一格，移动以后离开右边沿，或者掉落到坑里的袋鼠将永远消失。
问有多少种放这个**坑**的位置，可以使得所有操作结束后，矩阵里恰好剩下 $k$ 只袋鼠。
## 题解
对于这个序列 $S$，我们显然可以得到一个小矩阵 $(u1,v1,u2,v2)$，只有这个矩阵内的袋鼠才**有可能不从边沿离开**。
朴素的思路是：考虑枚举坑的位置，以及这个坑有可能坑掉小矩阵内的多少只袋鼠。
对于一个指定的坑，其对小矩阵的伤害，可以这么思考：
* 当我们向右移动袋鼠的时候，等价于保持袋鼠静止，坑向左移动（其他方向的运动也相同）；
* 坑对小矩阵的伤害，等于坑的移动过程中进入到小矩阵内的次数。
对于指定的坑，和给定的序列，我们可以得到过程中坑的所有位置，我们要考虑的是有多少个位置落在小矩阵内，这是一个二维数点的问题，可以使用树状数组或者前缀和处理。
对于不同的坑，他们的移动序列是相似的（无非是有一点相对于初始位置的偏移量），所以我们可以考虑这个小矩阵相对坑的位置的偏移矩阵内的点的个数。
# [B: gym104114i](https://vjudge.net/problem/Gym-104114I)
给定长度为 n 的非负整数序列 a[]，每次可以选择相邻的 2 个不同时为 0 的元素 $a_i$ 和 $a_{i+1}$，更新 $a_i = a_{i+1} = max(a_i, a_{i+1}) - 1$。
问最少几次操作可以使数组变为 0。
## 题解
我们考虑极端情形：
* 如果 $a_i$ 仅有 1 段长度为 len 的 1，其余都是元素 0 的时候，答案应该是 $\lceil\frac{len}{2}\rceil$。
考虑特殊情形：
* 如果 $a_i$ 仅由 0 和 1 组成，答案应该是 $\sum{\lceil\frac{len_i}{2}\rceil}$，其中 $len_i$ 表示第 i 段连续的 1 的长度。
考虑更一般的情形，$a_i$ 的值域是 [0, +inf]，则答案是 $\sum_{1<=v<=+inf}\sum{\lceil\frac{len_{v,i}}{2}\rceil}$，其中 $len_{v,i}$ 表示第 i 段连续的值域**大于等于 $v$ 的长度**。
# [C: cf1019c](https://vjudge.net/problem/CodeForces-1019C)
给定一个有向图，要求找出一个点集 $Q$ 满足：
* 任意两个在集合中的点 $x$ 和 $y$，之间没有边相连；
* 对于不在集合中的点 $z$，至少存在一个集合中的点，在两步内可以到达 $z$。
## 题解
1 到 n 正向扫一遍，如果 $u$ 没有被标记**暂时选中**，则标记 $u$ 出发能一步到达的所有**没有标记的邻点 $v$ 不需要选**，并且把 $u$ 标记为**暂时选中**。
但上述**暂时选中**的结合 $\{u\}$ 未必是合法的，因为可能有后来选中的 $u_2$ 其实是能一步到达之前选中的某个 $u_1$ 的。
为了避免这种情况，我们从 n 到 1 反向扫一遍，如果 $v$ 没有被标记**不需要选**，则标记 $v$ 出发能一步到达的所有邻点 $u$ 不需要选。
# [D: gym104128j](https://vjudge.net/problem/Gym-104128J)
给定 $n$（是偶数） 个节点的一张图，每个节点上有一个元素 $a_i$。
两个节点有边，当且仅当 $|a_i - a_j| = |i - j|$。
求这个无向图的一个完美匹配，或者宣称不存在这样的完美匹配。
## 题解
我们可以构建一个二分图，其中左边的节点是 $\{a_i - i\}$，右边的节点是 $\{a_j+j\}$ 们，这个二分图在 $\{a_k - k\}$ 和 $\{a_k + k\}$ 的点对上有一条边。
现在我们需要把这个二分图拆成若干条**长度为 2 的路径**。
如果某个联通块的边不为偶数，则显然无解。否则总是可以吗？
事实上，不局限于二分图，我们可以在任意连通图上完成这样的构造：
* 随便得到一棵生成树；
* 然后在树上做 dp，优先完成子树内的边，最多留出一条边和父亲匹配。
# [E: gym104114e](https://vjudge.net/problem/Gym-104114E)
给定 $2n$ 个节点的一个图，每个节点上有权值 $c_i$。
除了 $n$ 对限制关系 {$ u = 2 * i - 1$, $ v = 2 * i$} 以外，任意两个节点 {$u, v$} 均有一条边，每条边的权值即是两个节点权值的差值，即 $|c_u - c_v|$。
可以证明这样的图，一定存在完美匹配。
求该图上最小权完美匹配的值，即 $min${$|c_{u_i} - c_{v_i}| + |c_{u_i} - c_{v_i}| + ... + |c_{u_n} - c_{v_n}|$}。
## 题解
我们总是希望选中的匹配在权值上尽可能靠近。
故我们先把 $c_i$ 们按权值排序，如果相邻的权值没有相邻的编号，则显然按顺序把两个两个连结，得到的权值最小。
否则，通过小数据暴力，容易发现，一定满足某种方案，使得每一条匹配边的距离不跨过 3 个元素。
故可以从左往右 dp，在状态上记录最近 3 个元素是否已经被匹配了。
# [F: gym104323h](https://vjudge.net/problem/Gym-104234H)
对于两个图 $G1$ 和 $G2$，我们说这两个图同构：
* 当且仅当存在一个排列 p[] 使得：如果 $u$ 和 $v$ 有一条边在 $G1$，则 $p_u$ 和 $p_v$ 也有一条边在 $G2$ 中，反之亦然。
给定有 $n$ 个节点的一个图 $G$，判断和其同构的图的个数是否不超过 $n$ 个。
我们认为两个图 $G1$ 和 $G2$ 不同，当且仅当某条边在 $G1$ 中而不在 $G2$ 中。
## 题解
通过小数据暴力，可以发现：
* 当 $N$ 小于等于 3，总是 "yes"；
* 当 $N$ 大于 4：
* 如果输入的是完全图或者其补图，"yes"；
* 如果输入的是菊花图或者其补图，"yes"；
* 其他情况 "no"；
* 当 $N = 4$，我们可以暴力枚举排列，检查其是否有 4 个同构。
# [G: gym104114c](https://vjudge.net/problem/Gym-104114C)
新冠期间，$n$ 个人去做了 $m$ 支混管测试：
* 其中第 i 支混管的样本分别是：$a_{i,1}, a_{i,2}, ... a_{i,k}$。
混管的结果出来了，不幸的是**所有混管都呈阳性**。
假设测试前，每个人是否新冠的可能性均为 $50\%$。
根据混管的结果，显然有一些人比另一些人更有可能新冠中招。
要求把所有人的编号按照确诊的可能性从小到大排序。
## 题解
考虑计算出每一个人确诊的概率，然后比较大小。
根据提示，第 i 个人确诊的概率，和所有 $2^n$ 种方案中满足 $m$ 个混管都是阳性的情况下，其中第 i 个人是确诊的方案数，成正比。
考虑计算这个方案数（答案需要用高精度，或者可以考虑 bitset 存储）：
* 对于第 i 个人参与的混管，显然是满足的；
* 对于其不满足的混管，我们可以使用容斥原理来计算：钦定其中的若干个不满足，则确定了哪些人是**非阳性**的，其他则随意。
# [H: gym100548c](https://vjudge.net/problem/Gym-100548C)
我们可以把一对逆序对 $\{a_i, a_j\}$ 看成一条边连结了节点 $i$ 和 $j$。
则问题可以归约到：求一个点的子集，满足子集内的 **边数** 除以 **点数** 的比例最大。
这是经典的最大密度子图问题。
可以通过二分答案 + 网络流判定。
# [I: gym103428b](https://vjudge.net/problem/Gym-103428B#author=phtniit)
问有多少种方案，满足在 [0, N] 这 N+1 个数中选择一个大小恰好为 K 的集合，使得集合中的数的异或和的二进制恰好有 B 个 1。
## 题解