2022.4 专题题解汇总

Alex_Wei · 2022-05-04 23:04:46 · 个人记录

记录了近期专题练习的所有 27 道题目的完整题解。题单见 链接。

cnblogs 链接。

2022.4.26 计数专题

A. CF830D Singer House *2800

自然设 f_i 表示一条有向路径的数量，考虑若干种情况。

1. 不经过根，2f_{i - 1}。

2. 恰好以根为一端，4f_{i - 1}。

3. 完全跨过根的两个子树，2f_{i - 1} ^ 2。

4. 根，1。

5. 完全跨过根但在一个子树内。设 g_i 表示两条不交的有向路径的数量，2g_i。

考虑算 g_i，发现当一条路径经过根又回到其子树，且另一条路径也在相同子树时，又要用到三条不交有向路径的方案数。

这样下去不行，结合 n\leq 400 的数据范围，我们再记录一维表示路径条数。

设 f_{i, j} 表示 i 树 j 条有向路径的方案数，转移枚举 j, k 表示左子树和右子树的原路径条数。

1. 不经过根，f_{i - 1, j} \times f_{i - 1, k} \to f_{i, j + k}。

2. 以根为一个端点，共有 2(j + k) 个端点可以与根相接，f_{i - 1, j} \times f_{i - 1, k} \times 2(j + k) \to f_{i, j + k}。

3. 不同子树的两条路径通过根合并成一条，枚举左子树和右子树的一个出点和一个入点，f_{i - 1, j} \times f_{i - 1, k} \times 2jk \to f_{i, j + k - 1}。

4. 相同子树的两条路径通过根合并成一条，枚举左子树还是右子树，然后从中选择一个入点和一个出点（减掉成环的情况），f_{i - 1, j} \times f_{i - 1, k} \times (j(j - 1) + k(k - 1)) \to f_{i, j + k - 1}。

5. 新增根单点，f_{i - 1, j} \times f_{i - 1, k} \to f_{i, j + k + 1}。

由于 i 每次加 1 最多只会湮灭掉一条路径，所以路径条数这一维只需要开到 n - i + 1。

答案即 f_{n, 1}，时间复杂度 \mathcal{O}(n ^ 3)。

代码。

B. CF1383E Strange Operation *2800

考虑一次操作的本质。

若为 00，10 或 01 则 0 的个数减 1，否则 1 的个数减 1。

直接对操作序列计数难以去重，因此一般均考虑对最终得到的 01 串计数。

我们发现每次操作可以减少相邻两个 1 之间的 0 的个数，或直接删掉下标相邻的两个 1 之间用于填放 0 的空隙，于是尝试设相邻两个 1 之间 0 的个数序列为 a，注意开头和结尾的连续若干个 0 也要算上。举例，若 s = \texttt {001011001}，则 a = \{2, 1, 0, 2, 0\}。

显然，一个 a 和一个 01 串一对应。因此考虑对 a 序列计数。

设原 01 串相对应的序列为 b。尝试探究 a 能被 b 生成的充要条件。

这个有点困难，我们先观察一次操作对 b 的影响，再反推条件。显然，每次操作可以将 b 的某个不为 0 的数减 1，或者删掉 不在开头或结尾 的 0。

发现 a 的两端元素的取值相对独立，因为在操作过程中它们一直不会被删去（换言之，直接删去某个数是导致重复的罪魁祸首。若不可以删去数，答案显然为 \prod\limits_{i = 1} ^ {|b|} (b_i + 1)）。根据乘法原理，答案首先乘上 a_1 和 a_{|a|} 的取值范围，即 (b_1 + 1)(b_{|b|} + 1)。接下来忽略掉 a 的两端和 b 的两端。

根据操作的具体内容，不难得到 a 被 b 生成的充要条件：存在序列 i 满足 1 \leq i_1 < \cdots < i_{|a|} \leq |b|，使得 a_j \leq b_{i_j}(1\leq j \leq |a|)。

容易判定 a 被 b 生成，形如子序列自动机。记录指针 p 表示当前 b 匹配到的位置，初始值为 0。贪心找到大于 p 的最小的位置 q 使得当前 a 匹配到的位置 a_j \leq b_q，令 j 加 1 且 p \gets q。重复该过程直到 j > |a|（成功）或 q 不存在（失败）。

