202509~11 测试笔记兼停课记录

暑假太摆烂了，测试全都没认真测，测完也没认真学。

* 表示未学习。

9/1

下午：统计选择半停全停，那肯定得全停。

晚上：最终 GJ 决定所有人 $9$ 月半停，$10,11$ 月全停。

下午还有 $15:00\sim 18:40$ 的测试，问号。

T1

反思

• 组合数预处理出阶乘和阶乘的逆元做。

T2

反思

• 边权只有 0/1 时考虑用 0/1 BFS 求最短路，时间复杂度为线性。

• 不要保留 std::cerr。

T3 P10681 [COTS 2024] 奇偶矩阵 Tablica

题解

假设有 $a$ 行和为 $1$，$b$ 行和为 $2$，$c$ 列和为 $1$，$d$ 列和为 $2$。

则有 $a+b=n,c+d=m,a+2b=c+2d$。

故只需枚举一个 $b$ 就能得到 $a,c,d$。

问题转化为有 $c$ 种颜色的球各一个，另外 $d$ 种颜色的球各两个，放进 $n$ 个盒子里，并且每个盒子球的颜色不同，因为显然同一列的两个球不能放在同一行，求方案数。

首先有选出 $d$ 列的方案数是 $(\genfrac{}{}{0ex}{}{m}{d})$。

先考虑不放进盒子里，只把这 $c+2d$ 个球排成一排的方案数，即 $(c+2d)!$，但是交换任意一对同色球，两种方案等价，共有 $d$ 对，所以排成一排的方案数是 $(c+2d)!\times 2^{-d}$。

接着考虑放进盒子里，同理先选 $b$ 个盒子出来 $(\genfrac{}{}{0ex}{}{n}{b})$。然后发现直接把一排按顺序放进盒子里会导致出现以下两种不合法的情况：

• 在某种方案，盒子 $x$ 里放进了两个同色球。

• 在某种方案，盒子 $x$ 放的是 $\{1,2\}$ 色，而在另一种方案，盒子 $x$ 放的是 $\{2,1\}$ 色，这两种方案的这个盒子本质相同。

对于第二种情况，和上面交换的是同理的，乘上一个 $2^{-b}$ 即可。

对于第一种情况，考虑容斥，令 $t$ 表示至少有 $t$ 个盒子里面放了同色球。

先从 $b$ 个盒子和 $d$ 种颜色里面选 $t$ 个出来，然后盒子和颜色的搭配有 $t!$ 种情况，剩下的就按照上面的排成一排排就行了，$(c+2d-2t)!\times 2^{-d+t}$。还有容斥系数 $(-1{)}^t$。

总的式子是

$$\sum _{a+b=n,c+d=m,a+2b=c+2d}(\genfrac{}{}{0ex}{}{n}{b})(\genfrac{}{}{0ex}{}{m}{d})\sum _{t=0}^{min(b,d)}(-1{)}^t(\genfrac{}{}{0ex}{}{b}{t})(\genfrac{}{}{0ex}{}{d}{t})t!(c+2d-2t)!\times 2^{-d+t-b}$$

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

反思

• 二倍空间。

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

题解

直接考虑对 $x$ 坐标从左往右扫描线，那么加入一个矩形，它会和线段树当前它的祖先，它的儿子里的矩形合并（合并用并查集即可）。和祖先合并是容易 $O(\log n)$ 的，和儿子合并却难以做到。

考虑和儿子合并的都是些什么东西，有的矩形比这个矩形先出现，但是 $y$ 坐标上的长度又比这个矩形要小，所以需要这个矩形向儿子合并。那我们可以等到小矩形撤销的时候，往祖先跑，找到每一个在他之后出现的大矩形，和他合并。

时间复杂度肯定是对的，考虑线段树一个节点上的所有矩形 $y$ 坐标等宽，这些矩形一定是按出现时间从早到晚出现在队列里。然后你从队尾取一段出现时间比这个撤销矩形出现时间要晚的矩形，取出来的这些矩形一定会在这里合并进一个连通块，而队尾那个出现时间最晚的，在后面能够迎接更多的矩形和他合并，所以只留最后一个就行了。这样子你的每个矩形总入队 $O(\log n)$ 次，总出队 $O(\log n)$ 次（线段树特性，一个矩形被放进了 $O(\log n)$ 个节点里，所以你做的时候实际上是 $O(1)$ 的），只有队尾一个矩形被重复操作，可看作 $O(1)$。

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

反思

• STL 只有 vector 够快。

• 注意扫描线边界时条件的判断，$\le /<$ 的使用的选择。

9/2

早上 $12/27$ 位住宿生被锁宿舍，占比高达 $40\mathrm{\%}$。

对此，dly 花费晚上 $1\mathrm{h}$ 讲到班时间，基本都比级组的提前了 $5\sim 15min$，那我肯定不干啊（）。

这届级组还把 $18:55$ 提前到了 $18:50$，六百六十六。

晚上还因此被拉去小报告厅当内阁。

可恶啊，臭马可以全停。

9/4

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

反思

孩子们 set 不欢迎不是自己的 lower_bound。

T2 P6583 回首过去

题解

赛时很快想到对于每个分母 $i$，将他的 $2/5$ 因子全部去掉变为 $j$，其对答案的贡献即为 $\lfloor \frac{n}{j}\rfloor$，容易做到 $O(n\log n)$，但是当时觉得非常的不可优化。

直接优化确实很困难，但是可以换一个思路，考虑对答案贡献 $\lfloor \frac{n}{j}\rfloor$ 的数有哪些，显然这些数都是 $i=j\times 2^x\times 5^y$，如果已知 $j$，计算 $i$ 的个数是容易的，因为有限制 $2^x\times 5^y\le \lfloor \frac{n}{j}\rfloor$，而 $2^x\times 5^y$ 的总量不多，从小到大排序后，就可以快速找出有几个满足限制，这也是 $i$ 的个数。

显然，对于 $\lfloor \frac{n}{j}\rfloor$ 相等的 $j$ 对答案的贡献等价，这启示了数论分块。

但是并不能直接计算答案，我们对 $j$ 有限制不含 $2/5$ 因子，因此在整除分块时，要剔除掉这一段 $j$ 中含 $2/5$ 因子的，容斥一下容易剔除。

反思

可以考虑贡献的规律，快速统计贡献的次数。

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

$T\le 5\times {10}^5$，花费 $x+1$ 秒：孩子们，我们联合把 $N$ 的范围肘烂了。

题解

对于 $G$ 两边的其中一边的球，肯定先取远的再取近的，不然带着这个近的球跑来跑去肯定不优。

因此有推论：第一个被取的球一定是 $1/n$。

设 $f_{0/1,l,r,0/1}$ 表示第一个取的球是 $1/n$，当前准备取 $l$ 和 $r$，当前位置是 $l/r$ 的代价。代价不包含 $S\to 1/n$ 和最终 $\to G$ 的代价。

根据定义，$f_{0,1,n,0}=f_{1,1,n,1}=0,f=+\mathrm{\infty }$。

那么有转移：

$$f_{x,l,r,0}=min(f_{x,l-1,r,0}+(c+1)(X_l-X_{l-1}),f_{x,l,r+1,1}+(c+1)(X_{r+1}-X_l))$$

$f_{x,l,r,1}$ 同理，$c$ 是当前拿着的球数。

解释一下转移方程：因为状态是准备取，所以实则 $l,r$ 都没取，那你选择一边上一个准备取的地方，然后取了它跑过来。

最后 $\to G$ 还有从 $G$ 左边/右边进两种情况取最优。代价需加上前面两种被舍去的代价和捡东西的代价 $N$。

