【做题记录】历年 CSP-S 做题记录

CSP-S 2019

D1T1 格雷码

题目链接 AC

题解：

依题意按位模拟即可。

代码实现

D1T2 括号树

题目链接 AC

题解：

$\mathcal{DFS}$ 一遍整颗树，每个节点的答案等于父亲节点的答案加上自己的贡献。对于后者，我们维护一个栈即可计算。

代码实现

D1T3 树上的数

题目链接 AC

题解：

首先考虑一个基本的思路：枚举每个权值，将其移动到尽量小的位置。我们称这个过程为这个权值的移动。

对于一次移动而言，它可能会受比它更小的权值的移动的限制，同样也会限制比它更大的权值的移动，那么我们的核心任务就是处理这些限制。

考虑一次移动的路径 $u_1 \to u_2 \to u_3 \to \cdots \to u_k$ ，它将会造成的限制有：

对于 $u_1$ 而言， $(u_1, u_2)$ 这条边必须是所有和 $u_1$ 相连的边中第一条被删除的边；
对于 $u_i$ 而言，若存在节点 $u_{i - 1}$ 和 $u_{i + 1}$ ，那么 $(u_{i - 1}, u_i)$ 和 $(u_i, u_{i + 1})$ 这两条边必须是所有和 $u_i$ 相连的边中两条连续地被删除的边，即它们中间不能穿插地删除别的和 $u_i$ 相连的边；
对于 $u_k$ 而言， $(u_{k - 1}, u_k)$ 这条边必须是所有和 $u_k$ 相连的边中最后一条被删除的边。

那么，我们每次以当前枚举到的权值初始时所在的节点为根 $\mathcal{DFS}$ 整颗树，在遍历的过程中顺便维护每个节点的合法性即可。

代码实现

D2T1 Emiya 家今天的饭

题目链接 AC

题解：

考虑容斥，显然最多仅会有一列不合法，那么我们考虑枚举这一列，并设状态 $f_{i, j, k}$ 表示在前 $i$ 行中，这一列选了 $j$ 个数，其它的列选了 $k$ 个数的方案总数，转移方程是显然的。

这个 $\mathcal{DP}$ 的复杂度是 $\mathcal{O}(n^3 m)$ 的，不过可以注意到，我们关心的是 $j$ 和 $k$ 的大小关系而非它们的具体值，因此我们可以重新设状态 $f_{i, j}$ ，其中 $i$ 含义不变， $j$ 表示原状态中 $j - k$ 的大小。这样，这个 $\mathcal{DP}$ 的复杂度就降至 $\mathcal{O}(n^2 m)$ 了。

代码实现

D2T2 划分

题目链接 AC

题解：

首先需要介绍为正解做法做铺垫的两个定理：

划分出的段数越多，答案越优；
在划分出的段数相同的前提下，最后一段的权值和越小，答案越优。

那么，我们可以考虑设 $f_i$ 表示前 $i$ 个数的答案， $g_i$ 表示在前 $i$ 个数的最优划分方案中，最后一段的权值和。

暴力的转移是 $\mathcal{O}(n^2)$ 的，如何优化呢？

注意到 $f_j$ 转移到 $f_i$ 的条件为 $sum_i \ge sum_j + g_j$ ，并且转移时决策点越靠后越优（因为决策点越靠后， $g_i$ 就会越小），所以转移时的决策点仅会向右移动，那么我们用单调队列优化这个 $\mathcal{DP}$ 转移即可。

注意这题的空间限制是不允许我们开下 $f_i$ 数组的，所以我们在做 $\mathcal{DP}$ 时可以仅考虑把转移记录下来，做完后再通过高精度算法或 $\underline{}\underline{}\texttt{int128}$ 计算答案。

代码实现

D2T3 树的重心

题目链接 AC

题解：

首先考虑一个基本的思路：统计每个节点作为重心的次数。

我们首先找到一个重心 $rt$ 并将其作为整颗树的根节点。

对于一个不为 $rt$ 的节点 $x$ ，如果我们要想让 $x$ 成为重心，那么被删掉的边需要满足：

不能在 $x$ 的子树内；
设点 $x$ 的重儿子为 $y$ ，删掉这条边后得到的不包含 $x$ 的子树大小为 $k$ ，那么 $n - si_x \cdot 2 \le k \le n - si_y \cdot 2$ 。

对于第二条限制，我们可以在 $\mathcal{DFS}$ 的过程中用树状数组维护；对于第一条限制，我们可以在遍历完 $x$ 的整颗子树后统计这颗子树的贡献并将其减去。

