202408 集训测试笔记

没写的题意思是暑假没做出来，没什么时间补了。

Day1A

简要题意： $t$ （ $t \leq 10^{4}$ ）个 $n$ （ $n \leq 300$ ）位字符串，每次操作选中一个字符串相邻的两个字母，将其中一个变为字母表的前一个字母，另一个变为字母表的后一个字母， $a$ 不能向前， $z$ 不能向后，对于每个字符串，它能变化出多少种不同的字符串？

解析：假设 $a$ 的 “ASCII 码”是 $1$ ，发现每次操作后，那个字符串的 ASCII 码总和不变，设一开始字符串的总和为 $S$ ，那么问题变成求：

a_{1} + a_{2} + \dots + a_{n} = S, 1 \leq a_{i} \leq 26

的方案数。

DP 求即可，设 $f_{i, j}$ 表示处理到第 $i$ 位，前面总 ASCII 码为 $j$ 的方案数，答案即为 $f_{n, min (c n t d, c n t u)}$ ， $c n t d$ 表示每一位向前调的总和， $c n t u$ 表示每一位向后调的总和。

时间复杂度 $O (26^{2} n^{2} + T n)$ 。

Day1B CF82D Two out of Three

解析：发现在第 $i$ 轮中，总是在 $2 \times i$ ， $2 \times i + 1$ 和上一轮中剩下的 $j$ 里选 $2$ 个，因此，设 $f_{i, j}$ 表示第 $i$ 轮剩下 $j$ 的最小代价。

f_{i, j} = f_{i - 1, j} + max (a_{2 \times i}, a_{2 \times i + 1})

f_{i, 2 \times i} = f_{i - 1, j} + max (a_{2 \times i + 1}, a_{j})

f_{i, 2 \times i + 1} = f_{i - 1, j} + max (a_{2 \times i}, a_{j})

时间复杂度 $O (n^{2})$ 。

Day1C

简要题意：求 ${1, 2, \dots, n \leq 10^{5}}$ 两两之间商不为 $2$ 或 $3$ 的子集个数。

解析：如果考虑选择 $p$ ，那么在得到这样一张表格图：

1	2	3	4	5
$p$	$3 p$	$9 p$	$27 p$	$\dots$
$2 p$	$6 p$	$18 p$	$54 p$	$\dots$
$4 p$	$12 p$	$36 p$	$108 p$	$\dots$
$\dots$

左右相邻的不能选，上下相邻的不能选。

即使 $p = 1$ ，最多 $11$ 列 $17$ 行。

故用状压 DP $f_{i, s}$ 表示第 $i$ 行选中的数的集合是 $s$ 的方案数。

对于每个没有出现过的 $p$ 都要做一次 DP，每次求出的答案相乘。

时间复杂度 $O (p \log_{2} (n) \times 2^{\log_{3} (n)})$ ， $p$ 为 $[1, n]$ 间质数的个数。

Day2A

简要题意： $n \leq 100$ 歌瓶子，每个瓶子里最多能放 $b_{i} \leq 100$ 个物品，每个瓶子目前里有 $a_{i}$ 个物品，将所有物品移动到个数最少的瓶子里，瓶子个数最少是多少？在此条件下，最少要移动多少个物品？

解析：设 $s u m$ 表示物品总量， $f_{i}$ 表示装 $i$ 个物品需要多少个瓶子， $g_{i}$ 表示在 $f_{i}$ 的条件下，选中的瓶子里最多能有多少个物品。

f_{j} = min {f_{j - b_{i}} + 1}

g_{j} = max_{f_{j} = f_{j - b_{i}} + 1} {(g_{j - b_{i}} + a_{i})}

答案在 $i \in [s u m, 100^{2}]$ 中找到最小的 $f_{i}$ ，并记录当 $f_{i}$ 最小时 $g_{i}$ 的最大值 $m x$ ，用 $s u m - m x$ 就是移动次数。

时间复杂度 $O (100 n^{2})$

Day2B

简要题意：给出 $n \leq 500$ 个字符出现的频率 $a_{i} \leq 10^{9}$ ，构造一棵保序的 $k \leq 60$ 进制哈夫曼树，使得每个字符的编码与频率的乘积之和最小，输出这个最小值。

解析：设 $f_{l, r, k}$ 表示区间 $[l, r]$ 划分为 $k$ 棵子树的最优策略， $g_{l, r}$ 表示区间 $[l, r]$ 的最优策略。

