前言

本文章只记录了模拟赛的题目，其实每日还做了其他的题，不在此做记录。

* 表示未完成的题目，^ 表示待补博客的题。

---

09/01

经过讨论后得到的：

$9$ 月半停（下午和晚上），$10,11$ 月全停。

T1

题面

给定一个序列 $a$，令 $S$ 为 $a$ 序列的一个子集，称其合法，当且仅当存在一个 $S$ 的子集 $T$，使得 $|T|=|S|-k$，且 $\sum _{i\in T}{a}_i\ge m$。

求对于 $\mathrm{\forall }k\in [0,n]$ 时合法集合 $S$ 的数量。

$n,m,a_i\le 3000$

Solution

定义 $f_{i,j}$ 为前 $i$ 个数组成集合 $S$，$S$ 中权值和为 $j$ 的子集数量，转移就是正常的背包；

反过来想，$|T|=|S|-k$，也就是 $|S|=|T|+k$，此时 $k\in [0,n-i]$，乘上对应的组合数并记录贡献，即：

$$g_k=g_k+(f_{i,m}-f_{i-1,m})\times (\genfrac{}{}{0ex}{}{n-i}{k})$$

复杂度为 $O(n^2)$。

注意：这里权值和 $\ge m$ 的方案也都计入 $f_{i,m}$ 中。

Reflect

做的时候一直往如何对集合 $|S|$ 直接进行背包去想，但必须要顾及集合大小，取值和，转移状态达到三维；思路的突破口在于想到从 $|T|$ 入手，用组合数解决集合大小这一维度。

---

T2

题意

随机给出一张 $n$ 个点 $m$ 条边的无向简单联通图，点 $1$ 到 $n-1$ 初始值为 $1$，给定一个长度为 $n-1$ 的排列 $p$，第 $i$ 轮，从节点 $p_i$ 出发到 $n$，求路径点权和最小值。

$n\le 7.5\times {10}^4,n-1\le m\le 2n$

时限：$4s$

Solution

将 $1$ 到 $n$ 所有点的入边权值设置为 $1$，，从 $n$ 开始跑反图的最短路 $di{s}_i$，每次改变 $p_i$ 的入边权值，再从 $p_i$ 开始在反图上搜索。

由于每个点松弛过后，距离会减少 $1$，因为随机一棵树，直径期望值是 $O(\sqrt{n})$ 级别的，所以复杂度为 $O(m\sqrt{m})$。

我们发现一个问题，如果每次都用 dijkstra 松弛，时间复杂度带 $\log$。

• Tip ： 当边权都为 $0/1$ 时，可以运用 01bfs 将复杂度优化成线性。

---

T3 P10681 [COTS 2024] 奇偶矩阵 Tablica

题意

考虑只包含 $0$ 和 $1$ 的 $n\times m$ 矩形，称满足以下条件的矩阵是好的：

• $\mathrm{\forall }1\le i\le N$，${\displaystyle \sum _{j=1}^M{A}_{i,j}\in \{1,2\}}$；
• $\mathrm{\forall }1\le j\le M$，${\displaystyle \sum _{i=1}^N{A}_{i,j}\in \{1,2\}}$。

求好的矩阵的数量。

$1\le N,M\le 3000$

Solution

考虑行向列连边，相当于左边有 $n$ 个点，右边有 $m$ 个点，要求无重边，且每个点的度数为 $[1,2]$。

假设度数为 $2$ 的球有 $j$ 个，那么相当于把 $n+j$ 个球放入 $m$ 个盒子中，设 $f_{i,j}$ 表示将 $i$ 个球放入 $j$ 个盒子中的方案数，有：

$$f_{i,j}=f_{i-1,j-1}\times (\genfrac{}{}{0ex}{}{n}{1})+f_{i-2,j-1}\times (\genfrac{}{}{0ex}{}{n}{2})$$

因为左边的点本质相同，所以贡献为 $\frac{f_{n+j,m}}{2^j}$。

发现这样计算可能会出现重边，考虑枚举重边的个数 $i$，则答案为：

$$\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})(\genfrac{}{}{0ex}{}{m}{i})i!(-1{)}^i\sum _{j=0}^{n-i}\frac{1}{2^{i+j}}(\genfrac{}{}{0ex}{}{n-i}{j})f_{n-i+j,m-i}$$

复杂度为 $O(n^2)$，注意勤取模，特别是负数取模的处理。

---

T4 P11945 [KTSC 2025] 军事基地 / safezone

题意

给定 $n$ 个矩形，定义两个矩形连通为两个矩形有交点，求出每个矩形所在连通分量。

Solution

考虑对 $x$ 轴进行扫描线，需要支持加入、删除线段以及合并相交线段的编号，合并操作可以用并查集维护。

当往线段树上加入一条线段时，线段会被拆成若干个区间，与这些区间的祖先和儿子上拆出的其他线段的编号合并。

对于祖先的合并是简单的，在拆分线段的过程中暴力合并即可；

对于儿子的合并考虑使用懒标记，在删除线段时进行合并，具体的，在线段树的每个节点上建立队列维护懒标记，表示子树内加入时间在 $x$ 之前的线段会和后面加入的某条线段的编号产生合并，注意懒标记不需要下传；

定义一个矩阵的加入时间为其左线段加入线段树的时间（或者左线段的横坐标）；

在删除线段的时候，对经过的祖先上的懒标记队列所记录的线段编号中，加入时间比当前删除线段所在矩形的加入时间更晚的线段进行合并，并将这些线段全部弹出队列，只需要保留加入时间最晚的线段信息以便后续合并即可。

太干涩了，举个栗子，如下图中的若干个矩形，其中蓝色矩形的线段是最小的，区间值域为 $[5,6]$，在删除其右线段的过程中，必然会经过祖先区间 $[1,8],[5,8]$，当到区间 $[5,8]$ 时候，这个区间的队列懒标记中存储了灰、红、黄、绿、紫色的矩形所在连通分量的编号。

灰色矩阵的加入时间比蓝色矩阵的加入时间更早，不需要合并；而后面的四个矩阵则需要和蓝色矩阵的编号合并，并弹出队列，但还要将最晚加入的矩阵（紫色）再次加入队列，用于后面的合并操作。

时间复杂度为 $O(n\log n)$；空间复杂度为 $O(n\log n)$，瓶颈在懒标记队列，最多会加入 $n\log n$ 个点。

---

09/04

T1 P13532 [OOI 2023] Buying gifts / 购买礼物

题意

给定 $n$ 对数对 $(a_i,b_i)$，从每个数对选出其中的一个数，最后使得取出的 $a_i$ 与 $b_i$ 的最大值之差最小。

$0\le n\le 2\times {10}^5$

Solution

将 $n$ 对数对按 $a$ 从小到大排序，枚举 $a_i$ 为选出的 $a$ 中最大的数，那么 $j>i$ 的 $b_j$ 都必须选，这里很容易想到用最大后缀来维护；

那么对于 $j<i$ 的情况，可以选 $a_j$ 也可以选 $b_j$，选 $a_j$ 对答案没有影响，考虑选 $b_j$ 的情况，为了使差值最小，那就是找到最后一个 $\ge a_i$ 的 $b_k$，或者第一个 $\ge a_i$ 的 $b_k$，需要满足 $b_k$ 大于后缀最大值，可以直接用 set 维护，也可以用权值线段树。

Reflect

可以用其他简单的数据结构或者方法代替线段树的时候，尽量写得简单一些。

---

T2 P6583 回首过去

题意

给定正整数 $n$，求出有序整数对 $(x,y)$ 的个数，满足 $1\le x,y\le n$ 且 $\frac{x}{y}$ 可以表示为十进制有限小数。

$1\le n\le {10}^{12}$

Solution

先来想一下一个可以表示为十进制有限小数的分数，必然可以通过不断地乘以 $10$ 变成一个整数，分析一下可以得到其本质就在于分数进行约分后分母依旧存在质因子 $2,5$。

那么我们把 $\frac{x}{y}$ 分解成 $\frac{bc}{ac}$，其中 $a$ 只含有 $2,5$ 两种因子，$b$ 不含有 $2,5$ 两种因子，$c$ 为任意的整数（相当于约分）。

依次在 $[1,n]$ 内枚举 $a$，这里也可以对 $a$ 的数进行预处理，再在合法范围 $[1,\lfloor \frac{n}{a}\rfloor ]$ 内枚举 $c$，然后合法的 $b$ 个数是 $\lfloor \frac{n}{c}\rfloor$，这样做的时间复杂度为 $O(n^2)$；

