2025.10 做题记录

10.1

P12550

交换后无法换回来。等于把序列分成若干段，每段的价值为 AB 的逆序对数。

一段里不会有 $3$ 种字符，不会有一个划分两边相同，不会有一个划分两边字符集相同。

只有两个转移点，是当前包含两个字符的最远连续段的两端。

P8493

$c_{u}$ 的方案数是儿子为 $1$ 的数量，组合意义是选一个儿子让他为 $1$ ，即选一条链。

每个叶子的贡献为根到它以外的点乱选的 $\prod d_{u}$ ，区间 flip，线段树维护。

10.2

Q913

令 $k = l + r - n \leq 11$ ， $b e ll (k)$ 枚举中间哪些连通，要求出左右两个图在已经有一些点连通后的 MST。

只考虑图中的点，求 MST，扔掉没用的边，边数 $O (n)$ 。将中间所有点连通，求 MST，将连起来的点缩起来，点数 $O (k)$ 。

复杂度 $O (b e ll (k) k)$ 。

P9055

对于 $f (m)$ ，把 $0, \dots, m - 1$ 排成 $x$ 段，其中出现 $x + 1$ 次的排在前面，最后按相同的顺序在结尾加上第 $x + 1$ 次的数。这样每个 $l e n \geq m$ 的区间都合法。

对于 $f (i)$ ， $0, \dots, i - 1$ 一样排成 $min_{j < i} a_{j}$ 段，剩下要在段间插入一些数。假设当前在这个间隔已经有 $c n t$ 个数，在开头结尾加会有 $(i - 1) + c n t + 1$ ，中间会有 $2 (i - 1) + c n t + 1$ 的不合法段。

现在开头结尾各补 $i - 1$ ，再平均插在每个间隔中最优。

10.3

P6775

$m \geq n - 1$ 一定存在 $a_{n} \geq k$ 或 $a_{1} + a_{n} \geq k$ ，进入子问题。

$m = n - 2$ ，要选出一个子集，使得 $\sum_{x \in S} a_{x} = (∣ S ∣ - 1) k$ 。bitset。

Q14129

$i mod n$ 向 $n + i mod m$ 连边等价于 $i mod (n + m)$ 向 $(i + n) mod (n + m)$ 连边。

设 $a = n + m, b = n$ 。当做了 $a - b$ 步后，所有 $mod b$ 同余的点连通。接下来将进入 $i mod b$ 向 $(i + (a mod b)) mod b$ 连边的子问题。

对 $a - b$ 步进行二分，检查的时候如果点数还 $> k + 1$ 一定不连通，否则 $O (k)$ 检查。

CF1017G

一个点为黑色，要求到根路径上一个后缀操作次数大于等于路径长度。初始赋为 $- 1$ ，单点加，后缀和 max。

让 $u$ 的子树为白色，先清空子树内的操作次数，再在 $u$ 抵消掉到根的最大后缀和，即把最大后缀和重新减成 $- 1$ 。

10.7

Q12120

每个点在根在 dfn 序上变化的时候子树大小只有 $de g u$ 段。现在有 $O \sum d e g 1 u \times d e g 2_{u}$ 个矩形的值。