最后，我们还需要求 $rt$ 作为重心的次数。

设 $rt$ 的重儿子为 $a$ ，次重儿子为 $b$ ，删掉一条边后得到的不包含 $rt$ 的子树大小为 $k$ ，那么被删掉的边需要满足：

如果它在 $a$ 的子树内，那么 $k \le n - si_b \cdot 2$ ；
否则， $k \le n - si_a \cdot 2$ 。

对于这个部分，我们 $\mathcal{DFS}$ 一遍整颗树，用两个树状数组维护即可。

代码实现

CSP-S 2019 江西

T1 日期

题目链接 AC

题解：

暴力枚举一年中的每一天，然后一一和输入进行比对即可。

代码实现

T2 和积和

题目链接 AC

题解：

考虑包含 $a_i \cdot b_j$ 的 $S(l, r)$ 的个数，显然其为 $\min(i, j) \cdot (n - \max(i, j) + 1)$ 。

乍一看似乎并不好计算，不过我们可以考虑枚举 $i$ ，并分 $j \le i$ 和 $j > i$ 两部分计算，这样我们仅需预处理一些信息便可做到 $\mathcal{O}(n)$ 的时空复杂度。

代码实现

T3 网格图

题目链接 AC

题解：

考虑 $\mathcal{Kruskal}$ 算法求 $\mathcal{MST}$ 的过程，那么我们仅需判断成环的情况，简单维护即可。

代码实现

T5 多叉堆

题目链接 AC

题解：

对于一颗静态的树，求解答案是很简单的：设以点 $u$ 为根的子树的答案为 $f_u$ ，那么有 $f_u = (si_u - 1)! \cdot \displaystyle \prod_{v \in son_u} \frac{f_v}{si_v!}$ 。

那么，我们可以在当前存在的所有树的根节点上维护整颗树的 $f_u$ 和 $si_u$ ，这样合并时这两种信息可以做到单次 $\mathcal{O}(1)$ 维护。

最棘手的问题在于如何找根：首先，路径压缩并查集的复杂度在本题中是错误的；其次，本题规定了合并的次序，因此无法直接采用启发式合并以保证复杂度。

不过我们可以注意到这样一个事实：我们并不在意根节点是什么，我们只在意根节点上维护的信息。这样的话，我们仍然可以启发式合并，仅需把新子树的信息移植到新的根节点上即可。

代码实现

CSP-S 2020

T1 儒略日

题目链接 AC

题解：

对于 $1582$ 年之前的日期，我们可以考虑通过枚举依次确定年、月、日。

对于 $1582$ 年的日期，我们同样可以考虑通过枚举依次确定月、日，仅需对 $10$ 月份的日期做一点处理即可。

对于 $1582$ 年之后的日期，考虑到闰年的分布以 $400$ 年为周期，我们可以先确定大致的年份，然后再通过枚举依次确定精确的年、月、日。

代码实现

T2 动物园

题目链接 AC

题解：

在 $m$ 条限制条件中，若存在一个 $p_i$ 满足 $n$ 只动物的编号均不包含这一位，那么新加入的动物的编号也不能包含这一位。

这样我们就可以得出有多少个位是不能被选择的，那么剩下的位我们就可以随意选择。设前者的个数为 $cnt$ ，那么答案即为 $2^{cnt} - n$ 。

注意特判答案为 $2^{64}$ 的情况。

代码实现

T3 函数调用

题目链接 AC

题解：

回想在这道题中我们是如何处理乘法标记的下传的：我们会修改区间总和、区间加标记和区间乘标记三种信息。

这也是这道题的基本思路：对于每个位置的初值，以及对于每个 $T_j = 1$ 的函数，考虑它们对答案的贡献。

初值的贡献统计是简单的，而对于每个 $T_j = 1$ 的函数，它的贡献会受到所有在其之后的 $T_j = 2$ 的函数的影响。

那么，我们用一次拓扑排序预处理一些信息，再用一次拓扑排序求解答案即可。

代码实现

T4 贪吃蛇

题目链接 AC

题解：

首先，本题存在一个十分重要的结论：如果当前最强的蛇在吃掉了最弱的蛇之后不是最弱的蛇，那么它一定会选择吃。

不妨设当前最强的蛇为 $\text{A}$ 。如果条件满足，那么 $\text{A}$ 吃完后，最强的蛇比原先要弱，最弱的蛇比原先要强，所以此时如果最强的蛇（设其为 $\text{B}$ ）决定要吃掉最弱的蛇，那么 $\text{B}$ 在吃完之后一定会弱于 $\text{A}$ 。而 $\text{B}$ 一定会保证自己不被吃，所以 $\text{A}$ 也能够保证自己不被吃。