尝试通过转换枚举顺序来达到优化的目的，先枚举 $c$，$b$ 的取值范围依旧是 $[1,\lfloor \frac{n}{c}\rfloor ]$，而 $a$ 的取值就变成了 $[1,\lfloor \frac{n}{c}\rfloor ]$ 中只含有 $2,5$ 两种因子的数，也就是对于每个 $c$，记合法的 $a$ 的个数为 $d$，那么贡献就为 $d\times \frac{n}{c}$，时间复杂度为 $O(n)$；

记 $f(x)$ 为在 $[1,x]$ 中只含有 $2,5$ 两种因子的数的个数，那么上文的式子等价于：

$$f(\lfloor \frac{n}{c}\rfloor )\times \lfloor \frac{n}{c}\rfloor$$

这是一个经典的整除分块问题，但是 $c$ 的取值是不含有 $2,5$ 两种因子的数，可以用容斥思想，对于一段区间 $[l,r]$，设 $g(x)$ 为区间 $[l,r]$ 中 $x$ 的倍数的个数，那么合法的个数为 $cnt=g(1)-g(2)-g(5)+g(10)$，区间 $[l,r]$ 对答案的贡献为 $cnt\times f(\lfloor \frac{n}{c}\rfloor )\times \lfloor \frac{n}{c}\rfloor$，时间复杂度优化到 $O(\sqrt{n})$。

Reflect

连一些最基本的数学概念性问题都没搞懂？？？

---

T3 P10207 [JOI 2024 Final] 马拉松比赛 2 / Marathon Race 2

题意

在一条长为 $L$ 的路上放了 $N$ 个球，所在位置分别为 $X_i$，取一个球的时间为 $1$ 秒，拿着 $x$ 个球移动一个单位需要 $x+1$ 秒，且途中不能把球放下。

$Q$ 次询问 $(S_j,G_j,T_j)$，求从 $S_j$ 出发，终点为 $G_j$，在 $T_j$ 秒内是否能取完所有的球。

$1\le N,L,Q\le 5\times {10}^5$

$0\le X_i,S_j,G_j\le L,1\le T_j\le 5\times {10}^5$

Solution

每个球先按照顺序排序并离散化后，有球的位置的个数为 $n$，分别为 $a_i$，利用前缀和 $cn{t}_i$ 为前 $i$ 个位置的总球数；

很明显的一个结论，取的第一个球必然是在 $a_1$ 或者 $a_n$ 的，进而想到用 $f_{l,r,0/1,0/1}$ 表示从 $1/n$ 出发，已经取了 $[1,l)$ 和 $(r,n]$ 位置上的球，当前位于 $l/r$ 位置时的最短时间，令 $x$ 为当前状态移动一个单位所需要的时间 $cn{t}_{a_{l-1}}+cn{t}_n-cn{t}_{a_r}+1$，则有转移为：

• 移动到 $l$ 时，$f_{l,r,k,0}=min\{f_{l,r,k,0}+x\times (a_l-a_{l-1}),f_{l,r,k,1}+x\times (a_{r+1}-a_l)\}$

• 移动到 $r$ 时，$f_{l,r,k,1}=min\{f_{l,r,k,0}+x\times (a_r-a_{l-1}),f_{l,r,k,1}+x\times (a_{r+1}-a_r)\}$

（这里的 $k$ 为 $0/1$ 的时候，表示从 $1/n$ 出发）

观察一下题意，询问的时间限制 $T_j$ 的最大值为 $5\times {10}^5$，而移动一个单位的时间 $x$ 随着拿着球数量的增多而增多，最后的时间至少为 $\frac{n(n+1)}{2}$，因此 $n$ 只有 $O(\sqrt{T})$ 级别，时间复杂度为 $O(n^2)$ 完全可以过掉。

最后用二分找到离 $G_j$ 最近的点 $p$，取 $f_{p,p,0/1,0/1}$ 再加上从 $S_j$ 到 $1/n$ 和 $p$ 到 $G_j$ 的时间即可，注意还要加上取所有球的时间 $cn{t}_n$。

Reflect

一开始想把 $n$ 个球按位置以 $S_j,G_j$ 分为三部分进行贪心，$[S_j,G_j]$ 必然是最后取最优，虽然这个贪心可能是错的；

后面就应该要想到第一个取的球要么从最左边或者最右边的球开始，再考虑用这个写dp状态。

还要多关注数据之间的关系，考虑是否可以缩小数据，弱化题目。

---

T4 P10208 [JOI 2024 Final] 礼物交换 / Gift Exchange

题意

有 $n$ 个人，第 $i$ 个人会送出价值为 $a_i$ 的礼物，且要求收到的礼物价值不低于 $b_i$，保证 $b_i<a_i$。

$q$ 次询问 $(l_j,r_j)$，问区间 $[l_j,r_j]$ 内的人是否能互送礼物。

$2\le n\le 5\times {10}^5,1\le b_i<a_i\le 2n$

$1\le q\le 2\times {10}^5,1\le l_j<r_j\le n$

Solution

由于 $b_i<a_i$，我们不妨将每个人表示成 $[b_i,a_i]$，也意味着对于 $(i,j)$，只有其区间有交，两人才能互送礼物，且称 $(i,j)$ 连通。

考虑询问区间 $[l_j,r_j]$，所有 $i\in [l_j,r_j]$ 的区间形成了若干个连通分块；

把每一个连通分块单独拿出来分析，并按 $a$ 从小到大排序，当连通分块的大小 $\ge 2$ 时，其中最后一个人（$a$ 最大）可以把礼物送给连通分块里任意一个人，不妨直接送给第一个人； 根据上述连通的性质，从第一个人到倒数第二个人都可以把礼物送给后面一个人，相当于送礼物和收礼物的过程形成了一个闭环，这样连通分块里的人都能够互送礼物。

那么反过来想，如果要不能够互送礼物，就只能是单独一个人的连通分块，题目转化成快速求 $[l_j,r_j]$ 内是否存在 $[b_i,a_i]$ 与其他区间没有交集，不妨设 $L_i,R_i$ 分别表示 $i$ 左边/右边第一个与其有交集的人的编号，如果 $\text{⧸}\mathrm{\exists }{L}_x<l_j\le x\le r_j<R_x$，那么区间 $[l_j,r_j]$ 内的人可以互送礼物；$L_i,R_i$ 可以先对 $a$ 排序，再用值域线段树维护。

最后想如何判断 $\text{⧸}\mathrm{\exists }{L}_x<l_j\le x\le r_j<R_x$，考虑使用扫描线，支持区间加减和单点查询：

当遇到 $l_j$ 时，判断当前的线段树里是否存在 $x\le r_j\le R_x-1$，那也就是查询 $r_j$ 上是否为 $0$，所以在 $L_x$ 时插入区间 $[x,R_x-1]$（区间加 $1$），在 $x$ 时删除。

注意：扫描到位置 $x$，操作顺序为：先查询再插入和删除。

复杂度为 $O(n\log n)$ 的。

Reflect

遇到 $b_i<a_i$ 这种性质的东西，尝试用区间来表示；区间问题时有连通的性质不妨拆出来单独讨论；对于类似于上面最后的判定式可以往扫描线想。

---

09/06

T1 CF1497D Genius

题意

给定 $n$ 个问题，第 $i$ 问题有 $a_i=2^i,b_i,c_i$。

解决 $i$ 问题后解决 $j$ 问题需要满足 $x<|a_i-a_j|$ 且 $b_i\ne b_j$；

解决完问题后 $x=|a_i-a_j|$，获得 $|c_i-c_j|$ 分，$x$ 初始为 $0$，求可获得的最高分数。

$1\le n\le 5\times {10}^3,1\le b_i\le n,1\le c_i\le {10}^9$

Solution

$f_i$ 表示以问题 $i$ 为结尾的路径可以获得的最高分数，转移条件为路径的边权 $|a_i-a_j|$ 单调递增，$f_i=f_j+|c_i-c_j|$。

由于 $a_i=2^i$，对于 $i\in [2,n]$，前面 $i-1$ 个数都可以转移过来，因为 $a_i-a_{i-1}=2^i$ 都已经大于前面任意两个数的差了；对于 $L<R<i$，都有 $2^i-2^L>2^i-2^R$，也就是说，如果倒序枚举 $j\to i$ 的转移，顺带处理 $i\to j$ 进行转移，那么上一次（枚举到 $j-1$ 时）的 $x$ 必然都比 $a_i-a_j$ 小，直接暴力转移式子即可，有点妙啊。

最后总结就是一维 $i$ 顺序枚举，另一维 $j$ 倒序枚举，直接双向转移就可以了，时间复杂度为 $O(n^2)$。

---

T2

题意

