2022 年上海市大学生程序设计竞赛 - 十月赛 题解
George_Plover edited 2 年前
【Problem A】String
【题意】
给出两个字符串 $s$ 和 $t$，判断能否通过有限次交换 $t$ 上相邻的字符使 $t$ 变为 $s$ 。
【做法】
分别统计两字符串中每个字母的出现次数，若完全一致则可以，反之不行。
【Problem B】Questions on Binary Tree
【题意】
给出一棵 $n$ 个结点的二叉树，按二叉堆形式排布。有 $m$ 次询问，每次询问结点 $x$ 在树的前序遍历中的排名。
$n\le 10^{18},m\le 10^5$
【做法】
分析堆式二叉树的编码性质即可，容易对单个询问实现 $O(\log n)$ 的求解算法。复杂度 $O(m\log n)$ 。
以下是推导细节：
考虑用数学计算求出每个结点的 $dfs$ 序。
根是 $1$ 号。编号为 $i$ 的点，其父亲结点的编号是 $\lfloor\frac{i}{2}\rfloor$ ，其左儿子的编号是 $2i$ ，右儿子的编号是 $2i+1$ 。
我们用 $dfn(i)$ 表示结点 $i$ 的 $dfs$ 序。
用 $Lr(i)$ 表示结点 $i$ 在其所在层的排名，比如 $Lr(3)=2,Lr(6)=3$ （如图）
可以发现 $Lr(i)=i+1 - 2^{\lfloor\log_2{i}\rfloor}$ ，这是因为每一层最左边的数字一定是 $2$ 的整数次幂。
我们用 $Slr(i)$ 表示结点 $i$ 与其祖先的 $Lr$ 值之和，于是有递推式 $Slr(i) = Slr(\lfloor \frac{i}{2}\rfloor) + Lr(i)$ 。
我们要确定 $dfn(i)$ ，就需要知道在遍历的的时候，有多少个点在 $i$ 之前被遍历。
我们统计这些点的数量，分为三个部分，如下图，以计算 $dfs(3)$ 为例。
- 第一个部分，就是 $Slr(\lfloor \frac{i}{2}\rfloor)$ 。
- 第二个部分，从 $i$ 所在层前面的 $Lr(i)-1$ 个结点开始延伸，有若干层，其中每一层的结点是上一层的两倍。具体有多少层，可以直接根据树的高度和结点 $i$ 所在的高度算出。
- 第三个部分，树最下面不满的一层，需要特殊判断一下。
第一个部分直接递归求解。
第二个部分可以这么算出：假设树满的层数是 $D$ ，$i$ 所在层数是 $d(i)$ 那么这部分的值就是 $(Lr(i)-1)\times (2^{D-d(i)+1}-1)$ 。其中 $2$ 的幂次用位运算计算，是 $O(1)$ 的。
第三个部分可以这么算出：假设树满的层数是 $D$ 那么，$i$ 所在层数是 $d(i)$ ，那么随着 $Lr(i)-1$ 个点的延伸，最后一层本应该有 $2^{D-d(i)+1}$ 个结点，但是可能并不能取满，假设树最后一层（不满）有 $k$ 个结点，第三部分的值就是 $\min(2^{D-d(i)+1},k)$ 。
三个部分之和，就得到了在 $i$ 之前被遍历的结点数目，再 $+1$ 就是答案。
【Problem C】Moonlight over the Lotus Pond
【题意】
给出 $n\times m \le 10^5$ 的非负数矩阵，问有多少个子矩阵的和恰好为 $k$ 。
【做法】
枚举子矩阵的左右边界 $l,r$ ，对于每对给定的 $l,r$ ，当前要求解的问题变为：
- 长度为 $n$ 的序列中，子区间和为 $k$ 的子区间数量。
由于元素非负，这个问题可以通过前缀和+双指针 $O(n)$ 解决。
因此复杂度 $O(m^2 n)$ 。当 $m\ge n$ 时，将矩阵转置，这样就可以保证 $m<n$ ，也就是 $m< \sqrt {(mn)}$ 。
最终复杂度 $O((mn)^{1.5})$
有意卡掉了带 $\log$ 的做法，以及常数大的实现方式（例如 unordered_map）。
【Problem D】Permutation
【题意】
给出 $3$ 个长度为 $n\le 2\times 10^4$ 的全排列。
要求分别在其中找到长度为 $k$ 的子序列，并取出，得到：
$a_1,a_2…a_k$
$b_1,b_2…b_k$
$c_1,c_2…c_k$
并且要求对任意的 $1 \leq t \leq k$ ，满足：$a_t\times b_t=c_t \text{ or } b_t\times c_t=a_t\text{ or } c_t\times a_t=b_t$ 。
求 $k$ 的最大值。
【做法】
因为是全排列，可以列举出所有满足条件的三元组，一共不超过 $6\times 10^5$ 个。
于是转化为最长三维偏序序列问题，可以用 cdq 分治或者二维数据结构实现。
参考实现：采用树状数组套单调map
- 对三元组 $(x,y,z)$ 我们按照 $z$ 从小到大排序，然后按顺序考虑，这样保证了先讨论的三元组的 $z$ 一定不大于后讨论的。
- 接下来维护二维数据结构，需要支持如下操作：
- 在 $(x,y)$ 位置插入一个 $dp$ 值
- 在 $1\leq i\leq x,1\leq j \leq y$ 范围查询最大的 $dp(i,j)$ 的值
- 考虑维护树状数组表示 $y$ 坐标，并且树状数组每个结点维护一个 map，第一关键字是 $x$ 坐标，第二关键字是 $dp$ 值。map中保持元素第二维度单调递增（不满足的，弹出即可）（因为我们求的是前缀最值）
- 对于插入，我们在树状数组上根据 $y$ 修改最多 $\log n$ 个map，往map里面根据 $x$ 插入元素并且弹出不满足单调性的元素。
- 对于查询，我们在树状数组上根据 $y$ 查询最多 $\log n$ 个map，在上面直接
--upper_bound(x)就可以找到前缀最值。
时间复杂度 $O(M\log n\log ans)$ ，空间复杂度 $O(M+n\cdot ans)$ 其中 $M$ 是三元组个数，$ans$ 是此题答案范围。
容易证明 $ans\leq 423$ ，这是因为每个三元组都至少会用到一个 $\sqrt n<142$ 以内的数字，所以答案大小不超过 $3\sqrt n$ 。
因此，尽管 $M$ 是较为巨大的 $6\times 10^5$ ，该做法的 $\log $ 因子常数较小。
【Problem E】Minesweeper Game
【题意】
$n\times m$ 的扫雷，在双方已知所有雷的位置的前提下，轮流左键点击未开采的块。不能操作的人输。问胜负。
如果当前开采了一个块，且它周围8个方向相邻的位置没有雷，那么周围的8个位置也会立即被开采，这个过程将迭代到稳定态后停止，到达稳定态后才会换对手操作。
【做法】
考虑可以点击的块，有两种：
- 空白块，周围没有雷。
- 数字块，周围有1~8个雷。
以下讨论的联通，均指8方位相邻规则下的。
- 我们将极大空白联通块看成一个点。当我们点击当中的任何一个空白块，都将把这个联通块开采出来，并且还会把与它们相邻的数字块开采出来。
- 数字块，当我们单独点击它时，只会把它自己开采出来。
引理1：
对任何一个数字块，与它相邻的不同的空白联通块，只可能是0个、1个、或2个。
例如：
.2.
242
.2.
//与数字4相邻的有效块，都是数字块（不考虑雷）
.20
.20
//与数字2相邻的空白联通块，有1个
01.
121
.10
//与数字2相邻的空白联通块，有2个
枚举所有局部情况可以证明这一点。
- 对于相邻没有空白块的数字，它只可能被自己开采出来，因此它与其它格子独立，可以直接把它的 SG 函数设为 1 。
- （注意到我们把每个空白的极大联通块看作了结点）对于相邻有1个空白联通块的数字块，我们把它看作是空白联通块结点到自己的一个自环。
- 对于相邻有2个空白联通块的数字块，我们把它看作是链接两个空白联通块结点的一条边。
于是我们得到一张图。
这个游戏等价于：有一张图，双方轮流操作，每次可以删除一条边，或者删除一个点以及它所连的所有边。不能操作的人输。
这个博弈游戏在一般图上还没有多项式时间的算法。
但是在此题中，数据范围很小，可以状压图，然后算每个状态的 SG 函数来做。
注意到，图里如果出现重边，一条边出现了 $x$ 次，等价于出现了 $x\mod 2$ 次，这个条件可以一定程度减少状态数目。状压时，使用一些技巧可以只压边的状态（包括自环边）。
在 8*8 的扫雷图里面，有效边是超不过17条的，因此状压的做法时间是很充裕的。
以上。
Past Versions
- #28443 by George_Plover (2022-10-23 21:32:58).
- #28442 by George_Plover (2022-10-23 21:30:23).