每划分一次，层数就会增加，所以加上 $\sum_{i = l}^{r} a_{i}$ ，可以用前缀和 $q$ 维护。为了方便实现，这一部分可以在最后统计 $g$ 的时候再加。

f_{l, r, i} = {min}_{m i d = l}^{r - 1} {f_{l, m i d, i - 1} + g_{m i d + 1, r}}

g_{l, r} = {min}_{i = 2}^{k} {f_{l, r, i}} + q_{r} - q_{l - 1}

f_{l, r, 1} = g_{l, r}

答案是 $g_{1, n}$ 。

时间复杂度 $O (n^{3} k)$ ，数据太水可过。

Day2C

简要题意：一个 $n \times m$ （ $n, m \leq 200$ ）只含 $.$ 或 $#$ 的矩阵，进行以下流程求它的分数：若这个矩阵只有一种字符，分数为0。否则，则考虑所有的沿水平或者竖直方向的直线，将矩阵分成两个不为空的子矩阵，设两个子矩阵的分数分别为 $a$ 和 $b$ ，则原矩阵的分数为所有划分方法中 $max (a, b) + 1$ 的最小值。

解析：直接枚举矩阵的上下左右界肯定爆炸，但是发现每一个矩阵最终的分数都很小，不会超过 $\log (n) + \log (m)$ ，并且对于上下左边界相同的矩阵，分数随着右边界的增大而增大。

因此，设 $f (u, d, l, a n s)$ 表示矩阵左上角为 $(u, l)$ ，下界为 $d$ ，分数为 $a n s$ 时，右界的最大值。

同时，对 $#$ 求一个二维前缀和统计个数。

先预处理出 $f (u, d, l, 0)$ 的情况。

横着分割：

f (u, d, l, a n s) = {max}_{i = u}^{d - 1} {min (f (u, i, l, a n s - 1), f (i + 1, d, l, a n s - 1))}

竖着分割：

f (u, d, l, a n s) = f (u, d, f (u, d, l, a n s - 1) + 1, a n s - 1)

状态数 $O (n^{3} \log n)$ ，转移 $O (n)$ ，时间复杂度 $O (n^{4} \log n)$ ，优化：

对于上，左，右界相同的矩阵，最优分割点随着下界的增大而增大，所以单调性优化，不再从 $u$ 开始枚举 $d$ ，转移的 $O (n)$ 就没了。

此外 $a n s$ 一维可以滚动数组。

答案是当出现 $f (1, n, 1, a n s) = m$ 时， $a n s$ 的最小值。

时间复杂度 $O (n^{3} \log n)$ 。

Day2D

简要题意：有 $n$ 个物品，每个物品位于位置 $a_{i}$ ， $m$ 个黑洞，每个黑洞位于位置 $b_{i}$ 。每次操作让所有物品向左（位置 $- 1$ ）或向右（ $+ 1$ ），物品碰到黑洞就会消失（黑洞不会消失），直到所有物品消失。设第 $i$ 个物品因为编号为 $p_{i}$ 的黑洞而消失，求不同的 $p$ 序列的个数。（ $n, m \leq 10^{5}$ ， $a_{i}, b_{i} \leq 10^{9}$ ）

解析：设 $l_{i}$ 表示物品 $i$ 去到左边的黑洞有多远， $r_{i}$ 表示物品 $i$ 去到右边的黑洞有多远， $A$ 表示所有物品向左移动过的最远距离， $B$ 表示向右移动过最远的距离。

当 $l_{i} \leq A$ ，物品被左边的黑洞吸走， $r_{i} \leq B$ ，物品被右边的黑洞吸走。

把 $(l_{i}, r_{i})$ 映射到平面直角坐标系上，每次操作都会让 $A \leftarrow A + 1$ 或 $B \leftarrow B + 1$ ，因此每次操作后 $(A, B)$ 组成的折线是一根向右上角走的折线。 $l_{i} \leq A$ 即为位于折线左侧， $r_{i} \leq B$ 即为位于折线右侧。

因此，问题变成求有多少条向右上方走的折线划分 $(l_{i}, r_{i})$ 组成的点集。

可以用二位偏序，设 $f_{i}$ 表示以 $(l_{i}, r_{i})$ 为折线的右上角，折线的方案数。

f_{i} = \sum_{l_{i} > l_{j} \land r_{i} > r_{j}} f_{j}

