省选-做题练习 2

20260706

P3706 [SDOI2017] 硬币游戏

P3706 [SDOI2017] 硬币游戏。

这个需要用高斯消元来解决，因为这是无穷的概率。

我们考虑对一个状态去加东西。

对于一个未终止的状态 $N$ 如果放第 $i$ 个人的串 $s$，一定会在其中一个时刻结束，胜者不一定是 $i$。

方程：

$$\frac{1}{2^m} \cdot \mathbf{1} = \sum_{j=1}^{n} x_j \cdot \sum_{k=1}^{m} [\text{pre}(i,k) = \text{suf}(j,k)] \cdot \frac{1}{2^{m-k}}$$

还需要一个：

$$\sum_{i=1}^n x_i = 1$$

随便替代前面一个就行了。因为前面的方程应该有冗余。但是这样有问题，会有负数。

所以我们用前面的 $n$ 个方程算出结果之后放缩一下就行了。

题解是加那个归一化方程，然后直接当成 $n+1$ 个未知数，最后一个不用管，前面一定是对的，这个写法还行。

20260707

CF432D Prefixes and Suffixes

CF432D Prefixes and Suffixes。

这种字符串匹配问题自然想到 KMP。

我们发现这道题就是对于 $n$ 的 $kmp_n$ 表示最长的既是前缀又是后缀的东西，然后可以一直 kmp 下去。

至于出现次数，可以 dp，因为我们发现这个是一个可以互相贡献的递减序列，$f_i$ 表示长度为 $i$ 的前缀的出现次数。初始的时候 $f_i$ 为 $1$，然后只需要 $f_{kmp_i} + = f_i$ 就行了。

CF1729F Kirei and the Linear Function

CF1729F Kirei and the Linear Function。

我们发现模 $9$ 是有性质的，只需要每一位的和模就行了。然后我们对于那个式子只需要枚举 $a\bmod 9$ 和 $b \bmod 9$ 就行了。

CF825F String Compression

CF825F String Compression。

性质：要选一定选最小循环节。

我们设 $f_i$ 表示到了 $i$ 的最小位数：

$$f_i = \min\{f_{j-1}+cost(i,j)\}$$

然后问题就变成了怎么求 $cost$ 了。我们需要找到这个子串的最小的循环节，所以我们想到了 KMP。直接对于每一个 $j$ 进行 KMP 预处理。

最小循环节长度就是 len - next[len]，需要保证总长度除得尽。

CF17E Palisection

CF17E Palisection。

正难则反，考虑不相交的。

设 $L_i$ 表示 $i$ 开头的回文串的个数，$R_i$ 表示 $i$ 结尾的回文串的个数。

然后对 $R_i$ 做前缀和：

$$\sum_{i=1}^n sum_i f_{i+1}$$

然后 $L$ 和 $R$ 的求法显然要 manacher 了。我们发现 manacher 是相当于对于一个范围的所有值都 +1，所以可以差分解决。

至于写法，马拉车的 # 可以保留，只需要计算不带 # 的答案（偶数位）。

AT_abc213_f [ABC213F] Common Prefixes

AT_abc213_f [ABC213F] Common Prefixes。

这道题还是让我们想到了 lcp 可以用 SA。

$$lcp(p, q) = \min\{ h_{rk_{p}+1}, h_{rk_{p}+2}, ..., h_{rk_{q}} \}$$

问题就转化为了：对于排名为 $p$ 的后缀，求所有以 $p$ 为一个端点的区间的 height 最小值之和，再加上该后缀自身的长度 $n - sa_p$（因为自己与自己的 LCP 就是后缀长度）。

感觉跟昨天有一道题很像。

注意 $h$ 数组的下标。。。表示 $i$ 和 $i-1$ 的。

CF1063F String Journey

CF1063F String Journey。

首先答案的长度是根号级别的。

还有一个性质是由于有 $u$，所以我们一定可以写成 $1,2\cdots,k$ 的形式。

我们枚举长度。当前长度的 $f_i$ 表示以 $i$ 开头能否形成长度为 $len$ 的序列。

值域转移，找到 $j>i+len-1$ 使得其 $f$ 为 $1$ 而且是 $i$ 的子串（这个很好判断，因为长度仅差 $1$）。

这个方法还是比较容易理解，只要能想清楚。