那么，如果条件满足，最强的蛇一定会吃掉最弱的蛇，如此直到条件不满足。

如果条件不满足的话，当前最强的蛇会如何决策？仍然设最强的蛇为 $\text{A}$ 。 $\text{A}$ 若选择吃，那么它会变成最弱的蛇，此时如果最强的蛇（仍然设其为 $\text{B}$ ）决定要吃掉最弱的蛇，那么 $\text{A}$ 一定会选择不吃。以此类推，若 $\text{B}$ 选择吃且其在吃完后会变成最弱的蛇，它的命运又将由新的最强的蛇决定。

这个决策模型与经典的博弈问题 —— 海盗分金问题十分类似。从 $\text{A}$ 开始，这些蛇会一直做与下一条蛇相反的决策，而当某条蛇选择吃后不会成为最弱的蛇或剩余的蛇的数量不超过 $2$ 时，这些蛇的决策也就已经全部确定了 —— 要么 $\text{A}$ 会选择不吃，要么 $\text{A}$ 会选择吃而 $\text{B}$ 会选择不吃。稍加分析，可得 $\text{A}$ 的决策实际取决于总共需要做决策的蛇的数量的奇偶性。

根据上文的分析，我们可以分两个阶段解决这个问题：

第一阶段 —— 每次最强的蛇在吃掉最弱的蛇之后都不会变为最弱的蛇。

这一阶段我们可以用两个双端队列 $Q_0, Q_1$ 维护，前者维护还未做过决策的蛇，后者维护每一轮新产生的蛇。显然二者都是单调的。

每一轮从 $Q_0$ 的首部取出当前最弱的蛇的体力值，再从 $Q_0$ 和 $Q_1$ 的尾部取出当前最强的蛇。若新的蛇是当前最弱的蛇（即弱于 $Q_0$ 首部的蛇），那么进入下文所述的第二阶段；否则，把这条蛇放入 $Q_1$ 的首部。这一步实际上保证了最弱的蛇一定会在 $Q_0$ 的首部。

在进入第二阶段前，若剩下的蛇的数量不超过 $2$ ，那么我们可以直接得出此时的答案为 $1$ 。

第二阶段 —— 存在一轮决斗，最强的蛇在吃掉最弱的蛇之后会变为最弱的蛇

我们还是保留第一阶段中的两个双端队列 $Q_0, Q_1$ ，不过最弱的蛇我们需要单独维护。

还是按照第一阶段的方式取出最强的蛇。如果新产生的蛇仍然是最弱的蛇（注意此处为弱于 $Q_0$ 和 $Q_1$ 首部的蛇，因为此时两个队列中最弱的蛇并不一定在 $Q_0$ 中），那么我们重复这个过程；否则，我们可以直接通过在进入第二阶段前蛇的数量和进入第二阶段后做过决策的蛇的数量的奇偶性得出答案。

若新产生的蛇仍然是最弱的蛇，但此时蛇的数量不超过 $2$ ，那么次轮最强的蛇一定会吃掉最弱的蛇，我们此时也可以直接得出答案。

时间复杂度为 $\mathcal{O}(T n)$ 。

代码实现

CSP-S 2021

T1 廊桥分配

题目链接 AC

题解：

把所有的廊桥按照某种顺序编号为 $1 \sim n$ 。

我们不妨设每架飞机一定会选择停靠在当前所有空闲的廊桥中编号最小的廊桥，那么每架飞机要么无法停靠在廊桥，要么停靠的廊桥编号是固定的。

这样，我们可以假设当前的廊桥数量充足，然后用两个优先队列 $Q_0, Q_1$ 分别维护两种信息：前者维护正停靠在廊桥的飞机和其停靠的廊桥编号，后者维护当前所有空闲的廊桥。

对于国内和国外的飞机，我们分别按照这种方式求出每架飞机最终会停靠在哪个廊桥，然后再通过其分别求出 $f_i, g_i$ ：前者表示分配 $i$ 个廊桥给国内区最多可以使多少架国内航班飞机能够停靠在廊桥，后者同理。

最后，我们枚举分配给国内区的廊桥数 $i~(i \in [0, n])$ ，然后取 $f_i + g_{n - i}$ 的最大值即可。

代码实现

T2 括号序列

题目链接 AC

题解：

