2024牛客暑期多校训练营 赛题总结
前言
这篇笔记记录我在 2024 年牛客暑期多校训练营的 10 场比赛中遇到并认为值得记录的赛题题解以及我的思考和收获。
总览
- 【01D】XOR of Suffix Sums
- 【02B】MST
- 【02G】The Set of Squares
- 【03A】Bridging the Gap 2
- 【03E】Malfunctioning Typewriter
- 【04B】Pull the Box
- 【04J】Zero
- 【06I】Intersecting Intervals
- 【07D】Interval Selection
- 【08G】Haitang and Rock Paper Scissors
- 【09C】Change Matrix
- 【10D】Is it rated?
笔记
【01D】XOR of Suffix Sums
题意
有一个初始为空的序列，给定 $q(q\le 5\times 10^5)$ 次操作，每次操作删去序列末尾的若干个数并新增一个数。在每次操作后，求序列所有后缀和的异或值，模 $2097152$。
做法
- 发现模数 $2097152=2^{21}$，即所有操作只需要考虑前 $21$ 位。
- 将每一位拆开来分别处理，由于加减运算涉及进位退位，计算答案的每一位需要维护前面的所有位。
- 后缀和 $s_i$ 可以用前缀和表示为 $p_n-p_{i-1}$，每次修改时前缀和只有一个位置发生变化；而计算每一位的答案只要看与 $p_n$ 相减后这一位为 $1$ 的 $p_{i-1}$ 有几个，可以在值域上建树状数组维护。
笔记
- 本题的关键点有两个：一是用前缀和来表示后缀和，把区间修改优化成单点修改；二是注意到每一位只受前面更低位的影响，因此分别用值域树状数组维护每一位所需信息的总复杂度也只有 $O(mod)$。
【02B】MST
题意
给定一个 $n(n\le 10^5)$ 个点 $m(m\le 10^5)$ 条边的无向图和 $q(q\le 10^5)$ 次询问，每次询问一个点集 $S$，求 $S(\sum|S|\le 10^5)$ 导出子图的最小生成树。
做法
- 考虑根号分治，度数大于 $\sqrt{m}$ 的结点不超过 $\sqrt{m}$ 个；对于度数较小的结点存储所有邻接边，对于度数较大的结点只存储连向度数较大结点的邻接边，这样所有点的邻接表大小都不超过 $\sqrt{m}$，需要考虑的总边数只有 $|S|\sqrt{m}$。
- 使用 Kruskal 算法求最小生成树，通过对边进行预排序并预处理出每个询问涉及的边，即可避免 $\log m$ 乘在根号上，总时间复杂度 $O(m\log m+|S|\sqrt{m})$。
笔记
- 复杂度高的原因是询问可能重复涉及度数较高的结点使得枚举边数过大，但这些结点大多邻接边都是连向小度数点的重复边，对 Kruskal 算法没有帮助。
- 另一种方法是用邻接矩阵存储度数较大结点的邻接边，然后只考虑连向询问相关结点的邻接边，思路同样是减少需要考虑的较大度数结点的邻接边。
【02G】The Set of Squares
题意
给定 $n(n\le 1000)$ 个数 $a_i(1\le a_i\le 1000)$，定义“所有元素乘积为完全平方数（记为 $x^2$）” 的多重集合为“好集合”。求给定数的所有子集中好集合对应的 $x$ 的和。
做法
- 分解质因数，所有质数的幂都是偶数的子集即为“好集合”，转化为背包问题；但 $1000$ 内的质数有 $168$ 个，背包状态有 $2^{168}$ 种。
- 注意到 $1000$ 以内的数可能出现两次及以上的质因数不超过 $\sqrt{1000}$，只有 $11$ 个，其余质因数最多出现一次。
- 因此可以将所有数按照大质因子分类，只要分别保证每个大质因子对应的数取了偶数个即可，剩下的小质因子构成背包状态互相转移，总时间复杂度 $O(n\cdot 2^{11})$。
- 代码实现时没有大质因子的数需要特别处理。
笔记
- 本题的突破点在于对数据范围的敏锐觉察力，以及巧用类似“根号分治”的思想，将大质数和小质数分开处理。
- 本题时间复杂度可以优化的本质原因在于大质因数对应的状态位并不需要全程维护，因为在使用一个数进行状态转移时最多涉及到一个大质因数，所以可以对每个大质因数对应的数进行集中处理，这样在每次集中处理时只需要考虑一个大质因数，并且集中处理完成后就可以抛开它，再也不用考虑了。
【03A】Bridging the Gap 2
题意
有 $n(n\le 5\times 10^5)$ 个人想要到河的对岸，每个人的耐力为 $h_i$，但此时只有一艘船，船至少载 $L$ 人，最多载 $R$ 人，每人每坐一次船需要消耗 $1$ 点耐力。求能否让所有人都到对岸。
做法
- 每个人至少需要向对岸走一次，且每次需要有 $L$ 个人回来带 $R-L$ 个人到对岸，因此问题关注的重点是每个人能回来的次数 $h’_i=\lfloor \frac{h_i-1}{2}\rfloor$。
- 每次贪心地选择耐力最大的人带到对岸，可以保证策略的最优性，这一过程相当于每次在 $h’$ 中选择最大的 $L$ 个减 $1$，最多能减的次数就是能带 $R-L$ 个人到对岸的次数。
- 上述问题的答案为 $\underset{t<L}\min\lfloor \frac{\sum_{i=1}^{n-t}h’_i}{L-t}\rfloor$，证明过程见笔记部分。
- 另一种更简单的做法：直接考虑累计所有人能贡献的总次数再进行使用，但这样需要保证每次对面至少要有 $L$ 人能回来，这一限制可以等价转换为每人最多贡献 $\lceil\frac{n-R}{R-L}\rceil$ 次，故答案为 $[\frac{\sum_i\min\lbrace h’_i,\lceil\frac{n-R}{R-L}\rceil\rbrace }{L}>=\lceil\frac{n-R}{R-L}\rceil]$。
笔记
- 每次选择数组 $x$ 中的 $k$ 个数减一，最多进行的操作次数为 $\underset{t<k}\min\lfloor \frac{\sum_{i=1}^{n-t}x_i}{k-t}\rfloor$，证明：
- 另一种做法中，由于需要的耐力总数 $\lceil\frac{n-R}{R-L}\rceil\cdot L$ 已经固定，为了限制每趟船上的人数不小于 $L$，可以阻止耐力过大的人用自己多余的耐力代替其他人，即等价地限制每个人最多贡献 $\lceil\frac{n-R}{R-L}\rceil$。
【03E】Malfunctioning Typewriter
题意
给定 $n(n\le 1000)$ 个长度为 $m(m\le 1000)$ 的二进制串。现有一台打字机，按下 0 或 1 后打出正确字符的概率为 $p$，打出相反字符的概率为 $1-p$。求按照最优策略进行打字 $nm$ 次，最终打出的字符串正好是 $n$ 个给定串的某种排列的概率。
做法
- 对 $n$ 个二进制串建立 Trie 树，目标相当于经过所有叶节点恰好一次，此时 Trie 树的每个结点对答案的影响是相互独立的，可以累乘得到答案。
- 考虑结点 $x$ 满足要求的概率，假设左右子结点分别为 $l, r$，计数数组为 $c$，则结点 $x$ 需要满足在被经过 $c_x$ 次的前提下恰好向左走 $c_l$ 次且向右走 $c_r$ 次，这一概率记为 $f(c_l,c_r)$，而 $f(i,j)$ 可以通过 DP 预处理出来。
笔记
- 打字过程中策略随时可能变化，且在序列上考虑涉及的状态数过多，因此应该在 Trie 树上考虑。
- 在 Trie 树中自上而下考虑，上方的结点处的讨论保证了到达下方结点的次数一定，因此每个结点对答案的贡献是独立的。
【04B】Pull the Box
题意
给定一个 $n(n\le 10^6)$ 个点 $m(m\le 10^6)$ 条边的简单无向图，初始时人在 $x$ 号点，需要沿着相邻的边将 $1$ 号点的箱子拉到 $n$ 号点，求最少需要多少步。
做法
- 朴素的想法是先将箱子拉到一个非割点，再从另一边将箱子拉到终点。
- 可以发现人在第一次与箱子接触后就没有必要与箱子分开了，因此问题被简化，只需要考虑两个步骤：到达箱子的邻接点、将箱子拉到终点。
- 第一步只需要预处理最短路即可；第二步将箱子拉到终点的过程在点上考虑比较复杂，而在边上考虑比较简单，每拉动一次相当于从一条有向边转移到相邻的一条有向边，因此也可以在边上 BFS 预处理出最短路。
- 然而在边上 BFS 的复杂度可能到达 $\Theta(n^2)$，注意到每个点的邻接表最多被遍历两次就可以使所有邻接边都被更新完毕，因此可以限制每个点最多访问两次，使得复杂度为 $O(n+m)$。
笔记
- 将一张图的边作为结点，并将相邻边对应的结点连接起来得到的新图称为“线图”，这是一种常见的问题转化方法。
- 本题的做法与线图有所不同，因为本题中的边是有方向性的，需要将每条边拆成两个点。
- 需要注意，即使原图边数较少，线图的边数也有可能达到原图点数的平方级别。
【04J】Zero
题意
给定一个长度为 $n(n\le 10^5)$ 的字符串，仅包含 0 或 1 或 ?，每个 ? 都有一半的概率变成 0 和一半的概率变成 1。对于一个明确的二进制串，定义全 1 子串 $[l,r]$ 的贡献为 $(r-l+1)^k$，其它子串的贡献为 $0$，其中 $k(1\le k\le 30)$ 为给定的常数。求给定字符串所有子串贡献和的数学期望。
做法
- 每个子串对期望的贡献为成为全 1 串的概率乘以全 1 时的贡献。
- 考虑 DP，但每考虑一位都需要由所有长度的子串贡献之和转移到长度加一的子串贡献之和，即由 $\sum_{i=1}^{x} a_i i^k$ 算出 $\sum_{i=1}^{x}a_i (i+1)^k$，其中 $i$ 为子串长度。
- 注意到 $k$ 的数据范围较小，即上式展开后的项数较少，尝试进行展开：
$$\begin{aligned}\sum_{i=1}^{x}a_i (i+1)^k &=\sum_{i=1}^{x} a_i(C_k^0\cdot i^k+C_k^1\cdot i^{k-1}+\cdots+C_k^k\cdot i^0)\\ &=C_k^0\sum_{i=1}^x a_i i^k+C_k^1\sum_{i=1}^{x}a_i i^{k-1}+\cdots+C_k^k\sum_{i=1}^{x}a_i i^0\end{aligned}$$ - 发现该值可以由 $k$ 个同构的项相加求得，因此可以将所有长度子串的共同贡献值按照长度的幂拆分成 $O(k)$ 组进行 DP，总时间复杂度 $O(nk)$。
笔记
- 本题的关键在于发现不同长度的子串贡献转移方程是同构的，不需要根据长度区分，可以一起转移。
- 将完整的式子写出来比较容易看出转移方法。
【06I】Intersecting Intervals
题意
给定一个 $n\times m(n\times m\le 10^6)$ 的二维数组，要求在每一行选择一个区间 $[l_i,r_i]$ 使得相邻行的区间 $[l_{i-1},r_{i-1}],[l_i,r_i]$ 有交集，求在此限制下所有区间中数之和的最大值。
做法
- 考虑 DP，记 $dp_{i,j}$ 表示已选好前 $i$ 行且第 $i$ 行包含第 $j$ 个数的方案的最大和。考虑从 $dp_{i,j}$ 转移到 $dp_{i+1,k}$（不妨设 $k>=j$），此时第 $i+1$ 行选择的区间必须包含 $[j,k]$，即左端点必须在 $[1,j]$ 中选择，右端点必须在 $[k,m]$ 中选择，这相当于在前缀和数组中找前缀最小值和后缀最大值。
- 预处理出第 $i+1$ 行的前缀和数组的前缀最小值和后缀最大值，分别记为 $pre$ 和 $suf$，上述过程即 $dp_{i+1,k}\leftarrow dp_{i,j}+suf_{k}-pre_{j-1}$，其中 $dp_{i,j}-pre_{j-1}$ 由转移起点决定，$suf_k$ 由转移终点决定，可以拆分开来。
- 再考虑相邻行间的所有转移，$dp_{i+1,k}$ 需要由 $\underset{j<k}\max\lbrace dp_{i,j}-pre_{j-1}\rbrace +suf_k$ 和 $\underset{j\ge k}\max\lbrace dp_{i,j}+suf_j\rbrace -pre_{k-1}$ 得到。
- 预处理出第 $i$ 行的 $dp_{i,j}-pre_{j-1}$ 前缀最大值和 $dp_{i,j}+suf_j$ 后缀最大值即可 $O(m)$ 完成行间转移，总时间复杂度 $O(nm)$。
笔记
- 本题的关键在于想清楚 DP 状态的设计以及转移的方式，应该算是比较常见的一种模型。
【07D】Interval Selection
题意
给定一个长度为 $n(n\le 2\cdot 10^5)$ 的序列 $a(0\le a_i\le 10^9)$ 以及一个正整数 $k$，求区间中出现过的数的出现频率都是 $k$ 的区间个数。
做法
- 枚举左端点 $l$，对于每一种 $a_i$ 的值，右端点 $r$ 都要满足 $[l,r]$ 之间恰有 $0$ 个或 $k$ 个 $a_i$，即 $r$ 需要位于 $l$ 右边第一个 $a_i$ 左侧或第 $k$ 个 $a_i$ 和第 $k+1$ 个 $a_i$ 之间，因此合法 $r$ 的个数即 $O(n)$ 个区间集合取交集后的大小。
- 当左端点变化为 $l+1$ 时，只有与 $a_l$ 和 $a_{l+1}$ 有关的 $O(1)$ 个区间会发生变化，因此问题转化为动态维护 $O(n)$ 个区间集合的交集大小。
- 对所有区间集合的补集进行区间加后，数组中 $0$ 的个数即为所求。上述任务可以用一个维护区间最小值以及最小值个数、支持区间加减的线段树完成。
笔记
- 判断一个问题能否用线段树来解决有两个关键点：一是需要支持的区间操作的标记能否直接作用于需要维护的属性上，二是父区间需要维护的属性能否由两个子区间的属性合并而来。区间加减对于区间最小值和最小值个数的影响可以直接计算，且区间最小值和最小值个数可以直接合并，因此本题可以使用线段树。
- 类似：https://ac.nowcoder.com/acm/contest/81604/B
【08G】Haitang and Rock Paper Scissors
题意
你需要按顺序与 $n(n\le 2000)$ 个人进行石头剪刀布，你已经预先知道每个人会出的手势，但你不能连续两局出同样的手势，且不能输给任何一个人。给定长度为 $n$ 的包含 $0,1,2,-1$ 的序列，其中 $0,1,2$ 分别代表剪刀、石头、布，求将 $-1$ 替换为 $0/1/2$ 的所有情况对应的最多能赢的局数之和。
做法
- 在每场对决中有两种手势可以出，因此不可能输，但最大化胜场数的策略是无法贪心的。
- 考虑 DP，每种前缀情况的备选策略都有两种，但不能拆分为两种状态来保存情况数。此时可以考虑将两种策略的收益作为状态的划分，即设计 $dp(i,j,k,l)$ 表示考虑前 $i$ 场，最后一场对方出 $j$，最后一场己方出 $j$ 的策略对应最高收益为 $k$，己方出 $(j+1)\bmod 3$ 的策略对应最高收益为 $l$，复杂度 $O(n^3)$，还需要优化。
- 注意到只有两种策略的收益差是重要的，其中一种的收益可以直接加入答案，因此可以删去状态的一维，最终复杂度 $O(n^2)$。
笔记
- 本题的关键点有二：一是意识到前缀每种情况的备选策略有且只有两种，二是想到可以将两种策略其中一种的收益直接存在外部答案变量中，只将收益差作为划分状态的依据。
【09C】Change Matrix
题意
有一个 $n\times n(n\le 10^5)$ 的矩阵 $a$，初始时满足 $a_{i,j}=\gcd(i,j)$。接下来有 $q(q\le 10^5)$ 个询问，每个询问将某一列或某一行的数同时乘上 $y(y\in[0,10^9+7))$ 并求此时的矩阵元素和。
做法
- 只有当矩阵所有元素都相同时，题述操作才易于维护，因此考虑将矩阵拆成若干所有元素相同的小矩阵。
- 根据 $\gcd(i,j)=\sum_{d|i,d|j}\phi(d)$ 可以将每个位置的元素拆分。此时矩阵相当于 $n$ 个小矩阵的和，第 $i$ 个矩阵的元素全为 $\phi(i)$，且第 $r$ 行第 $c$ 列对应原矩阵的第 $r\cdot i$ 行第 $c\cdot i$ 列。所有矩阵边长的和为 $\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor=O(n\log n)$。
- 预处理出 $[1,n]$ 中所有数的因数，修改第 $i$ 行/列时只要将 $d(i)$ 个矩阵都进行更新即可。
- 由于数据是随机生成的，每次询问的复杂度并非 $O(d(n))$ 而是均摊 $O(\log n)$，总时间复杂度 $O(n\log n)$。
笔记
- 本题的关键在于利用欧拉函数的重要性质 $x=\sum_{d|x}\phi(d)$。证明：
$$x=\sum_{d|x}\sum_{i=1}^n[\gcd(i,x)=d]=\sum_{d|x}\sum_{i=1}^{\lfloor\frac{x}{d}\rfloor}[\gcd(i,\frac{x}{d})=1]=\sum_{d|x}\phi(\frac{x}{d})=\sum_{d|x}\phi(d)$$
【10D】Is it rated?
题意
初始 rating 为 $r_0$，参加 $n(n\le 10^5)$ 场比赛。给定每场的表现分 $p_i$ 以及系数 $k(0.1\le k\le 1)$，rating 计算方式为 $r_i=kp_i+(1-k)r_{i-1}$，可以选择其中 $m$ 场改为 unrated，求最终的 rating 最高为多少。
做法
- 通项公式 $r_n=\sum_{i=1}^n (1-k)^{n-i}kp_i+(1-k)^n r_0$。
- 可以发现 $(1-k)^{200}<\epsilon$，即在以 $\epsilon$ 为绝对精度的情况下，最终得分只与最后进行的 $200$ 场比赛有关，最多只需要考虑 $200$ 场比赛。
- 分类讨论并 DP，时间复杂度 $O(200n)$。
- 答案有可能小于 $1$，此时绝对精度可能小于 $\epsilon$，因此要开到 $400$ 才能过题。
笔记
- 本题的关键在于利用精度限制发现对答案有意义的场数较少，这是一个实用的思路。
2024牛客暑期多校训练营 赛题总结