2025.11 复习

· · 个人记录

我咋啥都不会。

\color{red}\text{P1117 优秀的拆分}

Problem

多测，每次给定 s，求 s 的所有子串的所有拆分中，有多少个是 \operatorname{AABB} 的形式。

T \le 10$，$n \le 3\times 10^4 1.5s, 512MB
Sol
$\operatorname{ABAB}$ 的形式比较好通过 $\operatorname{LCP \& LCS}$ 统计？ 扩展：求区间复制串数 #### $\color{green}\text{P1186 玛丽卡}
Problem

求删边最短路。

n \le 1000$，$1\le m \le \frac{n(n+1)}{2} 1s, 128MB
Sol

先跑出一棵最短路树。然后只考虑 1 \leadsto n 的路径。对于不包含在这上面的边 (u, v)，求出 1 \leadsto u，v \leadsto n 在 1 \leadsto n 这条路径上第一个离开/进入的点，记为 l, r，然后对 [l, r] 内的点 \operatorname{chkmax} 即可。

Q：可能有多条 1 \leadsto u 的最短路，选择的 l 是否会有问题？

A：不会。对于两个离开点 i, j，找到 i \leadsto u 的第一条边，我们对这条边算贡献的时候，就可以算对了。对于进入点同理。

\color{green}\text{P1852 跳跳棋}

Problem

给定 a, b, c, x, y, z。分别表示三颗珠子的初始位置和目标位置（珠子间相同）。每次可以遵循跳棋的规则进行一次操作。问是否可以达到，并求出最少步数。

值域 10^9

1s, 125MB
Sol

先判断是否合法，由于操作是可逆的，可以直接求出终态（2y=x+z）判断是否相等。

找最少步数我们难以找到一个类似于拐弯的地方。但是我们发现一个状态想要缩小的话只有一步，这是一个类似于树的结构，然后需要找的是 LCA。二分即可。时间复杂度是两个 \log。

\color{red}\text{P2135 方块消除}

Problem

给定 n 个相邻的区域，每个区域有长度 l_i 和颜色。对相同颜色的长为 l 一段消除的代价为 l^2，求最大代价。

n \le 50, l_i \le 20 1s, 512MB
Sol

考虑区间 DP。

但是发现对于 111100001111 这种情况是难以处理的，因为正解应该是先消 0 再一起消 1。但是无法记录当前区间剩余段的长度&颜色（时空难以接受）。考虑简单的变一下，变为 f_{l, r, k} 表示消除了 [l, r + k]（r\sim r+k 这一段同色）这一段的最大代价。

转移则直接扩展 k 或枚举断点（因为这样的话要消一定要）即可。

\color{blue}\text{P3286 [SCOI2014] 方伯伯的商场之旅}

Problem

对于一个 n 堆石子 p_{1..n}，每次可以移动一堆石子到另一堆石子上，代价为距离乘石子数，令 p 的代价为其移成一堆的最小代价。

定义一个 p(x) 表示 x 在 K 进制下每一位构成的序列。对 L \le x \le R，求出 p(x) 的代价和。

L \le R \le 10^{15}$，$2 \le K \le 20 1s, 125MB
Sol

最小代价是都移到中位数的位置。暴力的想法是枚举中位数的位置，但是这样会很麻烦，因为会有两个限制（L + x > R，R + x > L），并且可能会有两个位置都有中位数。考虑一下这个东西的本质，就是类似于左右移导数均小于 0，由于和在 DP 的过程中是可计算的，因此可以直接使用这个东西来进行调整：先都移到 1，然后再枚举 1\to 2，2\to 3 等过程中减小的代价。

\color{green}\text{P3327 [SDOI2015] 约数个数和}

Problem

求 \sum_{i\le n} \sum_{j \le m} d(ij)。

n, m \le 10^5 1s, 125MB
Sol

知道 d(ij) = \sum_{x|i, y|j} [x \perp y] 即可。证明这玩意可以直接把 i,j,ij 质因数分解后考虑。

\color{blue}\text{P3586 [POI 2015 R2] 物流 Logistics}

Problem

给定数组 a，每次单点修改。或给定 c, s，每次选出 c 个正数减一，问能否操作 s 次。询问的修改不会对序列造成真正的修改。

Sol

有一个比较简单的贪心，就是每次选择最大的 c 个，但是这样并不好维护。考虑把 a_i 填到次数里面去。由于 a_i \ge s 的时候只能填 s 次，先把这些数扔出去。把每一次选出的集合列成一行。则填入 a_i 的时候是从上到下扔进没有满的集合。然后你发现这个东西只需要判定，因此我可以直接把没有填满的列接着填而不是从上到下填（因为这时候一定不会产生重复）。于是只需要维护 a_i < s 的 \sum a_i 与 a_i \ge s 的 i 的数量。可以使用 BIT 维护。