时间复杂度 $O(N^2+Q\log N)$，空间复杂度 $O(N^2)$。

假设有 $n$ 个位置有球，则最优情况下，捡第一个球花费代价 $\ge 2$ 走到第二个球，再花费代价 $\ge 3$ 走到第三个球，……，花费代价 $\ge n$ 走到第 $n$ 个球，则至少花费了 $\frac{n(n+1)}{2}$ 的代价，而 $T\le 5\times {10}^5$，因此，只要 $n\ge {10}^3$，答案全是 NO。

时间复杂度 $O(n^2+Q\log N)$，空间复杂度 $O(n^2)$。

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

题解

把每个人 $i$ 看作区间 $[B_i,A_i]$，若 $c$ 个人的区间有交，那把这个连通块按 $A_i$ 从大到小排序，则有 $A_{i+1}\ge B_i$（区间有交），所以可以让人 $i+1$ 把礼物给人 $i$（$i<c$），而 $B_c$ 必然 $<A_1$，故让人 $1$ 把礼物给人 $c$。

因此，询问一个序列上的区间 $[l,r]$ 不合法，当前仅当存在人 $i\in [l,r]$，它和 $[l,r]$ 中每个人的区间都没有交。

用线段树即可处理出 $[L_i,R_i]$ 表示 $i$ 和 $[L_i,R_i]$ 内每个人的区间都没有交。具体地，按 $i$ 从小到大将每个 $[B_i,A_i]$ 放到线段树上，统计当前覆盖了 $[B_i,A_i]$ 的编号最大的区间，即可得到 $L_i$。$R_i$ 从大到小同理。

问题转换为：询问一个区间 $[l,r]$，是否存在 $i$，使得 $L_i\le l\le i\le r\le R_i$，对 $l$ 做扫描线即可。

当扫到 $L_i$ 时，对 $[i,R_i]$ 加一；当扫到 $i+1$ 时，对 $[i,R_i]$ 减一；当扫到 $l$ 时，查询 $r$ 是否有值。

时间复杂度 $O(N\log N)$，空间复杂度 $O(N)$。

9/5

为配合南海舰队的大蛇，晚上机房拜拜，教室爽坐 $3\mathrm{h}$ 自习。

9/6

爽坐 $4\mathrm{h}$ 自习。

神秘新生坐不住，$11:00$ 不到就开始早退，统统被级长制裁。

原来今天还有模拟赛，机房都没有你让我做。

T1 CF1497D Genius

题解

注意到当 $L<R<i$。

$$2^i-2^R<2^i-2^L$$$$2^i-2^{i-1}=2^{i-1}>2^{i-1}-2^1$$

因此一维从小到大，另一维从大到小，双向转移即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

T2

题意

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

$T\le 100$，$n,k\le {10}^{12}$。

题解

考虑用 $G(n,k)=z$ 表示最后的答案，则有 $G(n,k)=G(n-\lceil \frac{n}{k}\rceil ,k)+\lceil \frac{z^{\prime }}{k-1}\rceil$（之所以是 $k-1$ 是因为被删掉的人并不在 $z^{\prime }$ 内），$G(1,k)=1$。

接下来要证明，$\lceil \frac{n}{k}\rceil$ 的个数不会超过 $\sqrt{n}$。

证明：若 $k\le \sqrt{n}$，则每次被删掉的人数都 $\ge \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(x-1)+1$，$x$ 将持续到 $n$ 减到 $<l$ 的时候，因此 $n-x$ 一共减了 $\lceil \frac{n-l+1}{x}\rceil$ 次，减的次数便是 $s$。

接着考虑推这么多次到最终的答案 $z$。其实是同理的，显然 $\lceil \frac{z}{k-1}\rceil$ 的个数也是 $\sqrt{n}$ 级别的。于是令 $\lceil \frac{z}{k-1}\rceil =x$，则有最大的 $r$ 满足 $\frac{r}{k-1}=x$，即 $r=x(k-1)$，$x$ 持续到 $z$ 加到 $>r$ 的时候，因此 $z+x$ 一共加了 $\lceil \frac{r-z+1}{x}\rceil$ 次。

注意最后不要加超出了 $s$ 次。

时间复杂度 $O(T\sqrt{n})$，空间复杂度 $O(1)$。

T3 P11340 [COI 2019] TENIS

题解

某项取得第 $1$ 的人一定可以取得冠军，将这些人加入集合 $S$ 中。

在某项打败了 $S$ 中的人可以成为冠军，让 $S$ 中的人帮其代打其他人即可。

最终，可以发现可以成为冠军的极大连通块，是排名在 $[1,c]$ 内的选手，其中满足 $[1,c]$ 内的每个选手的三项排名都 $\le c$，并且不存在一个 $d<c$ 满足上述性质。

假设每个选手最高排名是 $L_i$，最低排名是 $R_i$，则 $c$ 满足不存在一个 $i$ 使得 $L_i\le c\le R_i$，且这个 $c$ 最小。

可以对 $L_i$ 处 $+1$，$R_i$ 处 $-1$，维护一个前缀和，则 $c$ 就是最小的前缀和为 $0$ 的位置，由于先加后减，前缀和的任意一个位置都 $\ge 0$，容易用线段树 区间后缀加 与 查询最小值位置 维护。

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

T4 P12445 [COTS 2025] 数好图 / Promet

IOI 2025 rk 34：孩子们这个题我只能拿 $N\le 7$ 的 $4^{\prime }$。

这是我能做的吗。

题解

先考虑 $k=n$，我们可以这样子构造答案：让每一个点 $i$ 都向 $[i+1,n]$ 中的若干个点连边，不能不连，这样子就能保证每个点都能到达 $n$，此时每个点的都有 $(2^{n-i}-1)$ 种连边方案。

这样子肯定会构造出不合法的方案，因为没有保证 $1$ 能够到达每个点。$1$ 不能到达每个点的条件是存在一个点的入度为 $0$，那么考虑容斥。

设 $f_{i,j}$ 表示当前考虑到 倒数第 $i$ 个点（$n-i+1$）；倒数第 $i-1$ 个点 到 倒数第 $1$ 个点 中，至少有 $j$ 个点入度为 $0$（为什么是 $i-1$ 后面会说）时，连边的方案数。边界条件是 $f_{1,0}=1$，那么考虑 倒数第 $i-1$ 个点 入度是否为 $0$，则有转移：

$$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\in [0,i)}(-1{)}^j{f}_{i,j}$$

这时候就可以说明上文斜体内容了，转移进 $F_i$ 时，$f_{i,j}$ 入度一定只能为 $0$，这时候对他讨论入度是否为 $0$ 是不正确的。

$k=n$ 做完了，接下来考虑 $k$ 更小的，其实就是往 $F_k$ 里加若干个不合法的点加到 $n$ 个。

加完点后，考虑点 $i$ 有哪些可能：

• $1$：$i$ 是 $F_k$ 中的答案。
• $2$：$i$ 是加的点，$1$ 能到达 $i$，但 $i$ 不能到达 $n$。
• $3$：$i$ 是加的点，$1$ 不能到达 $i$。

其中 $1,n$ 一定是 $1$ 类点，考虑这些点之间连边方案的计数。

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

容易发现，前面的 $3$ 类点可以向后面任意的点连边，所以如果确定了 $3$ 类点的位置 $p_i$，其连边方案就是 $\sum _i{2}^{n-p_i}$。考虑计算出如果固定了 $3$ 类点的个数，所有的连边方案的数量。