CF163E e-Government

CF163E e-Government。

感觉应该是建出来 AC 自动机，然后把那个询问塞进去。

但是这样会 TLE。我们可以观察性质。

这道题很强，我们发现一个点被选，其子树的所有的点都会被选。

所以我们对于加减操作只需要进行子树加和子树减，查询就单点查询。树状数组维护。

其中 fail 指向的表示这个子树上的父亲，因为这个一修改，前面的都要修改。

20260709

CF1968G2 Division + LCP (hard version)

CF1968G2 Division + LCP (hard version)。

首先先考虑 easy version，我们只需要二分长度，然后找这个长度和第一段的前缀一样的位置就行了。

然后 hard version 就根号分治一下即可。

对于 $k$ 很小的情况我们可以暴力，就用 easy version 的方法。

$k\ge \sqrt n$ 我们只需要枚举 lcp 长度即可。

CF1930D2 Sum over all Substrings (Hard Version)

CF1930D2 Sum over all Substrings (Hard Version)。

注意必须 $i$ 在 $l,r$ 中间。

性质：每一个 $1$ 都可以让附近这三个取到。

---

先说一下简单版，我们发现简单版就是 $p$ 为 $111$ 是 $q$ 为 $010$，$100$ 的时候可以 $010$，所以我们就可以想到对于每一个 $1$ 的位置我们需要顺便保证后两个也满足，于是就让下一位 $q$ 为 $1$ 就行了。

怎么扩展到所有子串？考虑 dp。我们设 $f_i$ 表示以 $i$ 为结尾的子串的贡献和。

当这一位是 $1$：

$$f_i = f_{i-3} + i$$

这里面，我们只需要让 $q_{i-1}=1$ 就行了。

否则：

$$f_i=f_{i-1}$$

AT_abc434_f [ABC434F] Concat (2nd)

AT_abc434_f [ABC434F] Concat (2nd)。

先看看这个：P1012 [NOIP 1998 提高组] 拼数，结论是比较 $a+b$ 和 $b+a$，证明方法：

证明

$a\times 10^n+b-(a+b)>b\times 10^m+a-(a+b)$ $a\times 10^n-a>b\times 10^m-b$ $a\times(10^n-1)>b\times (10^m-1)$

\tag{A} \frac{a}{10^m-1}>\frac{b}{10^n-1}

\tag{B} \frac{b}{10^n-1}>\frac{c}{10^r-1}

\tag{C} \frac{a}{10^m-1}>\frac{b}{10^n-1}>\frac{c}{10^r-1}

但是这道题求的是严格次小。

首先如果排序之后 $s_i+s_{i+1}=s_{i+1}+s_i$ 就输出最小的。

否则我们可以发现交换超过两个一定不优秀。所以我们现在只需要考虑交换相邻两项的情况了。然后，我们又发现，这个大概率是交换偏后面的数。

我们先定一个候选的 $s_{n-1},s_n$，可以发现，对于 $i\le n-3$，$i$ 这一位一定比那个候选的大，所以不成了。那对于 $s_{n-2},s_{n-1}$，确实有可能，因为这个的改变和最后一个的区间有交。

直接排序复杂度有问题，直接 random_shuffle 一下。

CF710F String Set Queries

CF710F String Set Queries。

第一种方法，枚举所有子串长度，$len\sqrt{len}$。

第二种，AC 自动机 + 二进制分组。我们按照二进制分组，依次插入，遇到大小相同的就进行合并。

20260710

P3121 [USACO15FEB] Censoring G

P3121 [USACO15FEB] Censoring G。

AC 自动机。

CF2209E A Trivial String Problem

CF2209E A Trivial String Problem。

首先肯定是 KMP，然后可以用 dp，从 $kmp_i$ 转移。但是有问题，需要从 $i-g_i$ 也就是最小的 border 转移。

P3311 [SDOI2014] 数数

P3311 [SDOI2014] 数数。

只需要用总数减去不合法的，然后不合法的用 AC 自动机。

但是 $n$ 太大了，需要数位 dp。

P2463 [SDOI2008] Sandy 的卡片

P2463 [SDOI2008] Sandy 的卡片。

二分答案。然后这道题的相同的定义需要差分。然后枚举了子串长度直接暴力哈希判断一个字串是否在 $n$ 个字符串里面都有。

