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

George_Plover edited 3 月,1 周前

【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$ (如图)

alt

可以发现 $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)$ 为例。

alt

第一个部分直接递归求解。

第二个部分可以这么算出:假设树满的层数是 $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$ ,当前要求解的问题变为:

由于元素非负,这个问题可以通过前缀和+双指针 $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

时间复杂度 $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. 空白块,周围没有雷。
  2. 数字块,周围有1~8个雷。

以下讨论的联通,均指8方位相邻规则下的。

引理1:

对任何一个数字块,与它相邻的不同的空白联通块,只可能是0个、1个、或2个。

例如:

.2.  
242
.2.  
//与数字4相邻的有效块,都是数字块(不考虑雷)    
.20
.20
//与数字2相邻的空白联通块,有1个
01.
121    
.10
//与数字2相邻的空白联通块,有2个

枚举所有局部情况可以证明这一点。

于是我们得到一张图。

这个游戏等价于:有一张图,双方轮流操作,每次可以删除一条边,或者删除一个点以及它所连的所有边。不能操作的人输。

这个博弈游戏在一般图上还没有多项式时间的算法。

但是在此题中,数据范围很小,可以状压图,然后算每个状态的 SG 函数来做。

注意到,图里如果出现重边,一条边出现了 $x$ 次,等价于出现了 $x\mod 2$ 次,这个条件可以一定程度减少状态数目。状压时,使用一些技巧可以只压边的状态(包括自环边)。

在 8*8 的扫雷图里面,有效边是超不过17条的,因此状压的做法时间是很充裕的。


以上。

Past Versions

Comments