设 $g_{i,j}$ 表示 $[i,n-1]$ 中有 $j$ 个 $3$ 类点，所有可能位置的连边方案的总数量。边界条件是 $g_{n,0}=1$，同理考虑 $i$ 号点是否是 $3$ 类点，有转移：

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

现在就差 $2$ 类点了！！根据上文，$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}=h_{i,j}+h_{i,j-1}\times (2^{i+j-1}-1)$$

为什么这个我要拆成两行写呢？因为显然第一行的 $2$ 类点都在第 $i$ 个 $1$ 类点（不含）以前，第二行的则有在第 $i$ 个和第 $i+1$ 个之间的。那么第 $i$ 个 $1$ 类点作为结尾，恰好符合第 $n$ 个点是 $1$ 类点的规则，所以其对 $an{s}_i$ 有贡献！执行完第一行转移后，我们把 $3$ 类点的答案乘进来，有答案统计：

$$an{s}_i=F_i\times \sum _j(h_{i,j}\times g_{2,n-i-j})$$

就差 $k=0,1$ 了！

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

对于 $k=0$，先构造出任意图，方案数是 $2^{n(n-1)÷2}$，减去所有 $k\ge 2$ 的答案，剩下的就是 $k=0$ 的答案。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

9/7

回坑两个月，再次达成原神全收集。

晚上就做了一道题，写了点笔记，摆！

9/8

由于台风登陆，$2:00\sim 3:10$ 都没蹲到血月，哭。

9/9

《科学教育中心第二周教学目录》

《9月9日CSP-S模拟4》

9/10

讲题 $1\mathrm{h}$，讲的一坨，还被发现了前三天的所作所为↑。

9/11

测试被 T1 小细节想复杂爆砍 $0^{\prime }$。

T1

题意

$q$ 次询问，执行 Query(1, n, k) 后，能够从小到大排序的排列 $a_{[1,n]}$ 有多少种？$n,k\le 300,q\le 500$。

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(1, m - 1, h - 1);
        Qsort(m + 1, r, h - 1);
    }
}

题解

看到数据范围，就能想到要么是 $O(q{n}^2)$，要么是 $O(q+n^3)$，由于题目没有强制在线，故先从后者入手。

考虑执行一次 partition(l, r) 函数，其相当于与 $a_r$ 比大小，将 $a_{[l,r]}$ 中 $<a_r$ 的按原本的顺序放入 $a_{[l,x)}$，将 $>a_r$ 的放入 $a_{(x,r]}$ 中，再继续进行递归排序。

因此，设 $f_{n,k}$ 表示排列长度为 $n$，递归次数 $\le k$ 时的答案。枚举 $a_n$ 的取值 $i$，则有 $f_{n,k}=\sum f_{i-1,k-1}\times f_{n-i-1,k-1}$，但这是不够的，因为这只考虑了 partition(l, r) 后的情况，执行这个函数前，序列还可能对应多种情况。

由于 $<i$ 的部分执行函数是按原本的顺序放入 $[1,i)$，因此他们对应的可能就是在 $n-1$ 个位置里选 $i-1$ 个放进去，即 $(\genfrac{}{}{0ex}{}{n-1}{i-1})$。

而 $>i$ 的部分看似在 swap 前后顺序改变，可能对应了多种情况，但实际上，右边改变前后是一一对应的。因为只有左边的当前“侵占”了右边的格子，才会导致右边的需要从左边换过来，改变了他们的顺序，而左边的格子和当前被“侵占”的格子一一对应调换，所以这一部分不用处理，最终就是

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

注意模数不是质数。

时间复杂度 $O(n^{2}k+q)$，空间复杂度 $O(n^2)$。

T2 CF1975D Paint the Tree

gzw round 里面的题。

题解

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

求整棵树的最短路径不一定要换根 DP，考虑如果两点染完之后必须回到一开始的中点，那么每条边都被走了 $2$ 次，答案就是 $2(n-1)$，而现在不必回到中点，贪心的将一条从中点开始的最长的链只走一次就行了，即 $2(n-1)-maxde{p}_u$。

T3 P12546 [UOI 2025] Convex Array

为什么 dalao 们都如此强势。

题解

首先，$b_{i+1}+b_{i-1}\ge 2\times b_i\Rightarrow b_{i+1}-b_i\ge b_i-b_{i-1}$。即相邻两点间的斜率单调不降。因此，最终的 $b$ 序列一定是个下凸包。

将 $a$ 从小到大排序，显然，$a_1$ 是这个下凸包中的最低点。考虑从 $1\to n$ 往凸包中添加 $a_i$，那只能添加到凸包的最左边或最右边，因此，只用考虑最左边的两个数和最右边的两个数这四个数。

仔细思考一下，对于当前 $i$，$a_{i-1}$ 一定属于这四个数，$a_{i-2}$ 可能属于这四个数，那么分类讨论一下状态的种类数。

• $\{(i,i-1),(f_1,c)\}$，
• $\{(i,i-2),(i-1,f_2)\}$，
• $\{(i,f_3),(i-1,i-2)\}$。

只有这三种，其中 $(x,y)$ 表示其中一支的最大值是 $a_x$，次大值是 $a_y$；$f,c$ 是未知数。注意大括号内是无序的，因为左右两支本质一样而本题不要求计数。

接下来考虑从 $i\to i+1$ 转移，就是插入 $a_{i+1}$，分类讨论他插入左边还是右边，插入的条件也要判断一下。发现下面两种的转移是 $O(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,c^{\prime }=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\to 3$。

我们知道，$f_2,f_3$ 越大，与最大值间相差的值越小，因此只要最大的 $f_2,f_3$ 的状态可行即可，这一部分的状态使用两个变量维护。

最后考虑 $1\to $ 的转移，由于有 $(f_1,c)$ 存在，问题变得有点棘手。设 $F_i$ 表示 $i$ 时，第一种的合法状态组成的集合。考虑分类讨论。

$1)$，$(i,i-1)\to (i^{\prime },i^{\prime }-1)$。前提是 $a_{i^{\prime }}-a_{i^{\prime }-1}\ge a_i-a_{i-1}$，如果这不满足，说明 $F_i\cap F_{i^{\prime }}=\text{empty}$。

$2)$，$(f_1,c)\to (i^{\prime },f_1)$。前提是 $a_{i^{\prime }}-a_{f_1}\ge a_{f_1}-a_c$，即 $a_{i^{\prime }}\ge 2a_{f_1}-a_c$。

考虑这个状态最终是转移到了第三种（$\{(i^{\prime }-1,i^{\prime }-2),(i^{\prime },f_3^{\prime }=f_1)\}$）而 $f_3$ 根据上面的分析只需要考虑最大的，那么这里 $1\to 3$ 转移我们也只用找到最大的满足 $a_{i^{\prime }}\ge 2a_{f_1}-a_c$ 的 $f_1$ 即可，将 $F_i$ 中所有合法状态按照 $2a_{f_1}-a_c$ 为下标放进某种数据结构。需要转移时就相当于在 $[1,a_{i^{\prime }}]$ 中找前缀 $max$。

利用单调队列的思想，使用 map 即可维护 $F_i$。你在下标 $w$ 插入 $x$ 时，将 map 中 $W\ge w$ 而 $X\le x$ 的全部删掉，保持 map 内 $X$ 单调递增。查询时查询位置 $w$ 的前驱上的 $X$ 值即可。

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

* T4 P11516 [CCO 2024] Summer Driving

9/13

不如健队，回家打模拟赛了

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

题解

糖题，假设 $a$ 位于第一行，$b$ 位于第一列。

只考虑行，$a_1$ 无贡献，$a_x$ 的“管辖范围”是 $[x,r)$，$r$ 是第一个 $a_r>a_x$ 的数，并且需满足 $\mathrm{\forall }i<x,a_i<a_x$。