有 $n$ 个人排成一列，游戏进行多个回合，每一回合淘汰在第 $i\times k+1,i\in \mathbb{N}$ 位置上的人，直到最后只剩下一个人，求问这个人的编号。

$2\le n,k\le {10}^{12}$

Solution

设 $G(n,k)$ 表示最后留下来的人的编号，令 $z=G(n-\lceil \frac{n}{k}\rceil ,k)$，考虑如何能推回去，由于上一轮游戏是每隔 $k-1$ 就淘汰一个人，则有 $G(n,k)=z+\frac{z}{k-1}$，显然的，$G(1,k)=1$。

容易发现在推导过程中不同的 $\lceil \frac{n}{k}\rceil$ 的个数不会超过 $\sqrt{n}$。

证明：若 $k\le \sqrt{n}$，则每次被删掉的人数都 $\ge \sqrt{n}$，至多只会删 $\sqrt{n}$ 次，意味着最多只会出现 $\sqrt{n}$ 次不同的 $n$，$k$ 不变，$\lceil \frac{n}{k}\rceil$ 的个数不会超过 $\sqrt{n}$；若 $k\ge \sqrt{n}$，那显然成立。

根据上面的结论，可以快速算出 $G(n,k)$ 到达 $G(1,k)$ 经过的轮数 $s$，具体的，设 $\lceil \frac{n}{k}\rceil =x$，找到最小的 $l$ 满足 $\lceil \frac{l}{k}\rceil =x$，即 $l=k\times (x-1)+1$，则减了 $\lceil \frac{n-l+1}{x}\rceil$ 次的 $x$ 使得 $n<l$，把其贡献进 $s$ 的次数里。

那么从 $G(1,k)$ 反推回 $G(n,k)$ 也是同理的，$\lceil \frac{z}{k-1}\rceil =x$ 的个数也是 $O(\sqrt{n})$ 级别的，找到最大的 $r$，满足 $\lceil \frac{r}{k-1}\rceil =x$，即 $r=x\times (k-1)$，则加了 $k=\lceil \frac{r-z+1}{x}\rceil$ 次 $x$ 使得 $z>x$；上面算出的总轮数为 $s$ 不断减去 $k$（注意 $k$ 不能超出 $s$），直到 $s$ 为 $0$ 时的 $z$ 就是最后的编号。

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

---

T3 P11340 [COI 2019] TENIS

题意

$n$ 个选手参加比赛，有三种不同的球场，每个人在不同的球场的能力值会不一样，并给定在每种球场上能力值从强到弱的排名编号。

一共会进行 $n-1$ 场比赛，每场比赛可以挑选任意两个人在特定的场地上比赛，在这种场地上能力值强的人会淘汰掉较弱的人。

接下来 $q$ 行，每行表示一个事件：

• 1 x：表示选手 $x$ 能否夺冠；

• 2 p a b：表示交换第 $p$ 个排名表中选手 $a$ 和选手 $b$ 的排名位置。

$1\le n,q\le {10}^5,1\le x,a,b\le n,1\le p\le 3,a\ne b$

Solution

把三个场地的排名看成一个二维数列，显然的，第一列的每个编号的选手都能够夺冠；

接着讨论第二列的选手，由于第一列的选手可以淘汰掉后面所有人，假定第一列的选手编号都不一样，分别为 $a,b,c$，第二列的编号分别为 $i,j,k$：

那么对于选手 $j$ 来说，在场地二能够淘汰掉选手 $a$，按照这个思路，只需要让 $a$ 淘汰掉除去 $j$ 的其他选手，最后让 $j$ 淘汰掉 $a$，那么 $j$ 就可以夺冠了，那么 $i,k$ 是同理的。

反向思考什么情况是不满足上述情况的，那就是当第 $x$ 列的选手在每种场地都无法淘汰掉前面的选手时，第 $x$ 列的选手都不可能夺冠，同样的，第 $x$ 列后面的所有选手都无法夺冠。

由此我们得到了一个结论：找到一个最小的 $x$，使得 $[1,x]$ 列中，每个数出现的次数都为 $3$，那么前 $x$ 列的所有选手都能夺冠。可以用数学归纳法证明吧...

现在考虑如何动态快速寻找 $x$，不妨令 $p_{i,1/2/3}$ 表示选手 $i$ 在三种场地上的排名，$l_i，r_i$ 分别表示排名的最小值/最大值，即 $l_i=min\{p_{i,1},p_{i,2},p_{i,3}\},r_i=max\{p_{i,1},p_{i,2},p_{i,3}\}$，对区间 $[l_i,r_i)$ 的数加 $1$，查询时找到最小的 $x$，且 $x$ 位置上的数为 $0$，用线段树上二分来维护，复杂度为 $O(n\log n)$。

Reflect

看到有淘汰关系类型的题，其实还应该想到连边，本题也可以在连完边后的有向图上缩点后进行分析性质。

---

T4 P12445 [COTS 2025] 数好图 / Promet

题意

给定正整数 $n$，对于 $k\in [0,n]$，求出满足以下条件的简单有向图的数量：

• 图中仅包含 $i\to j$（$1\le i<j\le n$）的边；

• 满足以下条件的点 $u$ 恰好有 $k$ 个：

  • 存在 $1\to u$ 和 $u\to n$ 的路径。

$2\le n\le 2000$

Solution

先讨论 $k=n$ 时，先考虑这样构造图，钦定 $i$ 必须向 $[i+1,n]$ 中的若干个点连边，则有 $2^{n-i}-1$ 种连边方案，保证了每个点都能达到 $n$。

接着构造从 $1$ 能够到达所有点的连边，如果 $1$ 不能到每个点，则至少有一个点的入度为 $0$，考虑容斥。

$f_{i,j}$ 表示钦定倒数第 $i$ 个点（也就是第 $n-i+1$ 个点）的入度为 $0$，从倒数第 $i-1$ 个点到倒数第 $1$ 个点中至少有 $j$ 入度为 $0$ 的点时的连边方案数（注意点 $n$ 的入度始终都不为 $0$）。

$f_{1,0}=1$，讨论第 $i-1$ 个点的入度是否为 $0$，无论如何 $i$ 都需要向后连边，得到转移式子：

$$f_{i,j}=f_{i-1,j}\times (2^{(i-1)-j}-1)+f_{i-1,j-1}\times (2^{(i-1)-j}-1)$$

令 $F_i$ 表示在有 $i$ 个点的图中，$k=i$ 的答案，由于容斥可得：

$$F_i=\sum _{j=0}^{i-1}(-1{)}^j\times f_{i,j}$$

对于更小的 $k$，其实就是往 $F_k$ 中加入 $n-k$ 个不合法的点，考虑点 $i$：

• $1$ 类点： $i$ 满足 $1\to i,i\to n$ 的路径都有，也就是 $F_k$ 中的点；

• $2$ 类点：$i$ 是加入的点，满足 $1\to i,i\nrightarrow n$；

• $3$ 类点：$i$ 是加入的点，满足 $1\nrightarrow i$。

其中 $1,n$ 一定是 $1$ 类点，依据第 $i$ 类点被前面的第 $j$ 类点连边后还是否满足其性质，来考虑这些点之间的连边：

• 后面的 $1$ 类点可以被前面的 $3$ 类点连；

• 后面的 $2$ 类点可以被前面的 $1,2,3$ 类点连，且必须被 $1,2$ 类点连；

• 后面的 $3$ 类点可以被前面的 $3$ 类点连。

观察发现，前面的 $3$ 类点可以向后面的任意点连边，设 $g_{i,j}$ 表示 $[i,n-1]$ 中有 $j$ 个 $3$ 类点的连边方案数；

从后往前枚举，$g_{n,0}=1$（并没有实际意义），有转移：

$$g_{i,j}=g_{i+1,j}+g_{i+1,j-1}\times 2^{n-i}$$

这里注意 $3$ 类点不一定需要向后面的点连边，故为 $2^{n-i}$。

最后考虑 $2$ 类点，其连边与 $1$ 类点的数量有关，设 $h_{i,j}$ 表示考虑完前 $i$ 个 $1$ 类点，在第 $1$ 个 $1$ 类点到第 $i+1$ 个 $1$ 类点之间插入了 $j$ 个 $2$ 类点的连边方案数，$h_{0,0}=1$，有转移：

$$h_{i,j}=h_{i-1,j}+h_{i,j-1}\times (2^{i+j-1}-1)$$

定义 $an{s}_i$ 表示在有 $n$ 个点的图中，$k=i$ 时的连边方案数。

