2023.7 做题记录

发表于 2023-07-11 分类于做题记录

山东省队集训 2022 Day1 T1

设 $f_{u, i, 0 / 1}$ 代表 $u$ 填了 $i$ ， $u$ 的子树内满足条件且最大值在 / 不在 $u$ 处取到的方案数．

对于 $0$ 的情况，转移显然．对于 $1$ 的情况，枚举在哪棵子树中取到最大值，统计方案．

这个复杂度有点寄，甚至过不了 50 分．加一车前缀和之后可以过．

正解就是这个换下根．嘴巴会了，没写代码．

山东省队集训 2022 Day2 T1

怎么连着两场都只有 T1 有分？

积木大赛的结论是区间正差分和．在平衡树上维护 $a_i - a_{i - 1}$ 和 $a_i - a_{i + 1}$ 即可支持区间翻转．撤销操作建操作树即可．注意修改的边界讨论．

可能是我写丑了，这题代码超级 /tuu，赛时还没调出来．ckain 赛时过掉了，拜谢 ckain．

Codeforces 1845E Boxes and Balls

补补补．题解．

Codeforces 1845F Swimmers in the Pool

补补补．题解．

洛谷 4140 奇数国

发现是计算询问是计算 $\varphi$ ．设 $n = \prod_{i=1}^{s}p_i^{k_i}$ ，有 $\varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}}$ ．

于是在线段树上维护区间乘积和区间质因数出现情况，第二个可以状压存．

洛谷 4569 [BJWC2011] 禁忌

多串匹配，首先建出 AC 自动机．

设 $f_{i, u}$ 表示前 $i$ 位匹配到 $u$ 节点的概率．有转移：

f_{i + 1, v} = f_{i, u} / |\Sigma|

其中 $v$ 代表匹配后走到的节点．注意匹配不能交，每次匹配后要走到 $0$ ．

DP 过程中每次匹配时统计答案，然后放矩阵里快速幂．

