Moscow International Workshops 2021 Day 1 题解 (aka AMPPZ 2021)

http://blog.qingyu.us/2021/11/moscow-international-workshops-2021.-day-1./

Warning: 这场比赛可能会被用作 XXII Open Cup 的 GP of Poland, 如果你到时候想参赛的话就别看这篇博客了~

A. AMPPZ in the times of disease

首先注意到, 如果我们对每个 $S_1,S_2, \cdots, S_k$ 都确定了一个元素, 那么其余点显然只能选择距离其最近的一个关键点, 并加入这个集合(若有多个则显然无解).

令 $P_1 \in S_1$, 随后我们考虑距离 $P_1$ 最远的点, 不妨假设其为 $P_2$. (若有多个, 我们随便取一个即可)

那么, 如果 $P_2 \in S_1$, 那么 $f(S_1) \geq \mathrm{dist} (P_1,P_2)$, 但另一方面, 限制要求我们有 $f(S_1) \leq \min _{x \in S_1, y \notin S_1} \mathrm{dist}(x, y)$, 因此除非 $U \setminus S_1 = \varnothing$, 否则一定无解.

不妨设 $P_2 \in S_2$, 那么我们同样找到一个 $P_3$, 使得 $\min(\mathrm{dist}(P_1,P_3), \mathrm{dist}(P_2,P_3))$ 最小, 同样我们有 $P_3 \in S_3$.

这样重复 $k$ 轮, 我们就为每个集合都找到了一个关键元素. 时间复杂度为 $O(nk)$.

B. Babushka and her pierogi

留坑.

C. Cake

这个旋转操作看起来比较强大, 但是注意到旋转前后两维的奇偶性都会改变, 所以如果设 $b_{i,0} = a_{i,i \; \bmod 2}, b_{i,1} = a_{i,(i+1)\;\bmod 2}$, 那么旋转操作等价于交换两个相邻的 pair, 问题转化成给你一个序列, 问最少交换相邻元素多少次变成目标序列. 在没有相同元素的时候就是逆序对数, 而有相同元素时, 容易发现我们直接按顺序匹配就是最优的. 时间复杂度 $O(n \log n)$.

D. Divided Mechanism

直接暴力模拟即可, 难度全在读题上. 时间复杂度 $O(\sum nmq)$.

实现的时候如果直接维护整个图形可能有点难写, 直接记一下差分了多少即可.

E. Epidemic

留坑

F. Fence

首先注意到, 对于一个 $(a_i,b)$ 的二元组, 我们可以 $O(1)$ 求出其生成序列的奇数位置和与偶数位置和.

注意到当我们将 $b$ 变为 $b+1$ 时, 只有 $a_i \geq b$ 的位置的值变化了, 而这样的变化总数是不超过 $\sum_{b \geq 0}\sum_{i=1}^n [a_i \geq b] = \sum_{i=1}^n a_i = S$ 的, 所以我们可以直接暴力修改.

由于修改一个位置会影响后面位置的贡献, 我们可以开一棵线段树, 支持一下单点修改和区间换标记即可, 由于只有两种标记, 直接暴力存两个区间和即可. 时间复杂度为 $O(n + S \log n)$, 足够通过.

注意到我们修改的时候, 凡是这一轮没修改过的位置, 以后都不会再改了, 所以我们其实没必要线段树, 直接暴力维护即可. 对于删除操作, 直接使用链表维护即可, 时间复杂度为 $O(n+S)$.

G. Gebyte's Grind

如果我们将每个点看作一个映射 $f: \mathbb Z \mapsto \mathbb Z$ 的话, 那么这三类节点分别相当于:

$f(z) = \begin{cases}z-b & z > b\\ -\infty & \mathrm{otherwise}\end{cases}$
$f(z) = \begin{cases} c & z \geq c \\ -\infty & \mathrm{otherwise} \end{cases}$
$f(z) = \max (z, c)$

首先注意到第三类节点可以写成 $f(z) = \begin{cases} z & z \geq c \\ c & \mathrm{otherwise} \end{cases}$, 那么注意到, 我们任意取出若干个映射, 他们的复合一定可以写成 $(f \circ \cdots \circ f_*)(z) = \begin{cases} -\infty & z \leq a \\ c & a < z \leq b & \\ z + d & \mathrm{otherwise} \end{cases}$的形式(更特殊的, 其实一定有 $d=c-b$), 所以我们可以开一棵线段树, 每个节点维护这个区间的复合对应的映射长什么样. 容易发现我们可以 $O(1)$ 求两个映射的复合, 所以我们可以轻松合并标记. 对于修改操作, 我们直接做即可. 对于查询操作, 我们先从 $l_i$ 往上 jump, jump 的时候把 parent 对应的右儿子复合起来, 如果发现此时 $f(z)$ 已经是 $-\infty$ 了, 就代表需要左拐, 直接进去右儿子并不断往左跳即可(整个过程类似线段树二分). 总的时间复杂度为 $O((n+q) \log n)$.