对于 $b$ 的情况是类似的。当 $a,b$ 中有相等的可管辖的数时，需要容斥掉右下角的公共部分。

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

原题大赛魅力时刻。

记忆力惊人时刻。

题解

部分分具有提示性的题目。

从 sub 4 入手，当点权只有 $1,2$ 时，若 $a_1=2$，则答案一定是 $2$，先手可直接结束游戏。否则，先手一定会往下一步有 $2$ 的方向移动。后手为了使答案更小，一定会往下一步有 $1$ 的方向移动。当不能移动的时候，当前手必然是输的（假如先手走到了 $2$ 后不能走，当前手是后手）。

设 $f_i=-1/0/1$ 表示在 $i$ 号点，当前手状态未知 / 输 / 赢。因为不是 DAG，有可能成环，所以状态会未知。

转移直接转移就行了，$f_u=1$ 的条件是它的后继状态中有 $0$ 的，$u$ 就会走过去以让下一手输掉。$f_u=0$ 的条件就是它的所有后继状态都确认为 $1$，此时其不得不输。

如果 $f_1=-1$，即未知，那么先手肯定是败的。因为这说明后手可以拉着先手走上一个 $1\to 2\to 1\dots$ 的环，这样子 ${10}^{100}$ 步后，后手赢。

看似直接拓扑排序 DP 就行了，但是这不是 DAG，而 $f_u=1$ 又只需要后继有任意一个 $0$ 即可确定。因此我们拓扑排序的队列里只能放 $f_u=0$ 的状态。那么当 $f_u=0$ 时，找到它的所有未确定前驱状态 $f_v$ 设为 $1$，再对每个 $v$ 找到所有未确定的前驱状态 $w$ 设为 $0$，若 $w$ 的所有后继已经确定，就让它入队。

由于转化成 $0/1$ 问题可做，二分答案，对小于 / 大于等于答案的点权标记为 $0/1$ 即可。

时间复杂度 $O(30(n+m))$，空间复杂度 $O(n+m)$。

T3 P11986 [JOIST 2025] 救护车 / Ambulance

题解

发掘医院性质，对于对角线上的两个医院（如 $(1,L)$ 和 $(L,1)$），他们接受的患者一定被一条 $y=x+b$ 的直线切割，如下图中紫色的去 $(1,L)$，黑色的去 $(L,1)$。因为直线上方的点距离 $(1,L)$ 一定比直线下方的点距离 $(1,L)$ 更近。直线上的多个点均有两种可能，但是他们本质相同（离 $(1,L)/(L,1)$ 的距离相同），所以按离 $(1,L)$ 的距离排序，按顺序枚举即可。

拓展到四个医院，对另外一条对角线上的医院也会有相同的性质，因此我们可以枚举两条 $y=x+b$ 与 $y=-x+b^{\prime }$，将平面分为四个部分。这两条直线必然分别经过至少一个点，否则是可以被替代的。在经过多个点的情况下，需要枚举这上面的点哪些属于其中一部分，哪些属于另一部分。因此直线的数目是 $O(n^2)$。

显然根据上文，每个部分的患者只有两个可选的医院。

定义 $(1,1)$ 为医院 $1$，$(1,L)$ 为医院 $2$，$(L,L)$ 为医院 $3$，$(L,1)$ 为医院 $4$，$c_x(i)$ 表示患者 $i$ 到医院 $x$ 花费的时间。

可以发现，部分 $1$ 的患者分配关系到医院 $1,2$，部分 $2\to$ 医院 $2,3$，部分 $3\to$ 医院 $3,4$，部分 $4$ $\to$ 医院 $4,1$。也就是说，这几个部分的分配是环环相扣的。

因此，设 $f_x(i,t)$ 表示对部分 $x$ 进行分配，分配到第 $i$ 个点，其中分配给医院 $x$ $t$ 点时间，另一个医院 $y$ 最少需要多少时间，来接受完部分 $x$ 的人？

转移是容易的。

• 若点 $i\in x$，$f_x(i,t)=min(f_x(i-1,t-c_x(i)),f_x(i-1,t)+c_y(i))$。
• 若点 $i\notin x$，$f_x(i,t)=f_x(i-1,t)$。

最后令 $f_x(i,t)$ 对 $t$ 这一维取前缀 $min$，即可得到所需。

状态数 $O(nT)$，转移 $O(1)$，时间复杂度 $O(nT)$。

考虑如何检验方案是否合法，枚举医院 $1$ 分给部分 $1$ 的时间 $t_1$，则可以得出医院 $2$ 分给部分 $1$ 的最小时间 $t_2$，$T-t_2$ 即为医院 $2$ 分给部分 $2$ 的最大时间，以此类推。对 $t_2,t_3,t_4\le T$ 进行检验。最后还需要检验一下，部分 $4$ 分给医院 $1$ 的时间加上最初枚举的 $t_1$ 是否合法。

因此，检验的复杂度为 $O(T)$。总复杂度为 $O(n^{3}T)$，不能通过。

将点按 $c_1(i)$ 进行排序，那么从小到大枚举这些点就相当于枚举 $y=-x+b$，接下来按 $c_2(j)$ 从小到大枚举点，就相当于枚举 $y=x+b$，通过判断 $c_1(j)$ 与 $c_1(i)$，即可得出它位于哪个部分，此时在顺势进行 $f$ 的转移，其中 $f_{1/2}$ 是正序，$f_{3,4}$ 是倒序（看图显然）。

因此，我们将状态数的 $O(n)$ 和枚举 $y=x+b$ 的 $O(n)$ 合并进了一个循环，时间复杂度降为 $O(n^{2}T)$，空间复杂度 $O(nT)$。

卡常小技巧：如果有大量数需要 $\times 2$，就将少量数 $÷2$。

T4 P11303 [NOISG 2021 Finals] Pond

题解

显然有类似 $4$ 号 T3 的 DP，但是没啥用，优化不了。

然后题解区大神就想到将贡献拆成直接走过去的贡献 $+$ 迂回走来走去造成的额外贡献。

容易将 $D_i$ 距离转换为每个点在数轴上的坐标 $X_i$，直接走过去的贡献是 $\sum |X_i-X_K|$。

设 $f_i$ 表示从 $K$ 走到 $i$，$i\le K$，因迂回对 $[K,N]$ 的数造成的额外代价。

设 $g_i$ 表示从 $K$ 走到 $i$，$i\ge K$，因迂回对 $[1,K]$ 的数造成的额外代价。

初始条件有 $f_K=g_K=0$。

假设 $f_i$ 从 $g_j$ 这个点迂回回来，到达 $i$ 点时产生的额外贡献，那么从 $j\to i$，后面的 $(N-j)$ 个点全部产生了额外贡献，贡献是迂回距离的 $2$ 倍。，那么转移方程有：

$$f_i=min(g_j+2(X_j-X_i)(N-j))$$

$g_i$ 从 $f_j$ 这个点迂回回来，那么转移方程有：

$$g_i=min(f_j+2(X_i-X_j)(j-1))$$

最终的答案是 $min(f_1,g_n)+\sum$ 前面的。

这个转移一定是对的，你可能会觉得没有考虑到沿着一个方向一直走的情况，那其实就是令 $f_i$ 从 $g_K$ 处转移（当还没向右走时）。

拆开第一个括号，变为 $g_j+2(N-j)\times X_i+2(N-j)\times X_j$，将 $X_i$ 的系数视为 $k$，其它视为 $b$，这就是李超线段树优化斜率优化 DP。