洛谷 6478 [NOI Online #2 提高组] 游戏

首先二项式反演一下，算钦定 $k$ 对非平局的方案．

设 $f_{u, i}$ 表示 $u$ 子树内钦定 $k$ 对点的方案数．子树的方案树上背包转移一下，然后分讨当前点的颜色，计算从自己子树中选一个异色点的方案数．

LOJ 6498 「雅礼集训 2018 Day2」农民

发现一个权值为 $x$ 的点能被走到的充要条件为：到根的链上所有作为左儿子的节点，其父亲的权值 $> x$ ；所有作为右儿子的节点，其父亲的权值 $< x$ ．

轻重链剖分维护每个点是哪个儿子和作为左 / 右儿子节点的父亲节点的权值的 minmax，然后就能转子树了．

LOJ 6499 「雅礼集训 2018 Day2」颜色

8 MB，强制在线．考虑分块．

bitset 存颜色出现情况，块间建 ST，卡卡空间．没了．

LOJ 6503 「雅礼集训 2018 Day4」Magic

大家写分治 FFT 都这么鬼畜的吗？题解．

LOJ 6508 「雅礼集训 2018 Day7」B

令 $f(x) = (ax + b) \bmod n$ ．考虑每个 $T_i$ 能够贡献到的 $p$ ．

若 $T_i = 1$ ，有 $f(x) \in [0, c)$ ，解得 $\overline{x} \in \overline{[-ia, c - ia)}$ ．

若 $T_i = 0$ ，有 $f(x) \in [c, n)$ ，解得 $\overline{x} \in \overline{[c - ia, n - ia)}$ ．

其中的诡异记号 $\overline{x}$ 表示 $x$ 在模 $n$ 意义下．

搞棵动态开点线段树维护．

LOJ 6066 「2017 山东一轮集训 Day3」第二题

先二分转化成判定性问题．

子树同构，一眼哈希．但是常用的树哈希方式并不支持限制深度的子树查询．

但是这题中树的儿子是有序的！这启发我们对括号序进行哈希．

对深度为 $k$ 的子树的括号序哈希可以通过枚举深度为 $k + 1$ 的儿子然后去除不需要的部分，剩下拼接起来．

这个复杂度是对的，因为每个点只会是一个点的深度为 $k$ 的儿子，那么枚举量就是 $O(n)$ 的．

洛谷 3175 [HAOI2015] 按位或

这个随机选数并上去的操作相当于每次在一堆集合中选一个并到自己上去，求的就是自己变成全集的期望步数．

若设随机变量 $x_i$ 表示 $i$ 被选到的步数，那么我们就是要求 $E(\max_{i \in S} x_i)$ ，其中 $S$ 是全集．这个形式非常 min-max 容斥啊！那么转化成求

\sum_{T \subset S} (-1)^{|T| - 1} E\left(\min_{i \in T} x_i\right)

考虑如何求后半部分那个期望，记 $f(S) = E(\min_{i \in S} x_i)$ ，再记 $p(S) = \sum_{T \subset S} p_T$ ，其中 $p_T$ 代表选中集合 $T$ 的概率，那么有：

f(S) = \sum_{i = 1}^\infty i \times p(S) \times (1 - p(S))^{i - 1}

这也是经典问题！错位相减可得 $f(S) = \frac{1}{p(S)}$ ．那么只需要处理子集和就行了，这个可以 FWT 解决．

LOJ 6138 「2017 山东三轮集训 Day4」Right

先暴力打不同 $p$ 下 $\operatorname{SG}(x)$ 的表，发现在 $p$ 是奇数的情况下， $\operatorname{SG}(x) = x \bmod 2$ ．在 $p$ 是偶数的情况下

\operatorname{SG}(x) = \begin{cases} 2 & x \equiv p \pmod {(p + 1)} \\ x \bmod (p + 1) \bmod 2 & \text{otherwise} \end{cases}

推到了结论之后，暴力循环展开，卡卡取模次数好像就能过．网上题解说的分块做法没咋看，以后补．

LOJ 3052 「十二省联考 2019」春节十二响

先考虑链的情况怎么做，发现整棵树是由两根链拼成的，这两条链之内的元素都构成祖先关系，不能放到一个段中．那么贪心地合并链即可．具体地，我们为两条链分别维护两个堆，每次取出两个堆中最大的元素，这两个元素需要放到一个段中，加到答案上就行．容易证明这个策略是正确的．

树的情况类似，按照贪心策略启发式合并每棵子树的堆，然后把本轮合并出的段当成元素塞到合并完的堆里即可．复杂度不会算．

LOJ 3450 「USACO 2020.12 Platinum」Sleeping Cows

这个部分直接照抄的 PPT．

直接把所有元素塞在一起排序．为了匹配极大，我们钦定不会被匹配的奶牛和牛棚，并要求这些牛棚在奶牛之前．

设 $f_{i, j, 0 / 1}$ 表示当前考虑了前 $i$ 大的元素，且有 $j$ 头未被钦定不被匹配奶牛还没有被分配，目前是否钦定过不被匹配奶牛．

若当前元素是牛棚，转移没有钦定过不被匹配奶牛的状态时，可以让这个牛棚空着，钦定过的状态则不能空着，必须匹配此前的一头牛．有转移

\begin{aligned} f_{i, j, 0} &= f_{i - 1, j, 0} + (j + 1)f_{i - 1, j + 1, 0} \\ f_{i, j, 1} &= (j + 1)f_{i - 1, j + 1, 1} \end{aligned}

若当前元素是奶牛，转移没有钦定过不被匹配奶牛的状态时，当前奶牛只能塞进待匹配的奶牛中，钦定过的状态则可以抛弃当前奶牛．有转移

\begin{aligned} f_{i, j, 0} &= f_{i - 1, j - 1, 0} \\ f_{i, j, 1} &= f_{i - 1, j - 1, 0 / 1} + f_{i - 1, j, 1} \end{aligned}

洛谷 8863 「KDOI-03」构造数组

首先计算操作次数 $m = \frac{\sum_i b_i}{2}$ ，若不能整除则无解．

考虑设 $f_{i, \mathrm{full}, \mathrm{part}}$ 表示前 $i$ 位已经变成一样的，使用了 $\mathrm{full}$ 次完整的操作， $\mathrm{part}$ 次一半的操作（只操作一个位置）的方案数，容易进行转移．

状态数都是 $O((\sum_i b_i)^3)$ 的，看似没法优化．然而我们发现，对于合法的状态，一定有

\mathrm{part} = \sum_{k = 1}^i b_k - 2 \times \mathrm{full}

那么状态就可以只记录 $\mathrm{full}$ ，转移时计算半个操作的数目 $\mathrm{part}$ 和空闲操作的数目 $\mathrm{none}$ ，枚举当前补上前面的 $k$ 个半个操作，有转移

f_{i, \mathrm{full} + k} \leftarrow f_{i - 1, \mathrm{full}} \times \binom{\mathrm{part}}{k} \times \binom{\mathrm{none}}{b_i - k}

Codeforces 1188C Array Beauty

设 $f(x)$ 表示长度为 $x$ 的子序列数目， $g(x)$ 为长度 $\ge x$ 的子序列数目，那么答案为

\sum_{x} xf(x) = \sum_{x} \sum_{i = 1}^x f(x) = \sum_{i} \sum_{x \ge i} f(x) = \sum_{x} g(x)

那么考虑求 $g(i)$ ．注意到方案和顺序无关，于是先把 $a_i$ 排序．外层枚举 $x$ ，设 $f_{i, j}$ 表示考虑了前 $i$ 个元素，长度为 $j$ 的子序列数目．转移枚举 $p$ ，使得 $a_i - a_p \ge x$ ，有转移 $f_{i, j} \leftarrow f_{p, j - 1}$ ．由于 $a$ 有序， $p$ 单调增，求和区间是一个前缀，前缀和优化即可．

单次 DP 时间复杂度 $O(nk)$ ，外层只用枚举到 $\frac{\max_i a_i}{k - 1}$ ，故总复杂度 $O(n \max_i a_i)$ ．

LOJ 3164 「CEOI2019」立方填词

首先长度不同的串肯定不会在一个方案中出现，于是按照长度分类考虑．

其次我们把字符串集合中的串翻转之后塞回去，新集合中的字符串就是所有合法字符串．

发现边上的字符貌似不是很重要，因为边上的字符实际上是被角上的字符约束住了，方案数可以预处理．

考虑如何写暴力．预处理 $w_{x, y}$ 表示 $x$ 开头 $y$ 结尾的合法字符串个数，枚举 $8$ 个角上的字符，把每条边的方案乘起来求和．这样做的复杂度是 $O(|\Sigma|^8)$ ，T 飞了．

考虑减少枚举量．好像有很多枚举实际上是没有用的！我们可以直接不去枚举最后一个点填什么，然后预处理一个 $f_{x, y, z}$ 表示有一个点没有确定，与这个点相邻的点分别填了 $x$ ， $y$ 和 $z$ 的方案数，直接乘上去就行．

发现如果一个点的相邻的点上的字符全都确定了，那么他的邻边方案可以直接用预处理的值，我们称这样的点被覆盖了．然后对于正方体上的 $8$ 个顶点，我们只用 $4$ 个点就可以全部覆盖．选取 $2$ 个对面不共面的对角线的 $4$ 个端点枚举即可．

洛谷 5278 算术天才⑨与等差数列

lxl 给的确定性做法，很有趣！

考虑区间 $[l, r]$ 内的元素能够被重排为等差数列有那些条件：

$\max_{i = l}^r a_i - \min_{i = l}^r a_i = k(r - l)$ ．
相邻两数差的绝对值是 $k$ 的倍数．
区间内没有重复数字．

条件 1 可以通过维护区间最值判定，条件 2 可以通过维护差分数组 gcd 来判定，条件 3 可以通过维护每个数字上一次出现位置来判定．都可以修改！

感觉不如哈希．

LOJ 3724 「SDOI / SXOI2022」小 N 的独立集

树上最大权独立集问题有一个经典做法，设 $f_{u, 0 / 1}$ 表示考虑了 $u$ 的子树， $u$ 是否选的最大权独立集．转移显然．

这题要对方案计数，考虑一个 DP 套 DP．设 $F_{u, i, j}$ 表示考虑了 $i$ 的子树， $f_{u, 0} = i$ ， $f_{u, 1} = j$ 的方案数．有转移

F_{u, i, j} + F_{v, s, t} \rightarrow F_{u, \max\{i + s, i + t\}, j + t}

看起来很对！但是状态数炸了．

进行一个性质的观察，发现 $0$ 状态不会比 $1$ 状态小很多．为了减少外层 DP 的状态数目，我们重新设计内层 DP 的状态．设 $g_{u, 0 / 1}$ 表示考虑 $u$ 的子树，是否钦定不选 $u$ 的最大权独立集．发现 $g_{u,1} \in [g_{u, 0} - k, g_{u, 0}]$ ，这样外层 DP 的只用记录 $g_{u, 0}$ 和 $g_{u, 0} - g_{u, 1}$ ．

LOJ 2545 「JXOI2018」守卫

注意到由于保镖只能往左边看，所以点 $r$ 上一定会有一个保镖．

然后计算点 $r$ 上向左看到的最后一个位置 $p$ ，则 $[p, r]$ 中的所有亭子都已经被看到了．且 $[l, p - 1]$ 中的亭子都看不到．这就将原问题拆成了两个子问题，若设 $f_{l, r}$ 表示覆盖区间 $[l, r]$ 的最小代价，那么有转移 $f_{l, r} \leftarrow \max\{f_{l, p - 1}, f_{l, p}\} + f_{p, r}$ ．

枚举 $r$ 之后 $l$ 往左扫就可以做到 $O(n^2)$ ．

LOJ 3569 「COCI 2021.11」磁铁

船新 DP 技巧．

令覆盖区间表示一个方案中第一个磁铁和最后一个磁铁构成的区间．

如果我们能够计算出覆盖区间长度为 $x$ 的方案个数，记作 $f(x)$ ，那么考虑将剩下的空位往磁铁中间插，这个部分的方案就是

\binom{l - x + n}{n} f(x)

那么问题转化为求 $f(x)$ ．

首先按照 $r_i$ 升序插入磁铁，这样只用考虑插入的磁铁吸引前面已经放下的磁铁．

设 $f_{i, j, k}$ 表示当前考虑了 $r$ 前 $i$ 小的磁铁，这些磁铁被分为了 $j$ 组，每组互不影响，总覆盖长度为 $k$ 的方案数．

转移考虑 $i + 1$ 对当前分组造成的影响，有：

插入到某一组的某一端，有转移 $f_{i, j, k} \times 2j \rightarrow f_{i + 1, j, k + r_{i + 1}}$ ．
新建组，有转移 $f_{i, j, k} \times (j + 1) \rightarrow f_{i + 1, j + 1, k + 1}$ ．
合并两个组，有转移 $f_{i, j, k} \times (j - 1) \rightarrow f_{i + 1, j - 1, k + 2r_{i + 1} - 1}$ ．

最终我们要将所有分组合并，有 $f(x) = f_{n, 1, x}$ ．

洛谷 8511 [Ynoi Easy Round 2021] TEST_68

观察样例发现很多点的答案是一样的！答案不一样的点貌似分布在两条链上！

继续观察可以发现，链尾的两个节点权值的异或和就是全局异或最大值．

于是就有做法了．先把全局异或最大值和构成最大值的点对弄出来，只有这两个点到根的路径上答案会不同．暴力处理两根链上的答案即可．

LOJ 3503 「联合省选 2021 A | B」滚榜

观察到最后求的是排名的方案数，而不是可能的 $b_i$ 的分配方式，这启发我们去考虑如何刻画可行的最终排列这一信息．

考虑如何判定一个排列可行．我们可以贪心地使分配的 $b_i$ 尽量的小，多的部分可以全部扔给最后一个人．

直接抛出结论，对于最终排列 $p$ ，最优的 $b_i$ 分配方式为 $b_i = b_{i - 1} + \max\{a_{p_{i - 1}} - a_{p_{i}}, 0\}$ ．

那么考虑设 $f_{S, x, i}$ 表示已经考虑了 $S$ 中的元素，最后一个考虑的元素是 $x$ ，当前的 $\sum_k b_k$ 是 $i$ 的方案数，转移考虑加入一个 $S$ 中没有的元素 $y$ ，对 $\sum_k b_k$ 的影响为 $(n - |S|) \times (\max\{a_x - a_y + [y > x], 0\})$ ，那么有转移

f_{S, x, i} \to f_{S \cup \{y\}, y, i + (n - |S|) \times (\max\{a_x - a_y + [y > x], 0\})}

初始化时注意第一个被考虑的元素需要盖过原序列中的最大值．