需要离散化优化。

时间复杂度 $O (n \log n)$ 。

Day2E CF372C Watching Fireworks is Fun

解析：先把 $b_{i}$ 全部加起来，减去 $| a_{i} - x |$ 的最小值即可。

设 $f_{i, j}$ 表示第 $i$ 场活动人在 $j$ 的“ $| a_{i} - x |$ ”的最小值。

f_{1, j} = | a_{1} - j |

f_{i, j} = min_{k \in [1, n] \land | j - k | \leq Δ t} {f_{k}} + | a_{i} - j |

单调队列和滚动数组优化。

答案是 $\sum b_{i} - min {f_{m, i}}$ 。

时间复杂度 $O (n m)$ 。

Day3A CF220B Little Elephant and Array

解析：莫队板，卡常能过。

时间复杂度 $O (n \sqrt{n})$ 。

Day3C CF575I Robots protection

解析：先把四个方向的分开处理，后面都旋转成方向一的形状。

对于一个三角形，限制的是：

$x^{'} \in [x, n]$ ， $y^{'} \in [y, n]$ ， $x^{'} + y^{'} \in [x + y, x + y + l e n]$ 。

画个图会发现，满足 $y^{'} \in [y, n]$ 和 $x^{'} + y^{'} \in [x + y, x + y + l e n]$ 的部分减去满足 $x^{'} \in [1, x - 1]$ 和 $x^{'} + y^{'} \in [x + y, x + y + l e n]$ 就是要求的部分，开两个二维树状数组分别维护即可。

Day3D P6847 [CEOI2019] Magic Tree / CF1193B Magic Tree

解析：设 $f_{u, i}$ 表示以 $u$ 为根的子树，其操作全部在时间 $i$ 及以前完成。

不获得 $u$ 的果汁： $f_{u, i} = \sum f_{v, i}$ 。
获得 $u$ 的果汁： $f_{u, i} = w_{u} + \sum_{i \geq d_{u}} f_{v, d_{u}}$

两者取 $max$ 得到 $f_{u, i}$ ，时间复杂度 $O (n k)$ ，线段树合并优化。

Day4A

简要题意：一个长度为 $n \leq 5 \times 10^{4}$ 的只含 $a \sim z$ 的字符串，进行 $q \leq 5 \times 10^{4}$ 次操作，每次操作将 $[l, r]$ 升序或降序排序，求最终的序列：

解析：开 $26$ 个线段树维护 $a \sim z$ 连续段的左右位置，每次排序可以很快的求出这一段里每个字母有多少个，然后根据排序就可以算出每个连续段对应的左边界和右边界。

但是暴力做法也能卡过，可以运用计数排序（即将每个数放到数轴上在顺次取，适合值域小的情况）卡到 $O (n q)$ ，然后三秒时限直接玄学优化。

Day4B

简要题意：有 $n$ 个数 $a_{i}$ ，有 $m$ 次操作，操作一单点修改 $a$ 数组，操作二求随机选一段长度为 $k$ 的连续区间，不同数字的个数的期望值。 $n, m, a_{i} \leq 10^{5}$ 。

解析：计算出所有长度为 $k$ 的区间的种类个数后除以长度为 $k$ 的子区间的个数即可。

对于每个数字单独考虑。当选中的区间位于两个数字中间的空白段时，则这段区间无法被这个数字贡献（不同数字的个数），若两个 $1$ 中间长度为 $3$ ，则有 $3$ 个长度为 $1$ 的区间， $2$ 个长度为 $2$ 的区间， $1$ 个长度为 $3$ 的区间无法被数字 $1$ 贡献。

所以考虑维护每种数字中间的空白段，若从 $x$ 改成 $y$ ，就是 $x$ 左右的空白段合并， $y$ 分裂 $y$ 所处的空白段。

观察 若两个 1 中间长度为 3，则有 $3$ 个长度为 $1$ 的区间，$2$ 个长度为 $2$ 的区间，$1$ 个长度为 $3$ 的区间，发现区间的长度和不能被贡献的区间的个数，可以表示为一次函数 $y = - x + m$ ，树状数组维护即可。

Day4C

简要题意：有一个有无限个房间的酒店，从 $0$ 开始编号，一开始里面住满了 $0$ 号队伍。