最后还有转移顺序的问题，显然初始时解决出了 $L=R=K$ 处的 $f,g$，接下来要么解决 $[L-1,R]$，要么解决 $[L,R+1]$，根据取 $min$，$f_K\to f_1$ 单调递增，$g_K\to g_N$ 单调递增，因此只需要比较 $f_{L-1}$ 更小还是 $g_{R+1}$ 更小，选择小的进行更新即可。

时间复杂度 $O(N\log N)$，空间复杂度 $O(N)$。

9/22

T1 AT_abc302_g [ABC302G] Sort from 1 to 4

题解

对于 $1$，有在本应是 $2/3/4$ 的位置的，那就找在本应是 $1$ 的位置的 $2/3/4$，贪心的交换一下，不能对应的就随便换，模拟一下这件事就好了，瓶颈在输入数据。

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

反思

要注意值域不连续的情况，用 while 代替 if。

T2 P11338 [COI 2019] LJEPOTICA

2025-09-22 22:07:09 删除 回复 举报

什么数位DP啊，4k 124行差分计数成为最大输家

题解

先考虑差分，将 $\mathrm{solve}(A,B)\to \mathrm{solve}(1,B)-\mathrm{solve}(1,A-1)$。

题目中提到可以开局任选左右，那么只需做一次再把操作序列反转，再做一次，就可以很好的解决。

考虑 $\mathrm{solve}(1,B)$，我们让小明开局尽量沿着 $B$ 走，如果某一步他不变向往右走，还剩 $k$ 次变向的机会，他就可以在这一步变向往左走，后面任意走。

对于任意走的答案的计算，考虑计算每一位的贡献。设 $f_{p,0/1,0/1,i}$ 表示当前走到第 $p$ 位，方向认知是否相反，位于第 $p$ 位是 $0$ 的点还是第 $p$ 位是 $1$ 的点，还剩 $i$ 次变向的机会，此时这样的点的个数。

可以证明，一种变向的方式对应一个唯一的答案，因此，我们可以让后面若干步任意变向 $i$ 次，用一个组合数处理即可。

然后 $f_p\to f_{p+1}$ 的转移是容易的，按照状态定义结合当前的行动序列敲代码就行了。

很有可能在某个状态之后，我们不能够沿着 $B$ 走了，假设走到了 $B$ 的左侧，此时他左侧的任意走状态仍然是有效的，如果这后面他在向右走，左侧的也有可能成为任意走的状态，正常维护即可。

如果走到了 $B$ 的右侧，那他不会再添加新的任意走状态，他也不会计入答案，把当前的任意走状态处理完就行了。

时间复杂度 $O(nk)$，空间复杂度 $O(nk)$。

T3 P12430 [BalticOI 2025] Exponents

拜谢 @Lgx_Q 大佬。

题解

考虑只有一组询问 $[1,n]$ 的情况，我们肯定让小的尽量合成，但又不超过当前的大的，所以建立大根堆笛卡尔树，设 $f_u$ 表示合并 $u$ 的子树内的点，且令合并后的点全部 $\le a_u$，合并后点的个数的最小值。可以证明，合并后 $<a_u$ 的值只有一个。因此，一堆 $a_v$ 合并成 $a_u$，个数就会 $÷2^{a_u-a_v}$。

$$f_u=1+\sum _v{f}_v÷2^{a_u-a_v}$$

于是我们就可以得到全部合并成 $a_{\mathrm{rt}}$ 的个数，可以发现答案是 $a_{\mathrm{rt}}+\lceil {\log }_2(f_{\mathrm{rt}})\rceil$。

接下来考虑询问 $[l,r]$ 的情况，把他挂到笛卡尔树上的 LCA 处进行处理，假设 LCA 是 $u$，那么他在笛卡尔树上管辖的一定是一段区间 $[L_u,R_u]$ 并且和其他的区间不交。因此我们一开始的 $f_u$ 可以看作 $f_{[L_u,R_u]}$，他由 $f_{[L_u,u-1]}$ 和 $f_{[u+1,R_u]}$ 转移过来，但是现在由于询问，我们只希望他从 $f_{[l,u-1]}$ 和 $f_{[u+1,r]}$ 转移过来。因此做法就浮现了。

用两棵线段树维护当前 $f$ 的后缀 $g$ 和前缀 $h$（注意这些前缀后缀不一定是连续的），这里以维护后缀的 $g_l=f_{[l,u-1]}$ 为例。一开始，$g_l$ 还都是合并成 $[l,u-1]$ 合并成 $a_v$ 的个数，我们现在需要知道合并成 $a_u$ 的个数，所以根据上面的转移。

$$g_l\leftarrow \lceil g_l÷2^{a_u-a_v}\rceil$$

$h_r$ 也进行这样的操作，然后我们就可以查询 $g_l+h_r+1$ 得到询问 $[l,r]$ 中，合并后小于等于 $a_u$ 的个数，根据上面的式子也可以算出最终答案。

接着要把 $[l,u-1],[u+1,r]$ 合并成 $[l,r]$，还是以后缀为例。

$$\mathrm{\forall }i\in [l,u],g_i\leftarrow g_i+g_{u+1}+1$$

很好理解，就是把后缀的部分和 $u$ 加上，前缀同理。

分析一下时间复杂度，对于一次区间除，如果除以 $1$ 就无意义，不除。如果区间 $[l,r]$ 内的数相同，直接区间覆盖走人。每个数最多除 $\log$ 次就会变为 $1$，所以是正确的。

所以只需要一个区间覆盖区间加线段树，判断相同只需要维护一下 $max$ 和 $min$。

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

* T4 P9536 [YsOI2023] Prüfer 序列

9/25

初赛 ${87}^{\prime }$，机房下游。

Lindone 佬 AK 了。

T1 AT_abc307_f [ABC307F] Virus 2

笑点解析：

CSP-J2 2023：BFS + 堆实现最短路 | 2025/09：DFS + 堆实现最短路

题解

考虑一个暴力，每一天，我们让当前所有感染的点都做一次另类 Dijkstra，$\mathrm{dis}$ 表示每个点还能感染多远的距离。

考虑优化这个暴力，之前走过的边我们肯定不会再走，因为不如从他走出去的那个点开始走。

如果 $u$ 的出边中边权为 $x$ 的可走，那么边权 $<x$ 的也可走，所以可以将出边按边权从小到大排序，用一个数组标记一下当前走到哪条边。

这样已经是总复杂度 $O(n\log m)$ 的了，但是每一天都要暴力遍历一下感染的点没走过的最小的边能不能走，这成为了时间复杂度的瓶颈。

把所有接下来可能可以走的出边丢进另一个堆里面就行了，每一天从堆中取可以走的出来做 Dijkstra，做完再把新的丢进去。

时间复杂度 $O((n+m)\log m)$，空间复杂度 $O(n+m)$。

反思

笑点解析。

T2 P12426 [BalticOI 2025] BOI acronym

什么叫逐位确定最难想，哪里难想了，我对 B 不是两边的众数思考了 $2\mathrm{h}$ 无果。

题解

可以得到一个最小的区间 $[L,R]$，满足所有的 B 都在 $[L,R]$ 中。

考虑逐位确定 $[L+1,R]$ 中的每个字母是不是 B（注意到 $L,R$ 一定是 B）。假设现在处理到 $i$，设 $x$ 表示 $[L,i-1]$ 中，B 的个数，$y=M_{L,R}-x$ 表示 $[i,R]$ B 的个数。

• B 是 $[L,i-1]$ 的绝对众数。
  • 判断是不是绝对众数，首先判断是不是众数，即 $x=M_{L,i-1}$，但有可能 O 在 $[L+1,i-1]$ 中也出现了 $x$ 次，所以第二个条件是 $x>M_{L+1,i-1}$。
  • 判定第 $i$ 位是不是 B：$M_{L,i}=x+1$。