$i,j$ 分别枚举 $1,2$ 类点的个数点 $n$，注意到 $h_{i,j}$ 的定义是指往第 $1$ 个到第 $i+1$ 个 $1$ 类点中插入 $2$ 类点，当钦定第 $i$ 个 $1$ 类为点 $n$ 时，此时连边方案数应为 $h_{i-1,j}$；由于点 $1$ 不属于 $3$ 类点，故 $3$ 类点的贡献为 $g_{2,n-i-j}$，综上有转移：

$$an{s}_i=F_i\times \sum _{j=0}^{n-i}{h}_{i-1,j}\times g_{2,n-i-j}$$

最后对于 $k=0,1$ 的情况特殊处理：

• $k=1$ 时，显然答案为 $0$，因为但凡存在 $1\to x\to n$ 的路径，$1,n$ 都属于答案。

• $k=0$ 时，先构造出任意的图，连边方案数为 $2^{\frac{n(n-1)}{2}}$，再减去 $k\ge 2$ 的合法连边方案数即可。

复杂度为 $O(n^2)$。

---

09/11

T1

题意

int a[MAXN];
int partition(int l, int r){
	int x = a[r],i = l;
	for(int j=l;j<r;j++){
		if(a[j] < x){
			swap(a[i], a[j]);
			++i;
		}
	}
	swap(a[i], a[r]);
	return i;
}
void Qsort(int l, int r, int h){
	if(l<r && h>1){
		int m = partition(l,r);
		Qsort(l,m-1,h-1);
		Qsort(m+1,r,h-1);
	}
}

$T$ 次询问，每次询问给定 $n,k$，问有多少个大小为 $n$ 的排列 $a$ 在调用 Qsort(1,n,k) 能变成有序。

$T\le 500,1\le n,k\le 300$

Solution

先分析清楚 Qsort 的作用，观察可得其实就是将 $a_r$ 排到有序的位置，左边都是 $<a_r$ 的数，右边都是 $>a_r$ 的数，且左右两边的数之间都是按照原序列的位置排序；再进而递归处理左右两边的序列，$k$ 限制了递归的层数。

考虑预处理答案，$f_{i,j}$ 大小为 $i$，递归 $j$ 层可以变成有序的排列个数。

枚举当前层 $a_r$ 的值 $l$，那么就是左右两个子问题的方案数做乘法原理；注意递归进入子问题前该层还需要对 $l$ 排序，相当于左右按顺序互相交叉，可以用插板法：

$$f_{i,j}=\sum _{l=1}^i{f}_{l-1,j-1}\times f_{i-l,j-1}\times (\genfrac{}{}{0ex}{}{i-1}{l-1})$$

复杂度为 $O(n^3)$，瓶颈在预处理 $f$。

一个小小小疑惑：查询都为 $O(T)$ 了，$T$ 的范围还取那么小，搞得我一开始以为不能预处理，要 $O(n^2)$ 在线求方案数...

Reflect

其实已经想到预处理和dp的状态和转移思路了，就是少了最后的插板法，漏想了排序前左右两边可以互相交叉。

---

T2 CF1975D Paint the Tree

题意

给定一个 $n$ 个点的树，初始每个点都是白色的，A 和 B 分别位于 $a$ 和 $b$，每一步会进行以下两个操作：

• A 移动到相邻的点，若该点是白色的，则将其染成红色；

• B 移动到相邻的点，若该点是红色的，则将其染成蓝色。

将所有顶点都染成蓝色所需要的最少步数。

$1\le n\le 2\times {10}^5$

Solution

• 找到 $a$ 和 $b$ 之间最短路径的中点 $c$，以 $c$ 为根求跑完整棵树的最短路。

上面的结论可以用交换论证法简单证明，不再赘述。

最后求跑整棵树的最短路不必用树形 DP，小技巧吧，每条边都必然要经过两次，也就是 $2(n-1)$，由于不用返回起点，再找到以 $c$ 为根的树中的最大深度 $d$，最短路长度就为 $2(n-1)-d$。

---

T3 P12546 [UOI 2025] Convex Array

题意

给定一个长度为 $n$ 的序列 $a$，判断是否存在一种元素排列 $b$，使得对于每个 $2\le i\le n-1$，都满足 $b_{i-1}+b_{i+1}\ge 2\times b_i$。

$3\le n\le 3\times {10}^5,0\le a_i\le {10}^9$

Solution

$b_{i-1}+b_{i+1}\ge 2\times b_i⟺b_i-b_{i-1}\le b_{i+1}-b_i$，也就是说排列 $b$ 中相邻两点间的斜率单调不降，表现为下凸包。

对 $a$ 序列排序，最后的排列中一定是 $a_1$ 在下凸包的最低点，左右两边分成两个独立的部分，且差分序列单调不降。

从小到大往左右序列插入 $a$，前提条件只和该序列中的最大和次大值有关，于是设 $f_{p,q,l,r}$ 表示考虑到第 $i$ 个时，是否能做到左序列的最大值 $p$ 和次大值 $q$，右序列的最大值 $l$ 和次大值 $r$。

由于题目不要求计数，对于左右序列的顺序不作区分，发现 $p,l$ 中必然有一个是 $i$，不妨钦定 $p$ 为 $i$，且 $i$ 位于左序列，也就是 $f_{i,q,l,r}$，暴力转移，时间复杂度为 $O(n^4)$。

$i-1$ 也必然在状态中，时间复杂度降为 $O(n^3)$。

接下来讨论 $i-2$ 的分布：

• 在左序列中：

  • $\{(i,i-1),(x,y)\}$
  • $\{(i,i-2),(i-1,x)\}$

• 在右序列中：

  • $\{(i,i-1),(i-2,x)\}$
  • $\{(i,x),(i-1,i-2)\}$

（其中 $x,y$ 为未知数）

综上，可以列出三种状态：

• $\{(i,i-1),(f_1,x)\}$ （包括了上面 $\{(i,i-1),(i-2,x)\}$ 的情况）
• $\{(i,i-2),(i-1,f_2)\}$
• $\{(i,f_3),(i-1,i-2)\}$

这里的 $f,x$ 都是未知数。

考虑插入 $a_{i+1}$ 时的转移，分讨插入左序列还是右序列，令 $i^{\prime }=i+1$：

• 插入左序列（$2\to 1$）：

  $$\{(i,i-2),(i-1,f_2)\}\to \{(i^{\prime },i^{\prime }-1),(f_1^{\prime }=i^{\prime }-2,x=f_2)\}$$

• 插入右序列（$2\to 2$）：

  $$\{(i,i-2),(i-1,f_2)\}\to \{(i^{\prime }-1,f_2^{\prime }=i^{\prime }-3),(i^{\prime },i^{\prime }-2)\}$$

同理可推得 $3\to 1/2$ 的转移，并且 $2/3\nrightarrow 3$，注意在转移前判断插入的判定条件。

当 $f_2,f_3$ 越大时，与其所在序列中的最大值的差值就越小，也就更易于转移，若最大的 $f_2,f_3$ 都无法转移的时候，较小的也无法转移，所以只需要维护最大的 $f_2,f_3$ 状态，用两个变量 $O(1)$ 维护即可。

接下来考虑状态 $1$ 的转移，设 $g_i$ 表示考虑到 $i$ 时，合法的状态 $1$ 组成的集合，分类讨论：

• 插入左边（$1\to 1$）：$(i,i-1)\to (i^{\prime },i^{\prime }-1)$，前提是 $a_i-a_{i-1}\le a_{i^{\prime }}-a_{i^{\prime }-1}$，若不满足，说明 $g_i\cap g_{i^{\prime }}=\mathrm{\varnothing }$；

• 插入右边（$1\to 3$）：$(f_1,x)\to (i^{\prime },f_1)$，前提是 $a_{f_1}-a_x\le a_{i^{\prime }}-a_{f_1}$，即 $a_{i^{\prime }}\ge 2\times a_{f_1}-a_x$。

  $$\{(i,i-1),(f_1,x)\}\to \{(i^{\prime },f_3^{\prime }=f_1),(i^{\prime }-1,i^{\prime }-2)\}$$

上文提到 $f_3$ 只用维护最大，相当于要找到所有满足 $a_{i^{\prime }}\ge 2\times a_{f_1}-a_x$ 的 $f_1$ 中的最大值；

令 $v=2\times a_{f_1}-a_x$，利用单调队列的思想，用 map （其实也可以用其他的类似于 set 等数据结构）按 $v$ 的大小来维护合法集合 $g_i$ 的单调队列，每次转移时只需要找到前缀 $[1,a_{i^{\prime }}]$ 中最大的 $f_1$；

加入新的点 $(v,f_1)$ 时，把 map 中满足 $V\ge v,F\le f_1$ 的劣点 $(V,F)$ 给删去，保持单调不减即可。