\color{blue}\text{P11368 [Ynoi2024] After god}

Problem

有两个初始为 0 的序列 a_{1..n}，b_{1..n}，每次修改给定 x, y，表示 a_x \gets y，然后对 i = 1, \dots , n 将 b_i 加上 \max_{j \le i} a_j，然后查询 \sum_{i \le x} b_i。

n,m \le 10^6$，$1\le x,y \le n 2.5s, 512MB
Sol

你想对这个东西直接上历史和，但是失败了，因为 \operatorname{chkmax} 操作没法子拆。使用单侧递归的技巧是 2\log 的。想想这玩意求的实际上是什么：把 \max a 按时间从上到下拆开变为 c_{1..t, 1..n}。然后求和是 \sum_{i \le x, j \le t} c_{j, i}，即矩形和。区间改值是一个上下左有边界的矩形 \operatorname{chkmax}，我们直接历史和失败的原因是因为上下界均有限制并且没法差分。考虑换成从左到右扫描线（即交换求和顺序），于是就可以直接维护历史和做到线对了。

\color{green}\text{CF1342F Make It Ascending}

Problem

给定长为 n 的序列 a，每次可以把一个数合并到另一个数上，要求合并完后的序列单调递增，求出最小操作次数即方案。多测。

$7s, 500MB
Sol

直接的不是很好做，因为可能涉及到插入。直接对最后的序列 DP（按合并的位置的顺序），由于值域是很大的，因此把答案扔进状态：f_{i, j, S} 表示当前用了 i 个集合，第 i 个集合合并的位置在 j，用了 S 中的数的情况下最后一个子集的和的最小值。转移枚举超集，新的 j' 一定是 S 中合法的里面最小的。时间复杂度是 O(n^23^n)。

trick：定义域和值域的交换。

\color{green}\text{P1251 餐巾计划问题}

Problem

总共 n 天，第 i 天需要 r_i 块餐巾。餐巾可以购买，或将用完的餐巾快洗或慢洗。三项操作每个餐巾分别花钱：p_1,p_2,p_3（递减的非负整数），三项操作花费时间 0,t_2,t_3（递增）天。用完的餐巾可以延期送洗，问满足每天要求的最小费用。

n\le 2000, 1 \le r_i \le 10^7, 1\le p_1, p_2, p_3 \le 10^4 4s, 125MB
Sol

对每天拆点为 (i_0, i_1)。令 (u, v, [l, r], p) 表示 u 连向 v，流量在 [l, r] 之间，费用为 c。

连边：

对于 i \in [1, n]，连边 (i_0, i_1, [r_i, r_i], 0)，(i_0, (i+1)_0, [0, +\infin), 0)，(0, i_0, [0, +\infin), p_1)，(i_1, (i+t_2)_0, [0, +\infin), p_2)，(i_1, (i+t_3)_0, [0, +\infin), p_3)，(i_1, 0, [0, +\infin), 0)。

然后求上下界无源汇最小费用可行流。

\color{green}\text{P1361 小M的作物}

Problem

小 M 现在有 n 种作物，第 i 种作物种植在 A 中种植可以获得 a_i 的收益，在 B 中种植可以获得 b_i 的收益，小 M 还找到了规则中共有 m 种作物组合，第 i 个组合中的作物共同种在 A 中可以获得 c_{1,i} 的额外收益，共同种在 B 中可以获得 c_{2,i} 的额外收益。

求最大种植收益。

2 \le n \le 10^3, 1 \le m \le 10^3 2s, 250MB
Sol

二者选其一，考虑最小割建模。

对于 i\in[1, n]，连边 (s, i, a_i), (i, t, b_i)。

对于第 j 个作物集合 S_{j}，连边 (j_A, t, c_{2, j}), (s, j_B, c_{1, j})。对 i \in S_j，连边 (i, j_A, +\infin),(i, j_B, +\infin)。

答案为 (\sum a_i+b_i) + (\sum c_{1, i}+c_{2, i}) - \operatorname{mincut}。

\color{blue}\text{P3978 [TJOI2015] 概率论}

Problem

求 n 个点的有根二叉树的叶子节点数的期望（两两不同）。

Sol

先考虑 DP。令 f_i 表示 i 个点的不同构二叉树个数，g_i 表示其叶子的个数和。则 \frac{f_i}{g_i} 即为所求，有：

f_i = \sum_{j = 0}^{i-1}f_jf_{i-j-1} g_i = 2\sum_{j=0}^{i-1}f_jg_{i-j-1}

初值：f_0=1，g_0=0, g_1 = 1。

感觉这个很有一个卷积的形式，我们使用生成函数求出这两个的通项。

卡特兰数（即 f）的生成函数 C(x) = \sum_{n \ge 0} C_nx^n。拆开，有：