如果新进来一个有 $k$ 个人的队伍，则先前房间 $i$ 里的人移动到 $i + k$ ，新队伍住进 $[0, k - 1]$ ；如果新进来一个有无限个人的队伍，则先前房间 $i$ 里的人移动到 $2 i$ ，新来的所有人住进每个 $2 i + 1$ 。

询问 $q \leq 3 \times 10^{5}$ 次队伍 $k$ 编号最小的房间，或编号为 $k$ 的房间里住的几号队伍。

解析：观察到对于 $i$ 号队，它们 $x$ 个队员的房间分布一定满足 $y = k_{i} x + b_{i}$ ，第一种询问直接用【模板】线段树 2 的方法就可以维护.

第二种询问，考虑哪个团队最终会选中这个房间，直接时光倒流：

新增一个房间，等待被一个队伍选取。
若出现一个有限人数为 $k$ 的队伍，则编号 $< k$ 的房间全部被这个队伍选取。
若出现一个无限人数的队伍，则编号为偶数的房间全部被这个队伍选取。

用一个 set 维护即可。

Day5A CF1795D Paint the Tree

解析：先让染红和染蓝走到两点的中点会合，然后以最短路径将整棵树遍历一遍即可。

Day6A

简要题意：给定一棵 $n \leq 10^{6}$ 个点、带边权的树，计算以哪个点为根时，根到其他点的距离和最大。距离定义为两点之间路径上边权最小值。

解析：维护 $max / min$ 问题很难直接维护，因此考虑时光倒流，每个点都变成孤立的点，依次加入边，这个操作可以用并查集维护。

然后考虑统计答案，设 $m a x x_{i}$ 表示以 $i$ 为根时，根到其他点的最大距离。

$f x$ 和 $f y$ 进行并查集合并时（ $f x$ 的 $s i z$ 大于 $f y$ ）， $m a x x_{f x} \leftarrow max (m a x x_{f x} + w \times s i z_{f y}, m a x x_{f y} + w \times s i z_{f x})$ 。

Day6B

简要题意：有一棵 $n \leq 3000$ 个节点的树，每个节点有一个权值。求相同权值的点数超过连通块点数一半的连通块的个数。

解析：分开每种权值考虑，将与当前考虑权值相同的点权设为 $1$ ，与当前考虑权值不相同的点权设为 $- 1$ ，若存在一个连通块权值和大于零，则说明这个连通块是一个满足题意的连通块。

设 $f_{u, i}$ 表示以 $u$ 为根的子树中，连通块权值和等于 $i$ 的方案数。

$f_{u, i + j} = f_{v, i} f_{v, j}$

如果以 $u$ 为根的节点颜色是 $i$ 的有 $c_{i}$ 个，而存在 $f_{u, j}$ ，其中 $j \leq - c_{i}$ ，这一部分的子树肯定是没用的，直接扔掉，时间复杂度优化到 $O (n \sum c_{i}) = O (n^{2})$ 。

Day6C CF1111E Tree

解析：考虑深度从浅往深放。

设 $f_{i, j}$ 表示考虑前 $i$ 个节点已经划分成 $j$ 组的方案数，节点 $i$ 它的祖父有 $c_{i}$ 个。 $i$ 不能和它任何一个祖先划分为一组，所以有两种方案：

$i$ 自己开一组： $f_{i, j} \leftarrow f_{i - 1, j - 1}$ 。
$i$ 和不是自己祖先的划为一组： $f_{i, j} \leftarrow f_{i - 1, j} \times (j - c_{i})$ 。

维护它的祖先的个数，用树链剖分即可。

Day6D

简要题意：两棵树共用若干个节点，A 可以在红树上移动，B 可以在蓝树上移动。输出 B 能捉到 A 的最少步数（双方都绝顶聪明），如果 B 捉不到 A，输出 $- 1$ 。

解析：

如果存在一条红边，它两端的端点在蓝树上的距离 $\geq 3$ ，那只要 A 到达这条边的两端，它就可以无限瞬移。
如果某个节点，A 过去比 B 过去要慢，那 A 肯定不往那边走。

将下面那种点打上标记，如果不经过下面那种点能达到上面那种点，那么就输出 $- 1$ ，否则，走到能走到的在蓝树上深度最大的点。

~~这不纯纯 dfs 模拟题了。~~

Day7A CF437C The Child and Toy

解析：由于一个点删 $x$ 条边就得付出 $x$ 倍的代价，所以每条边的结果相互独立，互不影响，每条边直接删它两端较小的那边就可以了。

