专题题解 - XXII Open Cup named after E.V. Pankratiev, Grand Prix of Poland

发表于 分类于
https://qoj.ac/contest/969

打 * 号表示没有写的题，可能是不打算写了，也可能是暂时没来得及写。

A. AMPPZ in the times of disease

难度：$\bigstar\bigstar$

题目大意：

给定 $n$ 个平面上的点，你需要划分成 $k$ 个非空点集，使得任意一对同一集合内的点的距离小于任意一对不同集合内点的距离，保证有解。

$n\leq 2\times 10^6, k\leq 20$

题目解法：

随便找一个点 $p_1$，再求出其余点与 $p_1$ 距离最远的点 $p_2$，再求出其余点和 $p_1,p_2$ 距离最小值最大的点 $p_3$，以此类推。

易证 $p_1,\ldots,p_k$ 属于不同集合，将每个其余点分进距离最近的 $p_i$ 所在集合即可。

时间复杂度为 $O(nk)$。

B. Babushka and her pierogi

难度：$\bigstar\bigstar\bigstar$

题目大意：

给定长度为 $n$ 的序列 $a_{1\ldots n}$，所有数两两不同，你需要通过若干次操作将其变为其某个给定排列 $b_{1\ldots n}$，每次操作可以交换两个数 $a_i,a_j$，代价为 $C+|a_i-a_j|$，其中 $C$ 为给定常数。求最小代价和。

$n\leq 2\times 10^5$

题目解法：

答案有一个下界 $(n-c)\times C+\dfrac{1}{2}\sum\limits_{i=1}^n|a_i-b_i|$，其中 $c$ 是置换环个数，有很多种方法得出这个下界，并且猜想这个下界可以达到。

考虑一次交换 $a_i,a_j$，它们在同一置换环上，设 $b_i<b_j$，如果 $a_i\in (a_j,b_j]$ 且 $a_j\in [b_i,a_i)$ 则称这是一次好交换。容易发现为了达到下界要求每次操作都是好交换，同时这也是充分条件。

剩下的一个结论是：考虑最小的 $b_i$ 使得 $a_i\ne b_i$，一定存在一组好交换 $(a_i,a_j)$，证明是考虑满足 $a_j<a_i$ 的 $a_j$ 共有 $a_i-1$ 个，而 $b_j<a_i$ 的 $b_j$ 只有 $a_i-2$ 个（把空位挖掉）。

所以我们从小到大考虑每个 $b_i$，如果已经有 $a_i=b_i$ 则跳过，否则找出一个包含 $a_i$ 的好交换并进行之。

考虑如何在比较好的复杂度内找出这样的一个好交换，题解的思路颇为巧妙：从 $b_i$ 所在置换环向 $b_i$ 两边同步搜索，直到遇到一个好交换，这时如果原本长度为 $l$ 的置换环分解成长度为 $a,b$ 的置换环，则只进行了 $\min(a,b)$ 次检验，相当于启发式分裂，所以时间复杂度为 $O(n\log n)$。

还有很多种方法解决最后求好交换的问题，不过要做到 $O(n\log n)$ 并不容易。

C. Cake

难度：$\bigstar$

题目大意：

给定 $2\times n$ 矩阵的初始状态和目标状态，每次操作可以 180 度翻转一个 $2\times 2$ 连续子矩阵，问至少需要几次操作，或报告无解。

$1\leq n\leq 5\times 10^5$

题目解法：

将所有偶数列上下翻转，问题转化为每次交换相邻，求逆序对即可。

D. Divided Mechanism

难度：$\bigstar$

题目大意：

给定 $n\times m$ 网格，网格中有两个四连通块 $A,B$，接下来进行 $q$ 次操作，每次操作将 $B$ 向上下左右中的一个方向持续拉动，但不能与 $A$ 重叠，问最终能否使 $A,B$ 分离（使 $B$ 可自由移动）。

$n,m\leq 10, q\leq 100$

题目解法：

按题意模拟。

*E. Epidemic

难度：$\bigstar\bigstar\bigstar$

F. Fence

难度：$\bigstar$

题目大意：

给定长度为 $n$ 的序列 $a_{1\ldots n}$，对于每个 $1\leq x\leq \max a_i$，求出：

  • 把每个 $a_i$ 拆分成 $x+x+\ldots+(a_i\bmod x)$ 后，新序列所有奇数项的和。

$1\leq \sum a_i\leq 10^6$

题目解法：