P2336 [SCOI2012] 喵星球上的点名

P2336 [SCOI2012] 喵星球上的点名。

又利用到了之前的那个性质，种类数是根号级别的。

然后利用哈希，我们只需要先记录点名的串，直接对于每一只猫枚举长度然后处理出相同的，然后去重之后找到有哪些询问是点到了的。

AT_agc023_f [AGC023F] 01 on Tree

AT_agc023_f [AGC023F] 01 on Tree。

我们想尽可能把 $0$ 放到前面。我们考虑对于一个子树怎么排序，我们发现对于两个节点 $a,b$，更优的需要保证 $a_1\times b_0<b_1\times a_0$。

然后移项就变成了权值 $\frac{a_1}{a_0}$。

注意有的地方需要 1ll*。

20260713

P10013 [集训队互测 2023] Tree Topological Order Counting

P10013 [集训队互测 2023] Tree Topological Order Counting。

原来 $n\le 5000$。。。

首先设 $f_{i,j}$ 表示 $i$ 的拓扑序为 $j$ 的方案数。我们可以从父亲节点转移：

$$f_{x,j} = \sum f_{y,j} \binom{n-sz_y-1}{sz_y-sz_x-1}\times \frac{(sz_x-sz_y-1)!}{\prod\limits_{x 在 u 的子树,不在 v 的子树}sz_x}$$

后面那个是一个树的拓扑序计算个数的公式，每一个点需要在其子树的第一个位置出现。

预处理子树 $sz$ 积。然后需要前缀和优化。

$ans_i=\sum\limits_{j=1}^n b_j\times f_{i,j}\times \binom{n-j}{sz_i-1}\times \frac{sz_i!}{\prod_{k\in subtree(i)} sz_k}$

CF55D Beautiful numbers

CF55D Beautiful numbers。

显然是数位 dp。我们需要状压出来余数，于是...我们考虑 $1$ 到 $9$ 的最小公倍数 $2520$。

$f_{i,j,k}$ 表示到了 $i$ 位，前 $i$ 位模的余数是 $j$，前 $i$ 位的最小公倍数为 $k$。

$$f_{i,j,k} = \sum f_{i-1,(j*10+x)\bmod 2520,lcm(k,x)}$$

CF1228E Another Filling the Grid

CF1228E Another Filling the Grid。

先考虑最简单的只有一行的情况。我们发现没法直接做，所以容斥：$k^n-(k-1)^n$。然后我们需要考虑怎么扩展到 $n$ 行。

我们考虑容斥，求出有至少 $i$ 列不合法的情况数，然后容斥掉。

我们发现，这个相当于需要保证每行有 $i$ 个数被钦定最小值大于 $1$。于是每行的合法方案数：

$$k^{n-i}*(k-1)^i - (k-1)^n$$

然后最后的答案就是：

$$\sum_{i=0}^n(-1)^i\tbinom{n}{i}(k^{n-i}(k-1)^i-(k-1)^n)^n$$

P3488 [POI 2009] LYZ-Ice Skates

P3488 [POI 2009] LYZ-Ice Skates。

贪心：优先穿小号的鞋子。但是显然是错的。我们需要用二分图匹配，于是想到了 Hall 定理。

整个匹配存在的充要条件：对任意 $S$，都有 $|S|≤|N(S)|$。这道题需要：

$$\sum_{i=l}^{r} a_i \le (r-l+1+d) \times k$$

设 $b_i=a_i - k$ 然后我们需要变成：

$$sum(l,r) \le d\times k$$

只需要维护区间最小值就行了。

CF1204E Natasha, Sasha and the Prefix Sums

CF1204E Natasha, Sasha and the Prefix Sums。

//首先设 $t_i$ 表示从 $i$ 往后的前缀和都小于 $0$ 的情况数。枚举每一个位置，然后对于这个位置的每一个值我们求出来情况数。好像需要容斥。（貌似不对。）

我们设 $f_i$ 表示前缀和等于 $i$ 的，$g_i$ 表示前缀和大于等于 $i$。

有一个技巧是反射容斥。

我们发现对于一个 $i$，就相当于图上的路径需要和 $y=i$ 有交点。如果起点终点在直线两侧，答案就是总数。

