2025 长训第二周 (1001 to 1006)

杂题

P1758 [NOI2009] 管道取珠

考虑平方的组合意义，实际上就是求满足生成序列一样的两种操作方案 A,B 形成的有序对 $(A, B)$ 的个数。

那么我们直接设 $d p_{a, b, x, y}$ 表示第一种操作到 $a, b$ ，第二种操作到 $x, y$ ，生成的序列一样的方案数，发现由于 $a + b = x + y$ 可以压掉一维，剩下的滚动数组即可。

P5307 [COCI 2018/2019 #6] Mobitel

如果直接设 $d p_{i, j, x}$ ， $x$ 代表乘积，状态数有点爆炸。

考虑整除分块的结论，即 $⌈ \frac{n}{i} ⌉$ 只有 $O (\sqrt{n})$ 种结果，于是考虑把状态改写为：

$d p_{i, j, x}$ 表示到格子 $(i, j)$ ，至少乘上 $x$ 可以 $\geq n$ 的方案数。第三维根据整除分块离散化一下即可。

1002【模拟赛 #4】

模拟赛 T1

一种“双序列二分”技巧：

对于当前的 $k$ ，分别取两个序列的前 $\frac{k}{2}$ ，如果第一个序列的 $\frac{k}{2}$ 比第二个序列的小，那么第一个序列的前 $f r a c k 2$ 一定都处于总的前 $k$ 小中。

这样子每次可以排除掉 $\frac{k}{2}$ 个元素，复杂度是 $O (\log n)$ 的。

模拟赛 T2 a.k.a CF1672D

因为染色时间是比较重要的，而又是树形 dp 题，所以染色时间是 dp 状态中的一个重要组成。

每个节点存储四种状态：在父亲边之前被染色，在父亲边被染色，在父亲边之后被染色，不被染色。

模拟赛 T3

神秘结论题

模拟赛 T4

数据结构维护 dp，一种类似扫描线的东西。

1003【模拟赛 #5】

模拟赛 T1 a.k.a. P12572 [UOI 2023] An Array and Addition Again

先将每个 pos 设置为 1，再将有需要的 pos 设置为 2，最后模拟从后往前加加加，类似于二进制凑一个数的过程。

模拟赛 T2 a.k.a P11340 [COI 2019] TENIS

按照吃人的关系建边，发现只有缩点后的 DAG 中的头部 SCC 才能吃掉所有人。

对应到序列上，其实就是第一个 $i$ 满足三个序列的前 $i$ 个元素构成的集合都相等。

考虑求这个 $i$ 。把每个数的出现位置，按照最小和最大看成区间 $[l_{k}, r_{k})$ ，那么 $c$ 就不能被任意区间包含。

怎么维护它们呢：

设 $p_{j} = \sum [l_{k} \leq j]$ ， $q_{j} = \sum [r_{k} \leq j]$ ，那么这个 $i$ 满足 $p_{i} = q_{i}$ 。

我们不妨维护一个序列表示 $p_{j} - q_{j}$ ，那么第一个为 $0$ 的位置就是我们要找的。又发现序列非负，所以找 $0$ 其实就是找最小值。

然后就可以做了，使用线段树维护，查询时使用线段树二分即可。

模拟赛 T3 a.k.a. CF2063F2 Counting Is Not Fun (Hard Version)

感觉和 T2 比，这道更简单一点？

考虑外层有一个括号之后，内层加一个括号，其实就是把外层序列的贡献减掉，再加上内层贡献，最后加上外层的加完之后剩下的贡献。

可以简单维护啊。但是还有内层括号，外层再套一个的过程呢？

这个就不好维护了。不过我们可以考虑时光逆流，从后往前考虑，加括号变成了删括号。此时就只涉及某括号内的贡献以及包含它的括号的贡献。

这个可以直接维护，先预处理出每个括号的最小的包含它的括号，然后删除的时候用个并查集之类的东西维护一下就行。

模拟赛 T4 a.k.a. P12573 [UOI 2023] An Array and XOR

待补。

1006【模拟赛 #6】

模拟赛 T1 a.k.a. P8048 [COCI 2015/2016 #4] ENDOR

把“撞在一起之后反弹并改变权值”改成“撞在一起之后改变权值但不反弹”，问题就变得简单了。

那么，颜色不变点的贡献容易计算。变的点在不同不变点中会形成若干个段，这些段只有 40 种本质不同的贡献，因此可以直接维护。

模拟赛 T2

我想起来去年多校联测写过一道 key observation 一模一样的题，当时场切了还高兴了一阵子。

考虑最终序列能被生成的充要条件是，将其相同值连续段压缩成一个一个值后，为原来序列的子序列。

而且这个压缩连续段之后，相邻不相同，对解决“不能有 $k$ 个相邻相同”有很好的辅助作用。

首先考虑求出原序列的子序列：设 $f_{i, j}$ 为长度为 $i$ ，以 $j$ 结尾的子序列个数。每次以 set 的方式更新（而不是加法）。然后使用一个 $s_{i} = \sum f_{i, x}$ 可以把字符集部分的复杂度压掉。

由于求出的子序列邻项互异，所以一种子序列生成的最终序列个数只和它的长度有关。

然后对于每个长度为 $i$ 的子序列，我们来考虑它能扩展成多少个“不能有 $k$ 个相邻相同，长度为 $n$ 的序列”。这是一个类似于背包问题的东西，可以前缀和进行转移。设生成方案数为 $t_{i}$ ，那么最终答案就是 $\sum s_{i} t_{i}$ 。

模拟赛 T3

关于一个子串的出现次数，其实就是两边的出现次数加起来，再加上一个合并之后新的出现次数。

所以我们只要维护头尾 $m - 1$ 个字符的前后缀。

先将序列长度扩展到 $\geq m$ 。然后你会发现拼接在一起的时候，各种前缀之间有一定的不变性。

于是可以使用矩阵乘法优化转移。至于两种特定前后缀拼接的方案，这个是可以先 KMP 一下，然后就可以丢到转移矩阵里当系数了。

模拟赛 T4 a.k.a. UOJ421 前半部分

待补。