\sum_{n \ge 0} C_nx^n = 1+\sum_{n > 0} \sum_{i=0}^{n-1}C_iC_{n-i-1}x^n = 1+x\sum_{n > 0} \sum_{i=0}^{n-1}C_ix^iC_{n-i-1}x^{n-i-1} = 1+x\sum_{i\ge0}C_ix^i\sum_{j\ge0}C_jx^j = 1+xC^2(x)

解得：C(x) = \frac{1 \pm \sqrt{1-4x}}{2x} = \frac{2}{1\mp\sqrt{1-4x}}。带入 C_0=1 可以知道只有 \frac{1-\sqrt{1-4x}}{2x} 这一组解。

使用牛顿二项式定理拆开 \sqrt{1-4x}：

(1-4x)^{\frac12} = \sum_{n \ge 0} \binom{\frac12}n(-4x)^n

然后把组合数拆成下降幂后再展开：

=\sum_{n \ge 0} \frac{(-1)^{n-1}(2n-3)!!}{n!2^n}(-4x)^n =\sum_{n \ge 0} -2\frac{(2n-2)!}{(n-1)!n!}x^n

带入 C(x)。

C(x) = \frac{1+\sum_{n \ge 0} \frac{(2n-2)!}{(n-1)!n!}x^{n}}x

常数项消了，得到。

C(x) = \sum_{n \ge 0} \frac{(2n)!}{n!(n+1)!}x^{n}

我们推导 G(x) = \sum_{n \ge 0} g_nx^n。带入转移式：g_i = 2\sum_{j=0}^{i-1}f_jg_{i-j-1}。

G(x) = x+2\sum_{n\ge 2}\sum_{i=0}^{n-1}f_ig_{n-i-1}x^n = x+2x\sum_{n\ge 2}\sum_{i=0}^{n-1}f_ix^ig_{n-i-1}x^{n-i-1}

由于 g_0 = 0，可以得到：G(x) = x+2xC(x)G(x)。

故 G(x)=\frac{x}{1-2xC(x)}。带入 C(x)=\frac{1-\sqrt{1-4x}}{2x}：

G(x)=\frac{x}{\sqrt{1-4x}} =x\sum_{n\ge0}\binom{-\frac12}{n}(-4x)^n =x\sum_{n\ge0}(-1)^n\frac{(2n)!}{(n!)^2}x^n

得到 g(n) = \frac{(2n-2)!}{((n-1)!)^2}。则 \frac{g(n)}{f(n)} 为：

\frac{\frac{(2n-2)!}{((n-1)!)^2}}{\frac{(2n)!}{n!(n+1)!}} = \frac{n^22(n+1)}{2n(2n-1)}=\frac{2n(n+1)}{2(2n-1)}

至此，我们完成了这道题。

\color{green}\text{P3599 Koishi Loves Construction}

Problem

给定 n，要求构造两个 1\sim n 的排列 a, b 满足 a 的前缀和在模 n 意义下两两不同，b 的前缀积在模 n 意义下两两不同。

n \le 10^5 1s, 125MB
Sol
$b$ 的构造： + 由于最后乘 $n$ 一定会让积变为 $0$，因此一定是把 $n$ 放在最后。当 $\prod_{i < n} i \bmod n=0$ 时无解。考虑如下构造：$1 \times \frac12\times\frac23\times\frac34\times\frac45\times\frac56\times\dots\times\frac{n-2}{n-1}\times n$。由于 $\frac1i$ 在 $\bmod n$ 意义下两两不同，所以 $1-\frac1i$ 也一定两两不同。 + 把它和第一问关联一下。由于 $n$ 只有 $2, 4, p$，因此找一个原根，对 $g^k$ 做类似构造即可。 #### $\color{red}\text{P3447 [POI 2006] KRY-Crystals}
Problem

给定 n，m_{1..n}。求满足 0\le a_i\le m_i 且 \oplus a_i=0 的序列 a 的个数。

###### Sol 有一个 $O(2^nV\operatorname{poly}(n))$ 的做法是从大到小考虑每一位，然后记录有没有顶到上界。 但是异或的性质非常好啊，你发现如果现在有一个上界是 $1$ 或没有上界就可以剩下的位随便选，然后用这一个 $1$ 来补。于是从高到低枚举 $i$，表示第 $i+1\sim 32$ 位这些位都是满的。然后枚举这一位第一个没有填满的地方，让它作为调整位，记为 $j$。则 $1\sim j-1$ 的位置都是满的，它们在剩下的位数中的贡献即为它们的低位组成的数。对于一个 $j$，需要统计 $j+1\sim n$ 的位置异或和与前面相同的方案数（未填满的贡献是 $2^k$），这个显然需要进行一个 DP。令 $f_{k, 0/1}$ 表示 $k\sim n$ 这些数的第 $i$ 位异或和为 $0/1$ 的方案数。时间复杂度 $O(n\log V)$。