• B 是 $[i,R]$ 的绝对众数。
  • 判断是不是绝对众数，$y=M_{i,R}\wedge y>M_{i,R-1}$。
  • 判断
• B 不是上面两种情况。
  • 这里有一个惊人（在哪）的观察，两边必然一边的众数是 O，一边的众数是 I。因为如果 O 既是 $[L,i-1]$ 的众数又是 $[i,R]$ 的众数，他一定是整个序列的众数。
  • 这个时候，我们用上面的方法即可判断出这一位是不是左边 / 右边众数对应的字母，如果都不是，那这一位就是 B。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

T3 P12558 [UOI 2024] Heroes and Monsters

题解

先将 $a,b$ 按从小到大排序。由于只关心英雄的选择方案，假如确定了集合 $S$ 的大小是 $m$，里面的英雄从小到大分别是 $a_{x_{1\dots m}}$，不在里面的英雄从大到小，里面分别是 $a_{y_{1\dots n-m}}$。那么就可以贪心地让 $a_{x_i}$ 去打 $b_i$，让 $a_{y_i}$ 去打 $b_{n-i+1}$。因此可以把序列拆成两个部分分别考虑。

设 $f_{i,j}$ 表示考虑完 $a_{1\dots i-1}$，$S$ 中放入了 $j$ 个英雄的方案数，那么就有

$$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times [a_i>b_j]$$

同理设 $g_{i,j}$ 表示考虑完 $a_{i+1\dots n}$，不在 $S$ 中的英雄有 $j$ 个的方案数。

$$g_{i,j}=g_{i+1,j}+g_{i+1,j-1}\times [a_i<b_{n-j+1}]$$

状态数 $O(n^2)$，转移 $O(1)$，这一部分的时间复杂度是 $O(n^2)$。

现在考虑怎么把这两部分接起来。假设确定了集合 $S$ 的大小是 $m$，让 $f_i$ 和 $g_{i+1}$ 拼起来，那么所有英雄由这几部分组成：

1. 在 $[1,i]$ 中，且在 $S$ 中的 $j$ 个。
2. 在 $[1,i]$ 中，且不在 $S$ 中的 $i-j$ 个。
3. 在 $[i+1,n]$ 中，且在 $S$ 中的 $m-j$ 个。
4. 在 $[i+1,n]$ 中，且不在 $S$ 中的 $n-i-(m-j)$ 个。

第 $1,4$ 部分由 $f,g$ 组成，一定合法。由于 $f,g$ 是在范围内任选英雄放入 DP 方案，那么该范围内的英雄都有可能不被选中，那么考虑极限情况，第 $2$ 部分需满足 $a_i<b_m$，第 $3$ 部分需满足 $a_{i+1}>b_m$。

由于 $a,b$ 单调递增且不同，对于枚举的 $m$，只需要找到最大的满足 $a_i<b_m$ 的 $i$，再枚举 $j$ 即可。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

* T4 Baekjoon 21096 Binary Search Tree

9/27

T1 CF1984D "a" String Problem

你这什么数据啊，乱做都能过。

题解

找到第一个不是 a 的字母，去除掉 $t$ 中的前导 a，这个字母必然是 $t$ 的第一个，假设这个字母是 b，出现了 $m$ 次，那么 $t$ 串中的 b 的个数是 $m$ 的因数，所以枚举因数，然后抛去前导 a 判断合法的 $t$ 有多少个，再找一找能加上多少个前导 a。

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

T2 P11352 [NOISG 2024 Finals] Coin

题解

跟上一场 T3 思路挺像，但是更简单一点。

假设已经确定了拓扑序列 $a$，当前我想询问的点 $u$ 是 $a_i$，那么如果只保留 $a_{i\dots n}$，那就相当于询问只保留 $a_{i\dots n}$ 引出的出边，到达每个点的最小时间的最大值，设 $f_u$ 表示这个最小时间。从 $n\to 1$ 将 $a_i$ 加入。那么当新加入 $u=a_i$ 时，$u$ 的所有出边指向的 $f_v$ 都可以更新，求 $f$ 的最大值使用可删堆维护即可。搞完之后，还没有一条边指向 $u$，所以 $f_u\leftarrow m+1$.

如果只保留 $a_{1,i}$，同理做一次即可。

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

T3 P11953 [科大国创杯初中组 2023] 石子

题解

考虑选定第 $x$ 堆石子作为起点，定义 $A_i=a_{x-i},B_i=a_{x+i}$，那么最终的操作一定是合并一段 $A_{1\dots p}$，再合并一段 $B_{1,q}$，再合并 $A_{p+1\dots r}$……考虑 Exchange Argument，什么时候先合并一段 $A$ 比先合并一段 $B$ 更优，即交换 $A,B$ 后对答案的增量贡献为正。对答案的增量易得是

$$\mathrm{len}(A)\times \mathrm{sum}(B)-\mathrm{len}(B)\times \mathrm{sum}(A)$$

即

$$\mathrm{len}(A)\times \mathrm{sum}(B)-\mathrm{len}(B)\times \mathrm{sum}(A)\ge 0$$

时，先合并 $A$ 更优。进一步化简得

$$\frac{\mathrm{sum}(A)}{\mathrm{len}(A)}\le \frac{\mathrm{sum}(B)}{\mathrm{len}(B)}$$

本质是要按平均值从小到大合并段。

对于选定的 $a_x$ 的一边（如只处理 $A$）是好做的，遍历 $A_i$，看一下 $A_i$ 能不能合并进上一段，若这一段的平均值小于上一段的平均值，为了满足平均值从小到大，我们必须让这一段合并进上一段，否则就可以另开一段，这其实相当于一个单调栈。

当有多个询问时，随着 $x$ 从小到大，相当于从 $A$ 的前端插入数，所以不能简单修改单调栈，看似需要每次暴力，但是注意到 $x$ 每右移一位，只会往单调栈里新加一个段，而每个段只会被删除一次，所以时间复杂度可以保证。

接着再考虑另一边，其实同理。那么可以得到所有段的进入时间和删除时间，于是把左右所有段的信息用扫描线维护。对于加入一个段 / 删去一个段，可以用树状数组快速统计出其贡献，就是 $\mathrm{sum}(\le )\times \mathrm{len}(\ast )+\mathrm{sum}(\ast )\times \mathrm{len}(>)+\mathrm{ans}(\ast )$，其中 $\le ,>$ 表示平均值小于等于 / 大于当前段的信息，$\ast$ 表示当前段，$\mathrm{ans}$ 表示段内答案。

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

T4 CF1975D Paint the Tree

？

10/3

T1 CF1942C2 Bessie's Birthday Cake (Hard Version)

题解

注意到每隔一个添加一个点可以添加两个三角形，而一段空格恰好可以这样添加（即到最后一个放的恰好和后面隔一个）还能多拿一个三角形，贪心即可。

时间复杂度 $O(X\log X)$，空间复杂度 $O(X)$。