通过把儿子按 $s i z_{v}$ 排序再求 dfn 序，特殊处理掉父亲，再双指针，可以减少为 $O (\sum d e g_{u}$ 个矩形。扫描线。

Q8109

求一棵生成树出来。断 $k$ 条边将其在 dfn 序上分为 $O (k)$ 段，每段连续且内部连通。段间的边数可以预处理二维前缀和与实际比较。缩点后判断。

10.9

dmy3349

给出三个整数 $n, k, d$ ，在 $n$ 个节点有标号无根树中随机选择一棵树，并把 $1 \sim n - k$ 号点及其边删除，在满足剩下的连通块大小都不超过 $d$ 的情况下，求剩下的连通块的期望个数。

$n \leq 1 0^{9}, k \leq 5 \times 1 0^{3}$ 。

结论。

设 $f_{i, j}$ 表示 $i$ 个连通块用了 $j$ 个，枚举当前最小点加一块： $f_{i, j} = \sum_{l = 1}^{m i n (j, d)} f_{i - 1, j - l} l^{l - 2} l (l - 1 j - 1) (n - k)$ 。

又因为只需要知道 $\sum i f_{i, k}$ ，维护 $f_{k}^{'} = \sum f_{i, k}$ ， $g_{k}^{'} = \sum i f_{i, k}$ ，每拼上一个连通块就让 $g_{k}^{'} = g_{k}^{'} + f_{k}^{'}$ 。

AT_diverta2019_f

正着 dp 容易， $O (2^{n} n^{3})$ 。

倒着做，在放一个树边之前必须放一些非树边。枚举当前放了哪些树边，同时维护当前的方案数和位置和 $(c, s)$ 。

加树边必须加在最前，对于当前所有树边，位置向后移 $1$ ，变为 $(c, s + (n u m + 1) c)$ 。

加非树边加在任意位置，对于当前所有树边，有其位置种方式加一，变为 $((n + 1) c, (n + 2) s)$ 。批量加入一堆非树边，形如阶乘。

10.10 Q8713

设 $f_{u, s}$ 表示 AC 自动机节点 $u$ ，已经出现过状态 $s$ 的串，先手的价值，转移是图。

按 s 从大到小分层考虑。如果后继状态 $v$ 能去到上一层，更新 $u$ 。如果 $u$ 的所有后继状态都确定，确定 $u$ 。否则取出当前最大的 $u$ ，如果 $f_{s, u} \geq 0$ ，确定 $u$ ；否则此时剩下的状态都是求和。

Q4888

$65535 = 3 \times 5 \times 17 \times 257$ 。要求 $\sum_{a} \sum_{i} (256)^{i} a_{i}$ 。

对于 $p = 3, 5, 17$ ， $256$ 取模后为 $1$ 。即求 $(\sum a_{i})^{n!}$ ， $n!$ 对 $ϕ (p)$ 取模，只用算 $p$ 次。

对于 $p = 257$ ，即求 $∣ S ∣ = \frac{n}{2}$ ， $(\sum_{S} (\sum_{i \in / S} a_{i} - \sum_{i \in S} a_{i}))^{\frac{n}{2}! \frac{n + 1}{2}!}$ 。当 $n \leq 11$ 时暴力。否则指数模 $ϕ (257) = 0$ ，只需要关注是否存在 $S$ 使得 $\sum a_{i} - 2 \sum_{S \in S} a_{i} = 0$ 。取 $a_{i}$ 最大的 $i$ 作为基准，如果其他的 $\sum a_{i} - max a_{i}$ 太大（ $\geq 2 p$ ），一定能做出 $0$ 。否则 bitset。

Q4811

有 $2^{m a x d_{v}}$ 的做法。对于每个儿子，检查 $0 \sim d_{b}$ 是否出现过。

有 $2^{d_{u}}$ 的做法。枚举 $m e x = 0 \sim d_{u}$ ，记录有多少个值有叶子选了，当前已经选了哪些儿子。

根号分治，对于 $d_{u} > B$ 的 $\frac{n}{B}$ 个，和 $d_{u} \leq B$ 的 $max d_{v} \leq B$ ，再拼起来。

10.12

agc041f

钦定 $i$ 个格子不满足限制， $(- 1)^{i}$ 。

枚举列 $S$ 存在不满足限制格子，钦定 $T$ 中不存在不满足限制格子， $(- 1)^{∣ T ∣ - 1}$ 。

对于每个行连续段，设 $S$ 在这些地方有 $p$ 列， $T$ 有 $q$ 列。要么整行没有不满足限制格子， $2^{l e n - p}$ 。要么选 $i$ 个不满足限制格子， $\sum_{i = 0}^{p - q} (i p - q) (- 1)^{i} = - [p > q]$ 。

建小根笛卡尔树，从儿子处合并 $p$ 和 $[p = q]$ 。再批量计算 $a_{u} - a_{f a}$ 行，每行 $2^{s i z_{u} - i} - [p > q]$ 。

Quartz 4

Explorer

Recent Notes

更新记录

P14170 题解