如果不在同一侧，我们就要“反射”一下，这样并不会影响重点哦。

然后现在上移了 $n+i$ 步，下移了 $n-i$ 步。然后我们又可以求出总数了。

CF920F SUM and REPLACE

CF920F SUM and REPLACE。

这种线段树统称为势能线段树，因为一个操作一直进行下去就会变成同一个数。

P5840 [COCI 2014/2015 #5] Divljak

P5840 [COCI 2014/2015 #5] Divljak。

感觉二进制分组可过。

正确的方法是对原来的字符串建立 AC 自动机，然后对于每一个插入的字符串，看看它会对哪些有影响。

对于每一个 $P$，我们考虑塞进 AC 自动机中。假设路径是 $u_1,u_2,\cdots$，我们需要把这个点到 $fail$ 树的根结点的所有点的权值都加 $1$，然后还需要把 $lca(u_i,u_{i+1})$ 到根结点的减 $1$，于是我们发现这个是差分，可以用树状数组维护。

20260714

P2852 [USACO06DEC] Milk Patterns G

P2852 [USACO06DEC] Milk Patterns G。

直接二分长度，然后哈希。

CF628D Magic Numbers

CF628D Magic Numbers。

数位 dp。

$f_{i,j,0/1,0/1}$ 表示在第 $i$ 位，余数是 $j$，是否到达上下界。

不想写高精减？直接 $ask(r)-ask(l)$，单独计算 $l$ 这一位。

CF1553F Pairwise Modulo

CF1553F Pairwise Modulo。

$$p_i=p_{i-1}+\sum\limits_{j=1}^{i-1}(a_j\bmod a_i)+\sum\limits_{j=1}^{i-1}(a_i\bmod a_j)$$

左边那个我们用总和减去少了的数。我们只需要对于所有的 $[ka_i,(k+1)a_i)$ 内的数的个数 $x$，减去 $xka_i$。

由于数两两不同，所以是调和级数级别的。

然后对于右边那个，可以利用 $a_i \bmod a_j=a_i-\lfloor \frac{a_i}{a_j}\rfloor a_j$，对于所有 $ka_i\le m$ 的 $k$，给 $b_{ka_i}$ 加上 $a_i$，然后总和加上 $ia_i-\sum\limits_{j=1}^{a_i}b_j$。

注意，需要 min((k+1)*a[i]-1,mx)。

AT_agc027_d [AGC027D] Modulo Matrix

AT_agc027_d [AGC027D] Modulo Matrix。

首先，限制是相邻的，这个让我们想到了黑白格。

于是，我们先尝试填白格，我们尝试每一个格子用不同的质数乘起来，然后黑格就是相邻的格子的 lcm 然后加一。如果不用 $2$ 这个质数，可以直接用奇偶性证明。

然后把顺序打乱掉大小均摊可以过。

P2566 [SCOI2009] 围豆豆

P2566 [SCOI2009] 围豆豆。

看到数据范围很小，考虑状压。

首先肯定需要坐标，然后还需要一个状态。

我们打开了题解，发现了一个很神奇的结论：一个点向右做射线，与图形竖线的交点个数为奇数的时候，这个点在这个图形里面。

所以剩下的一个状态就是这个点向右的射线和自己的交点个数，然后我们只需要知道奇偶性，所以就是 $0/1$。

然后具体的我们可以使用 bfs，当然，SPFA 也行的。

我们每次遇到竖线，就需要记录。因为豆豆不能在边界，所以少特判了好多 hh。 注意代码中的 $x,y$ 不是坐标的，是 $x$ 代表行，$y$ 代表列。

CF1034D Intervals of Intervals

CF1034D Intervals of Intervals。

二分第 $k$ 大区间的值。

然后使用扫描线，移动右端点，维护左端点的答案。容易发现 $v(l,r)\ge v(l+1,r)$。所以我们可以维护。

现在，我们来考虑加入了 $r$，对于其中每一小段 $len$，我们假设最近的一次覆盖在 $c$，那么，对于所有 $l$：

• $l\le c$，这一段中不需要改变。
• $v<l\le i$，这一段中并集需要正价。

至于怎么知道那一些段和 $c$，我们需要 ODT。

然后最后的答案就是 $check(x)$ 中的过程值。

写法上需要先 split r 再 l。