时间复杂度为 $O(n\log n)$，瓶颈在 map 的 $O(\log n)$ 查询，空间复杂度为 $O(n)$。

---

T4 P11516 [CCO 2024] Summer Driving*

点分树？蒟蒻不会，跑了跑了。

---

09/13

T1 P11662 [JOI 2025 Final] 方格染色 / Grid Coloring

题意

对一个 $n\times n$ 的网格图染色，给定两个序列 $a_i,b_i$，分别表示 $(1,i)$ 和 $(i,1)$ 被染上的颜色，一个格子 $(i,j)$（$2\le i,j\le n$）的颜色 $c_{i,j}$ 为 $max\{c_{i-1,j},c_{i,j-1}\}$。

在染色结束后，求被染上的次数最多的颜色编号，以及其染色的次数。

$2\le n\le 2\times {10}^5,1\le a_i,b_i\le {10}^9$

Solution

很显然能看出来对于格子 $(i,j)$（$2\le i,j\le n$），其颜色为矩阵 $(1,1,i,j)$ 中所有格子颜色的最大值（由于 $(1,1)$ 对后面所有的染色没有贡献，这里选择忽略），也为 $max\{\underset{2\le l\le i}{max}{a}_l,\underset{2\le r\le j}{max}{b}_r\}$。

进而可以想到维护 $a,b$ 的前缀最大值，得到两个单调不减的序列；然后对于行 $i$，该行有 $\sum _{j=2}^n[b_j\le a_i]$ 个格子被填上 $a_i$ 这种颜色；对于列 $j$ 同理可得 $\sum _{i=2}^n[a_i\le b_j]$，再统计贡献即可。

统计可以用 map，也可以离散化后用数组记录。

时间复杂度为 $O(n\log n)$，瓶颈在排序。

Reflect

当 map 只是用来记录出现次数时，可以换为 unordered_map。

---

T2 P12576 [UOI 2021] 数字图/AT_arc038_d [ARC038D] 有向グラフと数

dalao hyh 和我说这个 trick 很典也很常用！！！

题意

有一个 $n$ 个点 $m$ 条边的连通有向图，每个点 $i$ 上有一个数字 $a_i$，棋子一开始放在点 $1$ 上，A 和 B 依次移动棋子，两人都可以在自己移动的回合内终止游戏，且游戏最多会进行到 ${10}^{100}$ 回合自动结束。

A 希望最大化最终获得的数字，而 B 则希望最小化最终获得的数字，两人都用最优的策略，求游戏结束时将获得的数字。

$1\le n\le 2.5\times {10}^5,1\le m\le 5\times {10}^5,1\le a_i\le {10}^9$

Solution

博弈论问题，小 trick：

• 二分答案 $x$，将 $a_i\ge x$ 的点赋值为 $1$；反之赋为 $0$。

对于二分赋值后的图分析，若点 $1$ 的权值为 $1$，先手必胜；否则先手必然会把棋子移向相邻的权值为 $1$ 的节点，如果没有这样的点，那么后手必胜。

对于后手的选择明显也同上，最优的策略是把棋子权值为 $0$ 的点上。

如果出现 $1,0$ 一直交替出现的路径，也就是形成了环，由于最大的回合数为偶数，所以最后的赢家必然是后者。

发现对于图中所连两个点权值相等的边，其实是不会走的，不妨删去；对于没有出边的点 $i$，到 $i$ 时的先手必输。

考虑 SG 函数，反向建图，直接拓扑排序，对于起始点 $i$，显然有 $SG(i)=0$；对于 $i$ 在原图中的前驱点 $j$（即反图中 $i$ 指向的点），都有 $SG(j)=1$。

思考一下，现在已知的必胜点已经没有意义了，因为从原图上来讲，没有 $j$ 的前驱 $k$ 上的先手会无脑选择走到点 $j$，从而使得后手赢，所以可以把该轮确定的点 $j$ 都忽略，而去寻找反图中 $j$ 指向的没有确定必胜状态的点 $k$；

若点 $k$ 的所有入边都已经遍历完了，还是没有确定必胜，则有 $SG(k)=0$，并把点 $k$ 加入队列。

最后判断 $SG(1)$ 是否为 $1$，若为 $1$ 说明游戏结束时获得的数字至少为 $x$。

注意一个小问题，如果出现环，且点 $1$ 在环上，由于环上所有的点都不会入队，所以 $SG(1)$ 也必然不会被赋为 $1$。

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

---

T3 P11986 [JOIST 2025] 救护车 / Ambulance*

蒟蒻不会。

---

T4 P11303 [NOISG 2021 Finals] Pond

题意

数轴上有 $n$ 个点，从第 $k$ 个点出发访问所有点，记首次到达第 $i$ 个点的时刻为 $t_i$，最小化 $\sum t_i$。

注：给定 $n-1$ 个整数 $d_i$，表示相邻两点间的距离。

$2\le k\le n\le 3\times {10}^5,1\le d_i\le {10}^6$

Solution

有一点像前面的那道 P10207 [JOI 2024 Final] 马拉松比赛 2 / Marathon Race 2？但是没有那么好的性质。

对 $d_i$ 进行前缀和，将其转化为数轴上的点 $x_i$。

依旧暴力 dp，$f_{l,r,0/1}$ 表示已经访问过了 $[l,r]$ 内的所有点，当前位于 $l/r$ 时的最小时间。这个状态是平方级别的，很难优化。

观察整个移动过程，发现贡献可以拆成从 $k$ 直接往两边走的时间 $\sum |x_i-x_k|$ 和在 $k$ 的两边来回移动的时间。

分析向左边走，对于从点 $k$ 走到点 $i$ 时，改变方向去了右边的点 $j$，再走回来，这时点 $j$ 对于前 $i-1$ 个点的额外贡献为 $2(x_j-x_i)\times (i-1)$，因为到前 $i-1$ 个点的时间都增加了 $2(x_j-x_i)$。向右走同理。费用提前计算的思想？

不妨让 $f_i(i\le k)$ 表示当前走到点 $i$ 产生的额外贡献之和的最小值，$g_i(i\ge k)$ 表示当前走到点 $i$ 产生的额外贡献之和的最小值，得到转移：

• 转移到 $i$ 时，对 $(j,n]$ 的点都额外贡献了 $2(x_j-x_i)$：

$$f_i=\underset{j\ge k}{min}{g}_j+2(x_j-x_i)\times (n-j)$$

• 转移到 $i$ 时，对 $[1,j)$ 的点都额外贡献了 $2(x_i-x_j)$：

$$g_i=\underset{j\le k}{min}{f}_j+2(x_i-x_j)\times (j-1)$$

其实转移状态的过程可以理解为找转折点（改变方向）的最优选择方案。

最终的最小时间为 $min\{f_1,g_n\}+\sum |x_i-x_k|$。

但是发现转移有环且顺序不定，把转移看成正权无向图上的边，依照最短路的思想可以 dijkstra，从最小的点开始转移，考虑完 $[l,r]$ 后再选择 $l-1$ 和 $r+1$ 中更小的转移。

直接转移是 $O(n^2)$ 的，拆开转移式发现可以用斜率优化，上李超线段树维护即可，时间复杂度为 $O(n{\log }^{2}n)$。

也可以把状态转化成凸包，$O(n)$ 维护凸包，不过更麻烦？

---

09/17

在宿舍偶遇到很有感觉的大雨，幸运当时在丢瓶子，并未洗澡，得以获得在宿舍走廊玩雨的机会（真的很爽啊qwq）

后续：晚上开始喉咙痛...

第二天下午去医院看病了...

---

09/16 - 09/19

初赛复习

---

09/20

CSP-2025-S1 比赛日

考点在石门实验学校，我是跟学校租的大巴一起出发和返回的。

上午补了一道模拟赛的题，浅浅看了一下初赛复习的笔记；

中午吃了顿面，回机房看已经结束的 J1 试题，最后一道题考法很新颖，于是尝试了一下。

$13:00$ 上大巴出发，大概 $13:30$ 到的，然后就故地重游，感慨了一下小学部的设施，和我以前的初中部完全就不是一个样的，剩下大部分时间在明德楼楼下闲聊。

$14:00$ 可以去考场了，有幸体验了石实的新教室，就是不一样哈。

$14:30$ 准时开考，并没有提前做完，最后五分钟才作答和检查完毕。

关于考题，我压中了一道主定理，这个是我备赛第一天就笃定会考的，直觉还是不错的。

$16:30$ 结束考试，然后天气不怎么好，下大雨，导致本来预定的 $16:40$ 返程一直拖到了 $17:30$，中间经历了什么找车啊的小事，走了两次反方向的路，最终上车前鞋里已经全是水了，也是历经 $2h$ 的湿鞋回到家。