如果有连续一段 $a_i$ 满足 $a_i<x$，那么只需要这一段的奇数位和以及偶数位和即可，所以对于 $x$ 算答案时只需要 $x\leq a_i$ 的那些 $a_i$，按 $x$ 从小到大再利用双向链表即可做到 $O(\sum a_i)$。

G. Gebyte’s Grind

难度：$\bigstar\bigstar$

题目大意：

给定函数序列 $f_{1\ldots n}$ 以及数 $h$，$f_i$ 有三种可能：

  • $f_i(x)=\max(0,x-v_i)$；
  • $f_i(x)=v_i\times [x\ge v_i]$；
  • $f_i(x)=\max(v_i,x)$。

特别地，总有 $f_i(0)=0$。

你需要支持 $q$ 次操作，操作有单点修改，以及给出 $x$ 查询最大的 $r$ 使得 $f_r(f_{r-1}(\ldots (f_x(h))))>0$。

$n,q\leq 2\times 10^6, v_i\ge 1$

题目解法：

注意到若干 $f_i$ 的复合总可以写成：

的形式（这里用了题解写的形式，实际上你也可能得到一些等价形式），于是线段树维护即可，时间复杂度 $O((n+q)\log n)$。

H. Hidden Password

难度：$\bigstar$

题目大意：

小写字符串 $H_1$ 通过每个字符加 $x$（超过 z 则回到 a） 得到 $H_2$，$H_2$ 通过每个字符加 $x$ 得到 $H_1$，且 $H_1\ne H_2$，给定 $H_1$ 求 $H_2$。

$|H_1|\leq 2\times 10^5$

题目解法：

每个字符加 $13$ 即可。

I. Interesting Numbers

难度：$\bigstar\bigstar$

题目大意：

给定 $n$ 个数 $a_1,\ldots,a_n$，求最多能选出多少数使得两两的异或和 $\leq k$。

$n\leq 3\times 10^4, a_i<2^{20}$

题目解法：

经典的在 Trie 上 DFS，设 $dfs(x,y)$ 表示在深度相同的 $x,y$ 子树中各选出一些点满足条件的方案数，如果当前是第 $t$ 位，若 $k$ 的第 $t$ 位为 $0$，那么就只能递归到同向儿子，即 $\max(dfs(lc_x,lc_y),dfs(rc_x,rc_y))$（别忘了 $x,y$ 中有一个子树里一个点都没选的情况）；否则可以递归到不同儿子，同时两个子问题独立，所以 $dfs(lc_x,rc_y)+dfs(rc_x,lc_y)$。

时间复杂度为 $O(n\log A)$。

J. Jungle Trail

难度：$\bigstar$

题目大意：

给定 $n\times m$ 网格，每个格子为空地，障碍，好蛇或坏蛇，你可以选择一些行和一些列，然后翻转这些行列上蛇的好坏状态（如果一行一列都被选，交点处负负得正），然后你需要找到一条从左上角到右下角的只经过空地和好蛇的只能向下向右走的路径，或报告无解。

$n,m\leq 2000$

题目解法：

随便找出一条不经过障碍的路径，然后每走到一个格子，如果这个格子是坏蛇就翻转一下新到的行或列即可（具体地，如果这一步往下走就翻转这一行，否则翻转这一列）。

K. Kitten and Roomba

难度：$\bigstar$

题目大意：

给定一棵 $n$ 个点的树，猫猫一开始在点 $c$，机器人会通过（不一定简单的）树上路径 $a_{1\ldots n}$，如果机器人到达了猫猫所在的点，猫猫就会随机跑到一个邻居上，问猫猫期望会跑多少次。

$n\leq 10^6$

题目解法：

始终维护当前猫猫在每个点的概率 $p_i$，如果机器人到了 $x$，那么就把 $p_x$ 均匀分配给 $x$ 的邻居，在每个点上打标记维护其儿子的增量即可线性。

L. Lemurs

难度：$\bigstar$

题目大意：

给定 $n\times m$ 网格以及数 $k$，网格中有点和叉，你需要选择一些叉，使得到某个叉的曼哈顿距离不超过 $k$ 的点集恰好是所有叉，或报告无解。

$n,m,k\leq 1000$

题目解法：

先从点开始 DFS，得到哪些叉可以被选，然后从这些叉 DFS，看看是不是覆盖了所有的叉，复杂度 $O(nm)$。

*M. Median

难度：$\bigstar\bigstar\bigstar\bigstar$