根据判定过程就可以 DP 了。设 f_i 表示匹配到 b_i 的序列 a 的个数。a 的长度不影响转移，所以无需记录。

两种转移方法，一是枚举下一个 a 值是什么，并匹配到相应位置 j(i < j)，f_i 贡献给 f_j，但这样太劣了。直接考虑 f_i 对 f_j(i < j) 的贡献系数，不难发现，当 a 值小于等于 b_{i + 1} \sim b_{j - 1} 当中任何一个数时，匹配在 j 之前停止。因此贡献系数为 \max\left(0, b_j - \max\limits_{p = i + 1} ^ {j - 1} b_p\right)。

因为贡献系数主要与 j 有关，从 i 转移过去的角度考虑不方便。转换角度，j 受到 i 的贡献。

有 i, j 之间的最大值，容易想到单调栈。维护从左（栈底）到右（栈顶）递减的单调栈，那么当前栈中存储的所有元素即可以影响到 \max\limits_{p = i + 1} ^ {j - 1} b_p 的 b_1 \sim b_{j - 1} 的 后缀最大值 p_1 < \cdots < p_c。

我们发现，对于 i\in [p_{k - 1}, p_k)，它们对 f_j 的贡献系数都是 b_{p_k}。而对于 \geq b_j 的 p_k，p_k 左边的元素显然无法贡献至 f_j。而弹栈时只会弹出 \leq b_j 的栈顶，因此直接在弹栈的时候计算贡献即可。

需要使用前缀和优化求出一段区间的 f 值之和。时间复杂度线性。

代码。

C. CF1626F A Random Code Problem *2800

考虑一个朴素算法，根据期望的线性性，对每个 a_i 和 i \in [1, k]，枚举它在此之前被选中的情况 msk \in [0, 2 ^ {i - 1}]。继而算出它现在的值，乘以概率 \dfrac 1 {n ^ {1 + \mathrm{popcount}(msk)}}。时间复杂度 \mathcal{O}(n k2 ^ k)。

首先，我们的复杂度关于 n 只能是线性。因此我们尝试在值域上做点文章。

一个数被减掉的数值是很少的，但这并不意味着我们可以将所有数划分为很少个等价类。具体地，这个等价类的最小大小是 1\sim k - 1 的最小公倍数 P = 720720（不包含 k 因为不需要知道最后一次减掉的是多少）。

也就是说，对于 a_i，它的具体值不重要。我们只关心它模 P 之后的值，这是因为对于前 k - 1 次操作而言，任何数模 P 的值只会减小，不会增大，而 P\lfloor \frac{a_i}{P} \rfloor 这一部分的贡献容易计算。

基于以上推理我们尝试设计 DP。设 f_{i, j} 表示进行 i 轮后模 P 等于 j 的数的个数的期望值。转移是非常容易的。

对于 f_{i, j} 而言，若 j 被选择则以 \dfrac 1 n 的系数（概率）转移到 f_{i + 1, j - (j \mod (i + 1))}，否则以 1 - \dfrac 1 n 的系数转移到 f_{i + 1, j}。

算答案也很容易，即 \dfrac{\sum\limits_{i, j} f_{i, j} j} n，再加上 P\lfloor \frac {a_i} P \rfloor 这部分的贡献 \dfrac{\sum\limits_{i = 1} ^ n {P\lfloor \frac {a_i} P\rfloor}} n，最后乘以 n ^ k。

时间复杂度 \mathcal{O}(k \times \mathrm{lcm}(1\sim (k - 1))。

代码。

D. CF1615F LEGOndary Grandmaster *2800

考虑对于确定的 s, t 如何求解最小移动步数。

使用经典套路，将所有偶数位或奇数位的值异或 1，操作转化为交换相邻的 0 和 1（本题最核心的地方就在于对操作的转化，剩下来就不难想了）。

若转化后 s, t 中 01 个数不等，无解。否则最小移动步数即 s, t 对应 1 下标之差的和。

那么就简单了。应用在每个间隔处统计答案的技巧，设 f_{i, j} 表示考虑前缀 i，当前 s 中 1 的个数比 t 中 1 的个数多 j 的方案数，g_{i, j} 表示所有这样的方案的答案之和。