在车上讨论了一会儿，已经知道自己错了几道题，只剩 ${89}^{\prime }$ 了，预估自己 $[{85}^{\prime },{89}^{\prime }]$，痛惜没认真去理解最后一个完善程序题（考场上是靠感觉做的），不然应该更高的。

上小图灵估分，一开始是 ${87}^{\prime }$，但是我觉得有一道题小图灵错了，后面小图灵又改了，变成了 ${89}^{\prime }$。

预期：$89$ pts

$09/25$ upd：$89$ pts

---

09/22

T1 AT_abc302_g [ABC302G] Sort from 1 to 4

题意

给定一个长度为 $n$ 的序列 $a$，$a_i\in [1,4]$，可以任意交换位置，求使得序列 $a$ 变成单调不减序列的最小交换次数。

$2\le n\le 2\times {10}^5$

Solution

很容易能想到让 $a_i$ 向其属于的位置连边，不妨将整个序列划分成 $4$ 个区间，$cn{t}_{i,j}$ 表示 $i$ 区间的数向 $j$ 区间连边的个数。

接着一个很简单的性质，连边后必然会构成若干个环，且每个环的大小 $\le 4$；一个大小为 $m$ 的环的贡献为 $m-1$，最小化交换次数，其实就是最大化环的个数。

然后就能想到依次找大小为 $2,3,4$ 的环，记录贡献即可。

---

T2 P11338 [COI 2019] LJEPOTICA

没怎么学过数位 dp，于是趁着台风假补学了一下。

引用当天发的犇犇：

• 当你放弃记忆化搜索而选用最淳朴的方法去做多状态的数位dp，你将会达成“惊人的注意力”成就

题意

有一个深度为 $n$ 的完全二叉树，从根节点 $1$ 出发，给定一条包含 L,R 的路径 $s$，分别表示向左右儿子移动，每次移动前都可以改变方向（初始方向是不定的），移动过程中恰好改变了 $k$ 次方向，求问所有可能移动到的值域在 $[A,B]$ 之间的节点的权值和。

$2\le n\le {10}^3,0\le k\le n-1$

Solution

很套路的数位 dp 计数题，把 $[A,B]$ 拆成 $[1,B]-[1,A-1]$。

注意，由于初始方向是不定的，要分别算出初始方向为左右的贡献。

每一步的贡献可能为 $\times 2$ 或者是 $\times 2+1$，发现暴力计算贡献非常复杂，不妨把 $\times 2$ 和 $+1$ 分开计算，于是：

$f_{i,j,0/1,0/1}$ 表示移动到第 $i$ 层，改变了 $j$ 次方向，是否按照初始的方向走，是否顶到上界的总贡献；

$g_{i,j,0/1,0/1}$ 表示第 $i$ 层中符合上述条件的数的个数。

转移方程式是好推的，太多了不作分析，时间复杂度为 $O(n^2)$。

其实可以用记忆化搜索？太难理解了，不想打导致的qwq

Reflect

在考场上有一直想着怎么搞定怎么结合 $\times 2$ 和 $\times 2+1$，但是直接做太多太复杂了，其实可以尝试想拆开计数，再合并贡献。

---

T3 P12430 [BalticOI 2025] Exponents

同样的拜谢 @Lgx_Q 大佬的做法。和题解区其他做法都不一样的独特优美做法。

题意

定义 $a$ 和 $b$ 的合并为 $a+b=max\{a,b\}+1$。

给定一个长度为 $n$ 序列 $a$，$q$ 次询问 $(s,t)$，对序列 $a$ 中区间 $[s,t]$ 的任意相邻两个数合并，求合并到最后一个数时的最小值，每次询问之间相互独立。

$1\le n,q\le 3\times {10}^5,0\le a_i\le {10}^6$

Solution

显然的，从最小的数开始合并必然是最优的，所以先考虑权值最小的连续段，设其长度为 $L$，权值为 $x$，先讨论每个数至多合并一次的情况，合并后所有数都满足 $\le x+1$，若使其长度尽可能小，则以后合并的次数就变少，最终的值也就更小，那么就令相邻数两两配对，新的长度为 $\lfloor \frac{L}{2}\rfloor$。

由上可以推出：把连续段中所有数变成 $\le y$ 时的最小长度，就是 $\lfloor \frac{L}{2^{y-x}}\rfloor$。

令 $f(x)=\lfloor \frac{x}{2}\rfloor$，记 $y$ 次复合为 $f^y(x)=f(f^{y-1}(x)),y\ge 2$，要证明：$f^y(x)=\lfloor \frac{x}{2^y}\rfloor$：

• 引理：对于任意整数 $n$ 和正整数 $m$，有 $\lfloor \frac{\lfloor \frac{n}{m}\rfloor }{k}\rfloor =\lfloor \frac{n}{mk}\rfloor$。
  • 证明；设 $n=mq+r,0\le r<m$，则 $\lfloor \frac{n}{m}\rfloor =q$； 再设 $q=ks+t,0\le t<k$，则 $\lfloor \frac{q}{k}\rfloor =s$; 于是有 $n=m(ks+t)+r=mks+mt+r$。 由于 $mt+r<mt+m\le m(t+1)\le mk$，所以 $mt+r<mk$；因此 $\lfloor \frac{n}{mk}\rfloor =s=\lfloor \frac{\lfloor \frac{n}{m}\rfloor }{k}\rfloor$，证毕。
• 用归纳法证明。当 $y=1$ 时，显然成立：$f(x)=\lfloor \frac{x}{2}\rfloor =\lfloor \frac{x}{2^1}\rfloor$。 假设对某个 $y\ge 1$ 有 $f^y(x)=\lfloor \frac{x}{2^y}\rfloor$，那么 $f^{y+1}(x)=f(f^y(x))=\lfloor \frac{f^y(x)}{2}\rfloor =\lfloor \frac{\lfloor \frac{x}{2^y}\rfloor }{2}\rfloor$； 令 $n=x,m=2^y,k=2$，由引理可得 $f^{y+1}(x)=\lfloor \frac{x}{2^{y+1}}\rfloor$。 由数学归纳法，对任意正整数 $y$，有 $f^y(x)=\lfloor \frac{x}{2^y}\rfloor$，证毕。

模拟一下过程，其实就是权值小的连续段向上往权值大的连续段合并；顺着思路，对全局从大到小建立出来一个广义笛卡尔树状物，对于树上的点 $u$，值域区间为 $[l_u,r_u]$，设 $f_u$ 表示对原序列中的区间 $[l_u,r_u]$ 进行合并后得到的新序列 $b$ 满足 $\mathrm{\forall }i,b_i\le a_u$ 时的最小长度；由树的底部向上转移。

令 $ls,rs$ 为 $u$ 的左右儿子，那么容易得到转移式为：

$$f_u=\frac{f_{ls}}{2^{a_u-a_{ls}}}+\frac{f_{rs}}{2^{a_u-a_{rs}}}+1$$

考虑将询问 $(s,t)$ 挂在笛卡尔树的 $z=lca(s,t)$ 上，转移到 $z$ 时再处理询问。

• 一个小 trick：当询问 $(l,r)$ 支持离线且在分治、笛卡尔树等具备树分支结构上操作时，可以尝试维护贡献的前后缀。

改定义为 $f_u=f_{l_u,r_u}$，以点 $u$ 为分界线维护前缀 $g_i=f_{i,u-1}$ 和后缀 $h_j=f_{u+1,j},u+1$。挂在点 $u$ 上的区间 $[s,t]$ 合并到最后一个数的最小值就是 $a_u+\lceil {\log }_2(g_s+h_t+1)\rceil$。

维护前缀 $g$ 和后缀 $h$ 可以用线段树实现，对区间作向下整除运算（注意特判除以 $1$ 的情况，此时不需要操作）；线段树维护区间最大值 $mx$，最小值 $mn$，除数 tag $k1$，是否被覆盖 tag $k2$；对于一段区间，若 $\lfloor \frac{mx}{k1}\rfloor =\lfloor \frac{mn}{k1}\rfloor =v$，则说明这个区间当前操作完后数值都为 $v\to k2$，直接覆盖即可。

由势能分析，每个数最多被除 $O(\log V)$ 次，所以时间复杂度为 $O(n(\log n+\log V))$。

---

T4 P9536 [YsOI2023] Prüfer 序列*

---

09/23

“桦加沙”台风，最低达到 900.3 百帕了？因此，佛山竟然放了两天台风假，记得上一次还是小学时的“山竹”台风。

昨天晚上不是说肯定不放假的吗？？？