为了避免算重，我们可以考虑设 $f_{l, r}$ 和 $g_{l, r}$ ，分别表示有多少种确定所有尚未确定的字符的方案使得子段 $[l, r]$ 为 “符合规范的超级括号序列”，前者要求 $l$ 和 $r$ 位置上的括号配对，后者要求 $l$ 和 $r$ 位置上的括号不配对。

先 $\mathcal{O}(n^2)$ 预处理所有子段 $[l, r]$ 是否能成为一个合法的 S 串。

对于 $f_{l, r}$ ，它的转移是比较平凡的，分 ()、(S)、(A)、(SA)、(AS) 五种情况转移即可。

对于 $g_{l, r}$ ，它的转移只有 AB 和 ASB 两种情况，但是如果 $\mathcal{DP}$ 转移处理得不够精细，就会出现一种方案被多次计算的情况。我们如何避免这种算重的情况呢？钦定 A 串的方案数仅能由 $f_{l, r}$ 贡献即可。

注意直接转移 $g_{l, r}$ 的复杂度是 $\mathcal{O}(n^4)$ 的。为了辅助 $g_{l, r}$ 的转移，我们可以再设 $h_{l, r}$ 表示有多少种确定所有尚未确定的字符的方案使得子段 $[l, r]$ 为形如 SB 的串，这样转移 $g_{l, r}$ 的复杂度就降至 $\mathcal{O}(n^3)$ 了。 $h_{l, r}$ 的转移也是平凡的。

代码实现

T3 回文

题目链接 AC

题解：

假设我们已经从序列的首部或尾部取出了一个数，记这个数在序列中另一次出现的位置为 $pos$ 。

在上述步骤的基础上，若我们再从序列的首部或尾部取出了一个数，并记这个数在序列中另一次出现的位置为 $pos'$ ，那么如果这两次操作都是合法的， $pos'$ 就一定会等于 $pos - 1$ 或 $pos + 1$ 。

以此类推，通过数学归纳法可以证明，若取数方案合法，那么对于前 $i~(i \in [1, n])$ 次操作取出的数，它们在序列中另一次出现的位置经排序后一定是连续的，也即它们构成的集合是 $[1, n \cdot 2]$ 的一个子段。

这样，我们仅需考虑第一次操作是在首部还是在尾部取数，然后用四个指针模拟接下来的取数操作即可。注意到由于每个数在序列中会且仅会出现两次，因此在合法的基础上贪心地取数是正确的。

代码实现

CSP-S 2022

T1 假期计划

题目链接 AC

题解：

首先，由于所有边权均为 $1$ ，因此我们可以 $\mathcal{O}(n^2)$ 求出任意两点之间的最短路径。

接着，我们把所有最短路不超过 $k$ 的两点连边，形成一个新图。

然后，我们对于每个点 $u$ ，求出在所有从 $1$ 号点经过恰好一个中转点到达点 $u$ 的路径中，点权和第 $1 \sim 3$ 大的三条路径。

最后，我们枚举景点 $\text{B}$ 和景点 $\text{C}$ ，然后将各自维护的三条路径合并，若合法则更新答案即可。

代码实现

T2 策略游戏

题目链接 AC

题解：

注意小 $\text{L}$ 会比小 $\text{Q}$ 先选择，那么在最优策略下，小 $\text{Q}$ 为了保证得分最小，肯定会选择小 $\text{L}$ 所选择的行中的最小值，因此小 $\text{L}$ 为了保证得分尽可能大，肯定会选择最小值最大的一行。

综上所述，问题转化为在子矩形内部选择一行，使得这一行的最小值最大，求出这个最小值。

注意到对于一个非负数而言，选择最小的数和其相乘一定最优；对于一个非正数而言，选择最大的数和其相乘一定最优。因此，我们可以先求出数组 $\text{B}$ 的子段 $[l_2, r_2]$ 内的最大值和最小值。

为了避免大量的分类讨论，我们不妨考虑求出数组 $\text{A}$ 的子段 $[l_1, r_1]$ 内的最大值、最小非负数、最小值、最大非正数和四个值。对于前两者，若数组 $\text{A}$ 的子段 $[l_1, r_1]$ 内存在非负数，那么我们将二者和 $\text{B}$ 中选出的最小值相乘，取乘积的最小值即可；对于后两者，若数组 $\text{A}$ 的子段 $[l_1, r_1]$ 内存在非正数，那么我们将二者和 $\text{B}$ 中选出的最大值相乘，同样也取乘积的最小值即可。最后，再取二者所得答案的最小值即可。