H. Hidden Password

签到题.

I. Interesting Numbers

不妨假设 $a_i \in [0,2^b)$.

如果 $k < 2^{b-1}$, 那么显然选出的数的最高位必须全都相同, 我们将最高位为 $0$ 和为 $1$ 的分开做即可, 转化为 $a_i \in [0,2^{b-1})$ 的子问题.
如果 $k \geq 2^{b-1}$, 那么我们考虑建出一张图, 如果两个数异或小于等于 $k$ 连一条边, 答案即为图 $G$ 的最大团. 注意到最高位相同的 $a_i$ 之间一定会连边, 因此图事实上是两个团之间连了一些边, 求最大团.
- 注意到 $G$ 的补图为二分图, 所以可以直接跑二分图最大匹配, 如果使用 Dinic 算法, 总的时间复杂度会达到 $O(n^{2.5} \log V)$, 无法通过.
- 整个图的结构非常优秀, 我们可以考虑 Trie 树优化建图, 这样的时间复杂度优化到 $O(n^{1.5} \log n \log V)$, 可以通过. 当然, 如果做的时候精细实现一下, 把每一层重复的部分压缩起来, 应该可以做到 $O(n^{1.5} \log n + n \log V)$ (没写过, 口胡的)
- 事实上不用这么复杂, 我们仍然可以使用类似分治的方法解决. 我们继续将两个团 $A,B$ 划分为第 $b-1$ 位为 $0$ 的部分 $A_0,B_0$ 与为 $1$ 的部分 $A_1,B_1$, 那么我们考虑 $k$ 的第 $b-1$ 位:
  1. 如果这一位为 $0$, 那么答案显然就是 $\max (f(A_0,B_0), f(A_1,B_1))$, 直接递归即可.
  2. 否则, 注意到只有 $A_0,B_1$ 与 $A_1,B_0$ 的部分需要决策, 答案即为 $\max(|A_0|+|B_0|, |A_1| + |B_1| , f(A_0, B_1), f(A_1, B_0))$.
- 总的时间复杂度为 $O(n \log V)$

J. Jungle Trail

若起点与终点间不连通, 则无解. 否则, 容易发现, 我们任取一条起点到终点的长为 $n+m-2$ 的路径, 每次移动都会走到一个新的行/列, 直接调整这些位置就是一组合法的方案.

K. Kitten and Roomba

我们在走路的时候, 维护一个 $p_i$, 表示此时你站在 $i$ 号点的概率, 那么整个过程的答案可以使用以下过程求出:

初始 $E \leftarrow 0$
对于每一步所走的 $x$:
1. 令 $E \leftarrow E + p_x$
2. 对所有 $(x,y) \in G$, 令 $p_y \leftarrow p_y + p_x / \deg (x)$
3. 令 $p_x \leftarrow 0$.
$E$ 即为答案

由于图是一棵树, 我们直接随便钦定一个点当根, 然后对于修改一个点邻居的操作, 我们变成修改它的父亲并在自己位置打一个标记. 查询的时候直接询问真实的值与父亲的标记相加即可. 时间复杂度 $O(n+m)$

L. Lemurs

容易发现如果一个位置能放, 那么我们放了显然不会让答案变劣, 所以我们能放就放是最优的.

而对于一个位置 $(x,y)$, 其能放当且仅当对所有 $|x'-x|+|y'-y| \leq k$ 的 $(x',y')$ 都是 x, 这可以通过转 Chebyshev Distance 后询问矩形和实现. 而求出答案后, 做同样的操作即可.

唯一的问题是虽然 $1 \leq n,m \leq 1000$, 但最坏情况下有 $50$ 组测试数据, 上述算法的时间复杂度为 $O(T(n+m)^2)$, 于是以 4.5 秒(时限4.0秒)的好成绩 TLE 了.

考虑一个常数更小的算法: 对于一个 ., 本质上其限制了预期 Manhattan 距离 $\leq k$ 的位置不能放, 所以相当于这些位置都被 ban 了. 我们对每个点维护一个 $f_i$, 表示这个点的距离限制, 那么我们按照 $f_i$ 从大到小 BFS, 即可求出所有被 ban 的位置. 最后合法的位置同样可以求出, 这样的时间复杂度就优化到了 $O(Tnm)$, 可以通过.

M. Median

留坑.

Auto Post by QOJ Editorial bot

Qingyu的博客

博客