---

09/24

台风在登陆向西折了，对珠三角的影响不大，我甚至都感觉没来过。

放假了，台风又过来应付一下，最好的结果？其实周末要补课...

---

09/25

出初赛分数了。

S 组的保护分数线是 ${62.5}^{\prime }$，预料之中？

怎么又考一套模拟赛，上一套都还没补完呢；zsq 说以后一周三套模拟赛，如何呢。

---

T1 AT_abc307_f [ABC307F] Virus 2

题意

给定一张 $n$ 个白点 $m$ 条边 $(u_i,v_i,w_i)$ 的有权无向图，第 $0$ 时刻，有 $k$ 个点被染成了黑色。

有 $d$ 个时刻，在第 $i$ 时刻时，若点 $j$ 被染成黑色的条件：

• 与任意一个被染成黑色的点最短距离 $\le X_i$。

问每个点被染成黑色的最早时间，若无法被染成黑色，则输出 -1。

$1\le k\le n\le 3\times {10}^5,0\le m\le 3\times {10}^5,1\le d\le 3\times {10}^5$

$1\le u_i,v_i\le n,1\le w_i,X_i\le {10}^9$

Solution

实质是对图跑多源最短路，问题在于如果在第 $i$ 时刻对所有黑点的边都进行遍历，复杂度为平方级别。

考虑用小根堆维护黑点与白点之间的连边，对于第 $i$ 时刻，直接从 $\le X_i$ 的边开始做多源最短路，用堆维护最大的剩余距离 $x_u$，遍历 $u$ 的连边 $(w_{u,v},v)$：

• 若 $w_{u,v}\le x_u$，则说明第 $i$ 时刻初始的黑点能够到达点 $v$，且 $x_v=x_u-w_{u,v}$；
• 若 $w_{u,v}>x_u$，则说明还无法将点 $v$ 染成黑色，将 $(w_{u,v},v)$ 加入小根堆中。

每条边都只会被遍历一次，均摊下来是 $O(n)$ 级别的（$n,m$ 视为同阶）。

总时间复杂度为 $O(n\log n)$，瓶颈在堆维护连边和最短路，把这种做法称为双堆做法。

Reflect

接下来讲一下另一种做法（也是考场上的雏形思路，顺便反思）。

定义每个点最后在第 $d_i$ 天被染成黑色。

一开始是想着对 $X_i$ 前缀和 $s_i$，然后跑多源最短路，再对每个点的 $di{s}_i$ 进行二分答案；

接着发现对于每个点，在第 $d_i$ 天被染成黑色时需要的路程不一定是原图的最短路；

尝试在做多源最短路时二分答案 $d_i$，并把 $s_i\to di{s}_i$，这样就处理掉了上面的问题；

紧接着随着而来的又一个问题，对于点 $i$ 的邻点 $j$ 来说，可能满足 $d_i=d_j$，按照上面的更新方法无法实现这种情况。

下面的我考场上就没想到了...

其实跟第一种方法的本质的思考点，问题出在 $di{s}_i$ 就更新成了 $s_i$，那不妨改变其定义，每个点的 $di{s}_i=(d_i,x_i)$ 表示点 $i$ 在第 $d_i$ 天被染成黑色，与其源头的距离为 $x_i$，那么转移为：

• 若 $x_u+w_{u,v}\le X_{d_u}$：
  • $di{s}_v\leftarrow (d_u,x_u+w_{u,v})$；
• 反之，则说明点 $v$ 在第 $i$ 时刻不能被染成黑色，找到点 $v$ 被染成黑色的最早时刻 $i(i>d_u)$，满足 $w_{u,v}\le X_i$：
  • $di{s}_v\leftarrow (i,w_{u,v})$。

考虑第二种情况的快速转移，求区间 $[d_u+1,n]$ 中最小的满足条件的 $i$，可以用 st 表预处理，也可以用线段树上二分，复杂度为单 log 或者双 log，区别在于具体实现。

---

T2 P12426 [BalticOI 2025] BOI acronym

题意

有一个由 a,b,c 组成的长度为 $n$ 字符串 $S$，全局的绝对众数是 a。

给定 $\mathrm{\forall }1\le i\le j\le n$ 的 $d_{i,j}$，表示区间 $[l,r]$ 的众数出现的次数（不一定是绝对众数）。

求字符串 $S$ 中每个 a 出现的位置。

$1\le n\le 2000$

Solution

令 $m=d_{1,n}$ 表示 a 出现的次数，很显然可以确定最左/右的 a 出现的位置 $l,r$。

重要性质：考虑从左到右逐位确定每个数是否是 a。

对于 $i$，已经确定了 $[l,i)$ 中 a 的个数为 $x$，分类讨论 $[l,i)$ 和 $[i,r]$ 中是否存在某一段区间满足 a 是绝对众数：

• $[l,i)$ 的前提条件是满足 a 是区间的众数 $d_{l,i-1}=x$ 且判定是绝对众数 $d_{l+1,i-1}=x-1$：

  • 若 $d_{l,i}=x+1$，则说明 $i$ 位置上是 a；否则位置 $i$ 必然不为 a。

• $[i,r]$ 的前提条件是满足 a 是区间的众数 $d_{i,r}=m-x$ 且判定是绝对众数 $d_{i,r-1}=m-x-1$：

  • 若 $d_{i+1,r}=m-x-1$，则说明 $i$ 位置上是 a；否则位置 $i$ 必然不为 a。

• $[l,i)$ 和 $[i,r]$ 的绝对众数都不是 a，则 b,c 一定分别是两边的众数（不一定为绝对众数，可能和 a 的数量相同），由于 a 是 $[1,n]$ 的绝对众数，所以字母 b/c 不可能同时成为两边的众数：

  • 不妨取 $(l,i)$ 和 $[i,r)$，分别舍去了一个 a，那么 b,c 分别是这两段区间的绝对众数，假设 $(l,i),[i,r)$ 的绝对众数分别是 b,c：
    • 若 $d_{l+1,i-1}=d_{l+1,i}$，则说明第 $i$ 位不是 b；
    • 若 $d_{i,r-1}=d_{i+1,r-1}$，则说明第 $i$ 位不是 c。
  • 综上所述，若同时满足 $d_{l+1,i-1}=d_{l+1,i}$ 且 $d_{i,r-1}=d_{i+1,r-1}$，则第 $i$ 位是 a。

这部分是线性的，总时间复杂度为 $O(n^2)$，瓶颈在输入qwq。

Reflect

在 $[l,i)$ 和 $[i,r]$ 中存在某一段区间满足 a 是绝对众数时，不能用 $d_{l+1,i}=x$ 或 $d_{i+1,r-1}=m-x-2$ 去判定第 $i$ 位是否为 a，因为不能保证区间 $[l+1,i-1]$ 和 $[i,r-1]$ 的绝对众数是 a（我们只推出了 $[l,i)$ 或 $[i,r]$ 的绝对众数是 a，要想清楚，依据已有条件来拖判定式）。

---

T3 P12558 [UOI 2024] Heroes and Monsters*

---

T4 [Baekjoon 21096] Binary Search Tree*

---

09/27

T1 CF1984D "a" String Problem

题意

给定一个仅包含小写字母的字符串 $s$，求满足以下条件的子串 $t$ 的个数：

• $t\ne \text{a}$；
• $s$ 可以由若干个 $t$ 和若干个 $\text{a}$ 组成；
• 组成 $s$ 的子串中至少有一个 $t$。

$2\le |s|\le 2\times {10}^5$

Solution

很容易想到分类计数：

• $1$ 类子串：以 $\text{a}$ 作为 $t$ 的开头；
• $2$ 类子串：以其他字符作为 $t$ 的开头。

显然 $2$ 类子串的计数更加容易想，因为要保证 $s$ 中不为 $\text{a}$ 的位置都被覆盖到，且这样的 $t$ 的开头必然是第一个不为 $\text{a}$ 的字母 $s_p$；

枚举 $2$ 类子串 $t$ 的长度 $i$，那么 $s_{[p,p+i-1]}$ 就是 $t$，然后向后跳判定这个子串 $t$ 是否满足条件，找到 $s_{(p+i-1,n]}$ 中第一个不为 $\text{a}$ 的位置 $x$，查找可以预处理，判断 $s_{[x,x+i-1]}$ 是否为 $t$：

• 若为 $t$，则继续跳，直至不能跳为止，如果最后 $s_{[x,n]}$ 中的字符都为 $\text{a}$，说明这个 $t$ 是满足条件的子串之一；
• 否则说明这个 $t$ 不满足条件，舍去。

