XXII Open Cup named after E.V. Pankratiev, Grand Prix of Poland

ix35 · 2022-08-04 18:27:56 · 个人记录

XXII Open Cup named after E.V. Pankratiev, Grand Prix of Poland

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

A. AMPPZ in the times of disease

难度：\bigstar\bigstar

题目大意：

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

题目解法：

随便找一个点 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-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 连续子矩阵，问至少需要几次操作，或报告无解。

题目解法：

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

D. Divided Mechanism

难度：\bigstar

题目大意：

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

题目解法：

按题意模拟。

*E. Epidemic

难度：\bigstar\bigstar\bigstar

题目大意：

有 n 个人，他们中的一些得病，接下来依次发生 m 个事件，每个事件为以下四种之一：

• 有 k 个人参加聚会，如果其中至少一个人得病，则所有人都得病；

• 得知某人此时不得病；

• 得知某人此时得病，然后此人被隔离，之后不会出现在聚会中；

• 询问在序列 p,p+1,\ldots,n,1,\ldots,p-1 中，第一个可能得病并且没被隔离的人是谁（或说明所有未被隔离的人都不可能得病）。

题目解法：

可以发现测出得病是不会有新增信息的，只需要考虑测出不得病给我们的信息。

考虑倒推，记录每个人当前最早可能得病的时间，如果某人某时不得病，则之前参加的所有聚会的所有人当时都不得病，更新这个最早时间即可。

实现似乎有些麻烦。

F. Fence

难度：\bigstar

题目大意：

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

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

题目解法：

如果有连续一段 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(0)=0。

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

题目解法：

注意到若干 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。

题目解法：

每个字符加 13 即可。

I. Interesting Numbers

难度：\bigstar\bigstar

题目大意：

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

题目解法：

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

题目解法：

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

K. Kitten and Roomba

难度：\bigstar

题目大意：

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

题目解法：

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

L. Lemurs

难度：\bigstar

题目大意：

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

题目解法：

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

*M. Median

难度：\bigstar\bigstar\bigstar\bigstar

题目大意：

明天也不一定。

题目解法：

明天也不一定。