2022 年上海市大学生程序设计竞赛 - 十月赛 题解

George_Plover edited 2 年，6 月前

【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\dots a_k$

$b_1,b_2\dots b_k$

$c_1,c_2\dots c_k$

并且要求对任意的 $1\le t\le 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\le i\le x,1\le j\le 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\le 423$ ，这是因为每个三元组都至少会用到一个 $\sqrt{n}<142$ 以内的数字，所以答案大小不超过 $3\sqrt{n}$ 。

因此，尽管 $M$ 是较为巨大的 $6\times {10}^5$ ，该做法的 $\log$ 因子常数较小。

【Problem E】Minesweeper Game

【题意】

$n\times m$ 的扫雷，在双方已知所有雷的位置的前提下，轮流左键点击未开采的块。不能操作的人输。问胜负。

如果当前开采了一个块，且它周围8个方向相邻的位置没有雷，那么周围的8个位置也会立即被开采，这个过程将迭代到稳定态后停止，到达稳定态后才会换对手操作。

【做法】

考虑可以点击的块，有两种：

1. 空白块，周围没有雷。
2. 数字块，周围有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\mathrm{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).

Comments