T2 P9737 [COCI 2022/2023 #2] Lampice

胡言乱语：看到这个题我就不会做，不会做我就想到骗分，骗分我就想到不可以总司令和星战，星战我就想到和哈希。

但是想到和哈希没有注意到特殊的 $n,m$ 范围不会统计也是神人了。

题解

和哈希，对每种的一个点赋随机值 $v$，另一种赋 $-v$，那么等价于求矩形和为 $0$ 的数量。

枚举矩形在 $x$ 轴的左右边界 $L,R$，转换为类似传奇题目鸡蛋的一维问题。

时间复杂度 $O(n^{2}m)$，空间复杂度 $O(nm)$。

T3 P7830 [CCO 2021] Through Another Maze Darkly

题解

当一个节点 $u$ 第一次指向它的父亲 $\mathrm{fa}$ 逃离出 $u$ 的子树后，再次进入 $u$ 时显然能遍历到 $u$ 的所有儿子（除 $1$ 外）。

因此，经过若干次操作后，每个节点都能遍历到自己的所有儿子，答案进入循环。

考虑先求出最后循环的，发现其实就是欧拉序，定义 $u$ 最初指向的儿子到指向父亲之间的儿子叫左儿子，指向父亲之后的儿子到最初的儿子之前的叫右儿子。那么欧拉序里的顺序就是 $u\to$ 右儿子 $\to$ 左儿子 $\to u$。

定义已经从 $u$ 逃离过的点叫好点，没有从 $u$ 逃离过的点叫坏点。那么多次从 $1$ 开始遍历，每次解决一定量的坏点。对于一个坏点 $u$，按照遍历逻辑我们需要让他跳到“左儿子”这一块的第一个，接着让他去寻找欧拉序上下一个坏点，对于如何寻找，使用并查集向右连接（除了坏点）即可。

事实上，在“右儿子”和“左儿子”的欧拉序中，还会出现若干个 $u$，但按照遍历逻辑，只有第一个需要做坏点的特殊处理（跳到左儿子的第一个点）。

对于两个坏点间的欧拉序，这些点都是好点，说明我们会遍历完这一段欧拉序，所以对于这一段时间内的询问可以直接解决。

显然每个坏点只会被特殊遍历一次，其他都是并查集，所以时间复杂度 $O(n\alpha (n)+q\log q)$，空间复杂度 $O(n)$。

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

请勿外放，谨防社死。希格雯：你不可爱！

题解

对于一个合法的区间 $[l,r]$，我们肯定会贪心的让这个区间里的 $C_i=B_i$，区间外的 $C_i=A_i$，那么合法就有以下几个条件。

• $\sum _{i\in [l,r]}{B}_i\ge A$ 的最大子段和，否则不符合题意。
• $\mathrm{\forall }x,\sum _{i\in [x,l)}{A}_i\le 0$，否则区间可以向左拓展。
• $\mathrm{\forall }x,\sum _{i\in (r,x]}{A}_i\le 0$，否则区间可以向右拓展。
• $\mathrm{\forall }x\in [l,r],\sum _{i\in [l,x]}{B}_i\le \sum _{i\in [l,r]}{B}_i$，否则区间可以缩小右边界达到更大的子段和。
• $\mathrm{\forall }x\in [l,r],\sum _{i\in [x,r]}{B}_i\le \sum _{i\in [l,r]}{B}_i$，否则区间可以缩小左边界达到更大的子段和。

第一，二，三个条件可以轻松的 $O(n)$ 预处理，$O(1)$ 对一个位置做出判断。

记 $B$ 的前缀和数组为 $\mathrm{sb}$，那么第四个条件相当于 ${\mathrm{sb}}_r$ 是 $[l,r]$ 中的 $\mathrm{sb}$ 最大值，对于每个 $r$，用单调栈很好找出来合法的最左的 $l$，记作 $L_r$。

第五个条件相当于 ${\mathrm{sb}}_{l-1}$ 是 $[l-1,r-1]$ 中的 $\mathrm{sb}$ 最小值。

考虑对 $r$ 做扫描线，每次使用单调栈维护所有满足条件五的 $l$。使用一棵线段树维护同时满足条件二和条件三的 $l$ 的个数。在满足条件五的之中，满足 条件一 的 $l^{\prime }$ 一定是 $[1,l]$ 中的一段前缀 $l^{\prime }\in [1,x]$。那么 $[L_r,x]$ 就是对于 $r$ 所有合法 $l$ 的位置，形似 $[[l_1,r_1],r]$ 的询问已经可以做了。

把询问按 $r$ 进行差分，转换为求 $[[l_1,r_1],[1,r_2]]-[[l_1,r_1],[1,l_2-1]]$ 的答案，那么只需要维护一个历史版本和即可。

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

10/4

T1 AT_abc304_f [ABC304F] Shift Table

题解

枚举循环节的长度 $p$，那么循环节中有 $x$ 天可以自由出勤，这个循环节的答案就是 $2^x$，发现其中包含了循环节长度包含了循环节为 $d$ 满足 $d\mid p$ 的答案，简单容斥即可。

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

T2 P3590 [POI 2015 R2] 三座塔 Three towers

题解

考虑只有两种字母时的做法（虽然答案就是 $n-1/n$）。设 $a_i,b_i$ 分别表示两种字母的计数前缀和，那么就相当于对于每个 $i$，找到最小的 $j$ 满足 $a_i-a_j\ne b_i-b_j$，即 $a_i-b_i\ne a_j-b_j$，记 $A_i=a_i-b_i$。那么假设 $j$ 是最小的满足 $A_1\ne A_j$ 的，那么 $A_i$ 要找的要么是 $1$ 要么是 $j$，取决于 $A_i$ 是否等于 $A_1$。所以两个点就可以覆盖一条直线。

考虑拓展到二维的情况，最优的情况下选 $1\sim 3$ 三个点 $(A_i,B_i)$ 完全不同，就可以覆盖整个平面，但是最坏的情况下，可能前两个点在同一条平行于坐标轴的直线上，这样子画图可知剩下这条直线还没覆盖。再使用两个点覆盖另一条垂直的直线（实际上似乎一个点即可，但是为了方便处理），就可以只剩下这两条直线的交点未被覆盖，所以再用这两条直线外的一个点覆盖即可。

综上，可以得到：

• 最多有 $5$ 个点覆盖。
• $A_i,B_i$ 均相同的点只出现一次。
• $A_i$ 相同的点只出现两次。
• $B_i$ 相同的点只出现两次。

接着拓展到三维的情况，同理使用 $15$ 个点覆盖到只剩原点，再额外用一个选定的三个坐标轴的面以外的点覆盖，共 $16$ 个点。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

10/5

T1 P9975 [USACO23DEC] Cowntact Tracing 2 B

题解

找到最小的 1 连通块即可知道最多经过了多少天，然后贪心即可。

注意这两步都要特殊处理两端的块。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

T2 P7831 [CCO 2021] Travelling Merchant

题解

当图中不存在出度为 $0$ 的点时，显然所有点只要有足够的钱，都可以无限地走下去。那对于当前图中的 $r$ 最大边 $(u,v,r,p)$，只要在 $u$ 拥有的钱超过 $r$，他就可以无限地走下去，这条边可以删去。

当图中存在出度为 $0$ 的点时，说明他的答案已经确定，那么类似拓扑排序，可以确定更多现在或即将出度为 $0$ 的点的答案。

不断重复这两个过程即可。

时间复杂度 $O(n+m\log m)$，空间复杂度 $O(n+m)$。

T3 P10067 [CCO 2023] Real Mountains

容易贪心得到山峰最终形态，从小到大抬升一定最优，具体考虑怎么样抬升。

对于同种数，先抬其左边一格，再抬其右边一格，最终抬起中间的绿色。

使用一个堆维护当前最低的格子的左右边界，然后用线段树维护区间大于这个值的最小值，模拟这个抬升的过程即可。

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

10/7

T1

题目

给定 $n$ 根直的木棍，从中选出 $6$ 根木棍，满足能用这 $6$ 根木棍拼出一个正方形。求方案数。$1\le n\le 5\times {10}^3,1\le V\le {10}^7$。

题解

正方形每条边的木棍数情况有两种：$1-1-2-2$ 和 $1-1-1-3$。

先考虑 $1-1-2_1-2_2$ 的情况，枚举 $1$ 的边长 $a$，然后枚举从小到大 $2_1$ 的第一条边边长 $x$，双指针得到 $2_1$ 的另一条边边长 $y$，假设 $<x,>y$ 的边组成 $a$ 的方案有 $\mathrm{cnt}$ 种，边长为 $x$ 的有 $c_x$ 个。我们强制 $2_2$ 的短边小于等于 $2_1$ 的短边。

当 $x=y$ 时，判断 $2_2$ 的两条边构成是否与 $2_1$ 构成一致。若一致，方案数为 $(\genfrac{}{}{0ex}{}{c_a}{2})(\genfrac{}{}{0ex}{}{c_x}{4})$；否则方案数为 $(\genfrac{}{}{0ex}{}{c_a}{2})(\genfrac{}{}{0ex}{}{c_x}{2})\times \mathrm{cnt}$。

当 $x\ne y$ 时，若一致，方案数为 $(\genfrac{}{}{0ex}{}{c_a}{2})(\genfrac{}{}{0ex}{}{c_x}{2})(\genfrac{}{}{0ex}{}{c_y}{2})$；否则方案数为 $(\genfrac{}{}{0ex}{}{c_a}{2})\times c_x\times c_y\times \mathrm{cnt}$。

接着考虑 $1-1-1-3$ 的情况。

从小到大枚举 $3$ 中最长的边 $a$，然后设 $g_i$ 表示两个数和为 $i$ 的方案数。再从小到达枚举 $1$ 的边长 $b$，答案就是 $g_{b-a}$，然后再用 $a$ 更新 $g$ 即可。

事实上，只有 $g$ 的空间需要 $O(V)$，其他的时间空间都可以 $O(n)$，所以时间复杂度 $O(n^2)$，空间复杂度 $O(V)$。

T2 P10299 [CCC 2024 S5] Chocolate Bar Partition

チョコミントよりもあ～な～た～

题解

显然每个块的平均值等于全局平均值，让每个数减去全局平均值，等价于要求每个块和为 $0$。

设 $f_{0/1,i}$ 表示考虑前 $i$ 列，现在考虑第 $0/1$ 行作为结尾的最多段数。设 $s_{0/1,i}$ 表示这一行前 $i$ 列的前缀和。

• 仅限在本行的一段连通块。

判定条件：$s_{0,i}-s_{0,j}=0\Rightarrow s_{0,i}=s_{0,j}$

转移：$f_{0,i}\leftarrow f_{0,j}+1$。

• 两行都在第 $i$ 列断开的连通块。

显然，如果这么分是合法的，前面白色部分也必然需要合法的，即 $s_{0,j}+s_{1,k}=0$，那么若绿色部分合法，就相当于这一整段前缀和为 $0$，因此判定条件是 $s_{0,i}+s_{1,i}=0$。

转移：$f_{0,i}\leftarrow max(f_{0,i},f_{1,i})+1$。

• 在本行和延续一段，然后转入下一行延续一段的连通块。

同上面，判定条件是 $s_{0,i}+s_{1,j}=0\Rightarrow s_{0,i}=-s_{1,j}$。

然后考虑转移，由于这样划分出绿色的左边界是贪心得到的，因此我们要找 $j$ 左侧最后一个分界点的答案最大值，因此可以直接 $f_{0,j}\leftarrow max(f_{0,j-1},f_{1,j-1})$ 找到这个最大值。转移是 $f_{0,i}\leftarrow f_{1,j}$。

使用 map 维护这个 DP 即可，具体的，设 $m{p}_{0,x}$ 表示 $s_{0,i}=x$ 时 $f_{0,i}$ 的最大值。

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

10/8

T1 AT_arc132_d [ARC132D] Between Two Binary Strings

题解

显然，$s_3$ 是 $s_1\to s_2$ 途中的一个状态。

那么考虑每个 1 都有一个左右活动的区间，尽量把 1 凑在一起分数更高，所以先从右往左贪心，让 1 在尽量靠一起的前提下往左靠，再从左往右贪心做一次。但是注意到如果 1 占领了两端，答案可能会更优，所以再贪心一次：让最左边可以靠左的 1 尽量贴着左边界，其他全部靠右。

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

T2 P6294 [eJOI 2017] 游戏

题解

开局把所有数从大到小排序。对于每个询问，不断从大到小找到第一个目前可以取的数，再和当前新加入的数比较，如果新加入的数比当前找到的数要大，那就说明可以直接取新加入的，否则新加入的在后面一定会遍历到，继续往后遍历。

时间复杂度 $O(n\log n+nk)$，空间复杂度 $O(n)$。

T3 AT_arc119_f [ARC119F] AtCoder Express 3

细节细节。

题解

设 $f_{i,j,k}$ 表示考虑完前 $i$ 个点，这其中最后一个 A 点距离为 $j$，B 点距离为 $k$。

若下一个是 A 点，

• 若这一步是 A 点，直接转移：$f_{i+1,j+1,k}\leftarrow f_{i,j,k}$。
• 若这一步是 B 点，那么下一个 A 可以从这个 B 跳过来，花费 $k+1$，也可以上一个 A 跳过来，花费 $j+1$。这个 B 可以从下一个 A 跳过来，花费 $j+2$：$f_{i+1,min(j+1,k+1),min(k,j+2)}\leftarrow f_{i,j,k}$。

下一个是 B 点同理。

观察转移，$j>k+2$ 时对后续的影响与 $j=k+2$ 相同，$k>j+2$ 时同理，因此有用的 $j,k$ 状态只有 $O(5n)$ 种。

时间复杂度 $O(n^2)$，空间复杂度滚动数组一下可以 $O(n)$。

T4 P9058 [Ynoi2004] rpmtdq

板子支配点对，后面补笔记。

10/9

T1 AT_arc170_b [ARC170B] Arithmetic Progression Subsequence

题解

容易发现，排序去重后，计 $i$ 出现了 $c_i$ 次，合法的序列的 $c$ 就这两种情况：

• $\dots 4\dots$。
• $\dots 2(3)-1-1-\cdots -1-2(3)\dots$。

证明第一条：同一个位置上有 $4$ 个请求，让他们分别请求 $00/01/10/11$ 即可。

证明第二条：第一个位置上有 $2$ 个请求，可以让他们请求 $00/10$，这样子第二个位置只要请求 $1\ast$ 即可，假设让他请求 $10$，那么第三个位置又只需要请求 $1\ast$ 即可。最终到达最后一个位置，让他同时请求 $10/11$，合法。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

T2 CF2006C Eri and Expanded Sets

题解

思考一个集合 $S$ 最后变为的 $S^{\prime }$ 长什么样。

首先，若 $S^{\prime }$ 中两个数的差为偶数，并且这两个数的平均数不存在，那么可以继续加数，因此 $S^{\prime }$ 最终相邻两个数差为奇数。

然后，$S^{\prime }$ 一定是等差数列，若不是，则存在差 $d_1,d_2$，这两个数与 $d_1+d_2$ 必然有一者是偶数。

最后，$S^{\prime }$ 相邻两数的差是 $S$ 中两数的差 $g=gcd$ 的因数。$S$ 中的每个数均可以表示为 $kg+b$，令所有数减去 $b$ 对答案没有影响，那么显然一堆 $kg$ 只能拓展到另一堆 $k^{\prime }(\frac{g}{2^{\ast }})$。

若 $S^{\prime }$ 合法，那么其两数间的差等于 $1$。

T3 []