George_Plover edited 1 年,9 月前
This is a past version of blog 2022 年上海市大学生程序设计竞赛 - 十月赛 题解
【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](https://uploadfiles.nowcoder.com/images/20211015/595938312_1634228288121/0A7B8575F81E6D28645879810E6F43A9)
可以发现 $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](https://uploadfiles.nowcoder.com/images/20211015/595938312_1634228296796/8254A4657F68510FB01FAC469B5A9B42)
- 第一个部分,就是 $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相邻的有效块,都是数字块(不考虑雷)
.10
.10
//与数字1相邻的空白联通块,有1个
01.
121
.10
//与数字2相邻的空白联通块,有2个
枚举所有局部情况可以证明这一点。
- 对于相邻没有空白块的数字,它只可能被自己开采出来,因此它与其它格子独立,可以直接把它的 SG 函数设为 1 。
- (注意到我们把每个空白的极大联通块看作了结点)对于相邻有1个空白联通块的数字块,我们把它看作是空白联通块结点到自己的一个自环。
- 对于相邻有2个空白联通块的数字块,我们把它看作是链接两个空白联通块结点的一条边。
于是我们得到一张图。
这个游戏等价于:有一张图,双方轮流操作,每次可以删除一条边,或者删除一个点以及它所连的所有边。不能操作的人输。
这个博弈游戏在一般图上还没有多项式时间的算法。
但是在此题中,数据范围很小,可以状压图,然后算每个状态的 SG 函数来做。
注意到,图里如果出现重边,一条边出现了 $x$ 次,等价于出现了 $x\mod 2$ 次,这个条件可以一定程度减少状态数目。状压时,使用一些技巧可以只压边的状态(包括自环边)。
在 8*8 的扫雷图里面,有效边是超不过17条的,因此状压的做法时间是很充裕的。
以上。
【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](https://uploadfiles.nowcoder.com/images/20211015/595938312_1634228288121/0A7B8575F81E6D28645879810E6F43A9)
可以发现 $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](https://uploadfiles.nowcoder.com/images/20211015/595938312_1634228296796/8254A4657F68510FB01FAC469B5A9B42)
- 第一个部分,就是 $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条的,因此状压的做法时间是很充裕的。
以上。