Day7B

简要题意：Alice 和 Bob 在一个有向图（点数，边数 $\leq 10^{5}$ ）上轮流移动棋子，Alice 先手，分数是经过的所有节点的最大值。Alice 想最大化得分，Bob 想最小化得分。从每个节点出发，Alice 的得分是多少？

解析：设状态 $(i, A / B)$ 表示到达 $i$ 号节点，且下一步是 Alice / Bob 移动。

根据得分的机制，经过 $max$ 后的路径如何并不会影响答案，所以可以将 $max$ 从大到小考虑，每一轮统计出所有可以到达 $max$ 的状态。这样有效的解决了环的问题。

首先将那些已知的可以到达 $> max$ 的状态全部丢进一个集合 $S$ 里面（表示后面不可取）。

若从 $(i, x)$ 能够到达 $max$ ，则说明有一种转移： $(i, x) \to (j, \neg x) \to (k, x) \to \dots \to (max, A / B)$ ，这个序列应满足：

所有状态均不处于集合 $S$ 中，不然可以走到 $> max$ 的数。
对于每一个状态 $(u, A)$ ， $u$ 的任意一条出边的节点 $v$ 的状态 $(v, B)$ 必须不处于集合 $S$ 中，否则 Alice 可以沿着 $(v, B)$ 前往更大的节点。
对于每一个状态 $(u, B)$ ， $u$ 的任意一条出边的节点 $v$ 的状态 $(v, A)$ 必须处于集合 $S$ 中，否则 Bob 可以沿着 $(v, A)$ 使其前往更小的节点。

所以代码的实现就可以沿着上面的思路：拿出不在 $S$ 中的 $(max, A / B)$ 作为起点，沿着它的反边行走，看一下它的前继状态是否满足上面三条要求，沿着这个状态继续向前找。写一个像拓扑排序一样的东西即可。

Day8A

简要题意： $n$ 个点 $m$ 条边的有向图，每个点权值是 $a \sim z$ ，一条路径的权值是该路径中点权出现最多次的权值，出现的次数。求最大路径权值。

解析：Kosaraju 缩点跑拓扑排序 DP 即可。

Day8B

简要题意：一个机器人在一个有向图（点数，边数 $\leq 2 \times 10^{5}$ ）上走，走到自己走过的路径或者无路可走就自毁，遇到交叉路口可以花费 $1$ 代价让它按指定路线行驶，否则它将随机移动。求每个点到达 $t$ 的最小代价，无解输出 $- 1$ 。

解析：考虑到可以从终点反推走到这个点所需要的代价。设 $f_{i}$ 表示节点 $i$ 走到 $t$ 的最小代价。用 $u$ 表示每条边的起点， $v$ 表示每条边的反点。随机走就按最坏情况走，显然有：

f_{u} = min (max_{u \to v} f_{v}, min_{u \to v} f_{v} + 1)

令 $f_{t} = 0$ ，沿着正图反着走，采用 01BFS + 拓扑排序 的方法。

补充：01 BFS 是一种使用双端队列处理边权只有 $0$ 和 $1$ 的图的最短路的算法，时间复杂度为 $O (m)$ ，其贪心思路为：不断取出队首的点处理，若遇到边权为 $0$ 的边，这种边要多走，放到队头，否则放到队尾。可以证明双端队列中的元素从队首到队尾单调递增。

给每个点统计入度，当是 $max_{u \to v} f_{v}$ 的情况且入度为 $0$ 时，放到队头；另一种情况需要立马转移，不管入度直接放到队尾。

后记：这样一看我也就补了一半都没有的题，菜！

202408 集训测试 笔记 ​

Day1A ​

Day1B CF82D Two out of Three ​

Day1C ​

Day2A ​

Day2B ​

Day2C ​

Day2D ​

Day2E CF372C Watching Fireworks is Fun ​

Day3A CF220B Little Elephant and Array ​

Day3C CF575I Robots protection ​

Day3D P6847 [CEOI2019] Magic Tree / CF1193B Magic Tree ​

Day4A ​

Day4B ​

Day4C ​

Day5A CF1795D Paint the Tree ​

Day6A ​

Day6B ​

Day6C CF1111E Tree ​

Day6D ​

Day7A CF437C The Child and Toy ​

Day7B ​

Day8A ​

Day8B ​