接下来考虑怎么处理 $1$ 类子串，发现一个关键性质：$1$ 类子串中必然包含满足条件的 $2$ 类子串。

那么就可以在找到满足条件的 $2$ 类子串 $t$ 时加以计算，将该子串 $t$ 在 $s$ 中的起始位置 $x$ 都记录下来，只需要取相邻两个 $t$ 之间的 $\text{a}$ 的个数的最小值 $m$，即 $1$ 类子串的贡献；再加上 $1$ 个 $2$ 类子串的贡献即可。区间 $\text{a}$ 的个数可以用前缀和维护。

由调和级数可以知道时间复杂度是 $O(n\log n)$ 的。

Reflect

要想完全想清楚怎么打了再去打代码，不然边打边想效率很低；还有不要乱加特判，计数时要仔细一点，想的要周到些。

---

T2 P11352 [NOISG 2024 Finals] Coin

题意

有 $n$ 个不同的硬币，称重 $m$ 次，第 $i$ 次称重 $(x_i,y_i)$ 表示 $x_i$ 比 $y_i$ 轻。

找出每个硬币首次确定排名的称量序号，或者判断这个硬币的排名永远无法确定。

$2\le n\le 2\times {10}^5,1\le m\le 8\times {10}^5$

Solution

很容易想到让 $x_i$ 向 $y_i$ 连边，其实就是在 $n$ 个点 $m$ 条边的 DAG 上对每个点 $u$ 求最小的 $i$ 使得保留 $i$ 条边后点 $u$ 的拓扑序唯一（通俗点讲就是 $\mathrm{\forall }v\ne u$，都有 $u\to v$ 或 $v\to u$ 的路径）。

考虑对 DAG 做拓扑排序，显然点 $u$ 能被确定需要满足：

• 点 $u$ 出队列时，队列为空（若还有节点 $v$ 在队列中，无法比较 $u$ 和 $v$ 的大小，也就不能确定点 $u$ 的排名）；
• 可以由当前节点到达剩下还未入队列的点。

先想第二个条件，思考一个性质：对于 DAG 上的保留每个点的一条入边，不影响连通性。

由此对于每个点，只需要维护 未被遍历的入边 中出现的时间最小的那条边，求这些边的最大值即可，可以用 set 或优先队列实现。

对 DAG 正反做两次拓扑排序，记在正反拓扑到点 $u$ 时未被遍历的点的数量分别为 $s,t$，若 $s+t=n-1$，则点 $u$ 必然能被确定；反之不能。

时间复杂度为 $O(n\log n)$，瓶颈在于 set 或优先队列（可能优先队列会更快？）的维护；空间复杂度为 $O(n)$。

---

T3 [Baekjoon 18760] Heavy Stones*

---

09/30

2025.09 每月回顾题目

这个月任务量太大了，没怎么顾及这个记录，才写了两题，下个月尽量写吧...

就一直等着放假，期间和超强的 lyl 猜城市。

晚上抢十一国庆的广东博物馆票，运气好抢到了。

国庆八天假，放三天，国庆一号二号，六号中秋，呜呜呜。

---

10/01

去广东省博物馆咯。

---

10/03

不要回校集训啊啊啊！！！

今天的后两题是给人做的吗。

T1 CF1942C2 Bessie's Birthday Cake (Hard Version)

题意

有一个正 $n$ 边形，顶点从 $1$ 到 $n$ 顺时针编号，有 $x$ 个关键点 $a_i$，至多再选 $y$ 个关键点，在关键点之间连边，边不相交，最大化切出的三角形个数。

$4\le n\le {10}^9,2\le x\le min\{n,2\times {10}^5\},0\le y\le n-x$

Solution

先将已知的关键点互相连边，一个 $m$ 边形最多被切出 $m-2$ 个三角形，解法之一就是对一个点向除了相邻的点外的 $n-3$ 个点分别连边，构成 $n-2$ 个三角形，初始化 $cnt\leftarrow n-2$。

考虑在两个相邻的关键点之间选点连边，比较优的选法肯定是隔多个点选一个，贡献为 $2$，因为会多出来一条相邻的边；若同时选择两个相邻的点，贡献为 $1$，更劣。

由于间隔数的大小与贡献没有关系，$y$ 足够的情况下，为了贡献最大化，就需要更多的关键点，所以最优的选法就是隔一个点选一个。

如下图，两个红点为初始的关键点，黄点为选择的关键点，以 $A_1$ 为源点，向 $A_3,A_5$ 连边（黄边），$A_3,A_5,A_7$ 相邻点之间再互相连边（绿边）， $A_1$ 到 $A_7$ 之间贡献的三角形个数为 $5$：

在选同样多的点的前提下，下面两种选法更劣，$A_1$ 到 $A_7$ 之间贡献的三角形个数为 $4$：

最后对初始相邻两个关键点的间隔数按奇偶数分类讨论计算贡献即可，注意对 $y$ 限制的细节处理。

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

Reflect

隔一个选一个还是容易想到的，计算贡献时思路混乱了，想把初始和选择的关键点拿出来一起算，这样就必须要找出一个源点，很复杂...

以后可以在计算贡献多往子问题算再加起来想。

---

T2 P9737 [COCI 2022/2023 #2] Lampice

题意

在 $(n+1,m+1)$ 的矩阵上有 $k$ 种不同的数字各两个，求满足以下条件的子矩阵数量：

• 长宽均 $\ge 2$；

• 对于每种数字，要么都在子矩阵内，要么都在其外。

$1\le n\le 150，1\le m\le 1000,0\le k\le 2\times {10}^5$

Solution

很明显的异或哈希（和哈希也可以），用随机哈希值（可以用自然溢出 unsigned long long），赋给同种数字的两个位置，对子矩阵做矩阵异或和 $S$，若 $S=0$，则子矩阵满足条件。很套路：

枚举子矩阵 $(i,l,j,r)$ 的 $i,j$，再枚举列 $r$，对矩阵 $(i,1,j,r)$ 维护二维前缀异或和 $s_r$，找到使得 $s_l=s_r$ 的 $l\le r$ 的个数，这个可以用 unordered_map 利用 $O(1)$ 查询实现。

时间复杂度为 $O(n^3)$。

Reflect

一开始想着用扫描线 + 并查集实现？？？后面被 Lindone 大佬点破，题目只要求两个点，而我的并查集维护的是矩阵...

以后遇到判定子矩阵的数量可以往哈希上想，还有记住常用的套路：$O(n^3)$ 维护前缀和的方法，接着利用单调栈或 unorder_map 等计数。

---

T3 P7830 [CCO 2021] Through Another Maze Darkly*

---

T4 P11947 [KTSC 2025] 可爱区间 / maxsum*

---

10/04

T1 AT_abc304_f [ABC304F] Shift Table

---

T2 P3590 [POI 2015 R2] 三座塔 Three towers/P12765 [POI 2018 R3] 三座塔 2 Three towers 2

题意

长度为 $n$ 的仅包含 A,B,C 三种字符的字符串 $s$，求满足以下条件之一的子串的最大长度：

• 只有一种字符；
• 有多种字符，且任意两种字符出现的次数都不相同。

$1\le n\le {10}^6$

Solution

---

T3 P11346 [KTSC 2023 R2] 会议室 2*

---

T4 [Baekjoon 21089] Excluded Min*

---

10/05

T1 P9975 [USACO23DEC] Cowntact Tracing 2 B^

---

T2 P7831 [CCO 2021] Travelling Merchant^

---

T3 P10067 [CCO 2023] Real Mountains*

---

T4 P11983 [JOIST 2025] 展览会 3 / Exhibition 3*

---

10/07

T1 bzoj^

---

T2 P10299 [CCC 2024 S5] Chocolate Bar Partition^

---

T3 P9312 [EGOI 2021] Lanterns / 灯笼*

---

T4 P5642 人造情感（emotion）*

---

10/08

T1 AT_arc132_d [ARC132D] Between Two Binary Strings^

---

T2 P6294 [eJOI 2017] 游戏^

---

T3 PAT_arc119_f [ARC119F] AtCoder Express 3*

---

T4 P9058 [Ynoi2004] rpmtdq*

---

10/09

T1

---

T2 CF2006C Eri and Expanded Sets

---

T3 AT_arc178_d [ARC178D] Delete Range Mex^

---

T4 AT_arc174_f [ARC174F] Final Stage*

---

10/10

T1 P9350 [JOI 2023 Final] 宣传 2 / Advertisement 2^

---

T2 CF1473E Minimum Path^

---

T3 P9020 [USACO23JAN] Mana Collection P*

---

T4 QOJ2378*

---

特别鸣谢

试题出于 GJOJ，来源众多。

有部分文献参考于 garbage_fish