KDOI Tournament 2026 Advanced Round 1 题解

A - 盲盒找零（change）

支付 $10$ 元的顾客显然全部接待。先不考虑 $50$ 元，将每名能接待的 $20$ 元顾客与前面一名提供找零的 $10$ 元顾客匹配。

这样做不会损失最优解。若某名 $20$ 元顾客所需的 $10$ 元纸币被用来给 $50$ 元顾客找零，可以放弃后者，改为接待前者：人数不变，放弃后者退回的 $40$ 元零钱还足以保留原来的后续安排。若这张纸币匹配给了另一名 $20$ 元顾客，则沿匹配关系调整。因此，可以先保证接待尽可能多的 $20$ 元顾客。

有一个细节：每次要匹配最晚出现的、尚未匹配的 $10$ 元顾客。用较晚的纸币找零，能把较早的纸币留给中间的 $50$ 元顾客，不会使任何前缀的可用零钱变少。用栈维护即可：遇到 $10$ 元就压栈，遇到 $20$ 元且栈非空就弹出栈顶，并标记这两个顾客。

将匹配中的 $10$ 元纸币预留，再扫一遍序列。设可用零钱总额为 $s$：遇到未匹配的 $10$ 元顾客，令 $s\gets s+10$；遇到匹配成功的 $20$ 元顾客，令 $s\gets s+20$，他的找零已经预留；遇到 $50$ 元顾客，若 $s\ge40$ 就接待，并令 $s\gets s-40$。

剩下的零钱只有 $10,20$ 元两种面额，总额达到 $40$ 元就一定能找零。而 $50$ 元顾客的代价都相同，能接待时就接待即可。注意收到的 $50$ 元纸币不能用于后面的找零，不计入 $s$。

时间、空间复杂度均为 $\mathcal{O}(n)$。

B - 清空场地（clear）

将摊位看成点，器材看成边。记 $C_u=\sum_{e\ni u}c_e$ 为点 $u$ 的退款金额，$D_u$ 为其尚未删除的邻边的运费之和。$C_u$ 始终不变，$D_u$ 随删边而减小。

在下一次退款之前，必须付清某个点的全部剩余运费，所以至少需要 $\min D_u$ 元。反过来，有这么多钱时，就可以删掉对应点的全部邻边，领取退款。

由于 $c_e\ge d_e$，始终有 $C_u\ge D_u$。因此，只要一个点当前能处理，就可以先处理它：处理完后现金不会减少，其他点的剩余运费也不会增加。若连最小的 $D_u$ 都付不起，则无论怎样安排，都拿不到下一笔退款。

于是每次取 $D_u$ 最小的点即可。设已经处理的部分带来的净收益为 $s$，答案为 $\mathrm{ans}$，初始均为 $0$。取出点 $u$ 时，令 $\mathrm{ans}\gets\max(\mathrm{ans},D_u-s)$，再令 $s\gets s+C_u-D_u$。删除它的邻边，并更新相邻点的 $D_v$。

这里更新答案只是计算缺口，不是真的中途追加资金；一开始准备最终的 $\mathrm{ans}$ 元即可。邻点若变成孤立点，$D_v=0$，下一步会优先取出并结算退款。

用 std::set 维护最小值，时间复杂度 $\mathcal{O}((n+m)\log n)$，空间复杂度 $\mathcal{O}(n+m)$。金额之和需要使用 64 位整数。

C - 生成排列（perm）

将题面给定的排列记为 $q$，设排列 $r$ 满足 $r_{p_i}=i$（即 $r_i$ 表示交换 $i$ 与 $i+1$ 的时间），下标按环形理解。

倒序考虑操作过程，观察最终的位置 $i$。设 $r_i>r_{i-1}$，撤销最后一次移动，$q_i$ 回到 $i+1$：

• 如果 $r_{i+1}>r_i$，则位置 $i+1$ 不会再次被交换，即这个数初始就在 $i+1$，所以 $q_i=i+1$；
• 如果 $r_{i+1}<r_i$，则 $q_i$ 将持续向右移动，直到遇到某个 $r_{j+1}>r_j$ 后停止。

这启发我们将位置分类，一种是 $r_i>r_{i-1}$，称为 1 类，另一种是 $r_i<r_{i-1}$，称为 2 类。根据上面的过程，可以得到结论：最终的排列为 1 类位置向前 shift 一次，2 类位置向后 shift 一次的结果。也就是说，按编号递增排列同类位置，1 类位置的 $q_i$ 是同类中的下一个编号，2 类则是上一个编号，两端循环相接。

因此，首先将输入的排列分解为环，检查环的个数是否恰好为 $2$，并检验是否满足 1 类、2 类的性质。枚举两个环的两种分类方式，将合法情况的答案相加。

（注意：$n\le4$ 时交换 1 类/2 类可能仍然合法，不能只计算一种。$n=1$ 单独处理，答案为 $1$。）

接下来，原问题转化为：给定 $s_i\in\{0,1\}$，若 $s_i=0$，则 $r_i>r_{i-1}$；否则 $r_i<r_{i-1}$，计算满足条件的排列个数。

枚举 $1$ 的位置 $k$，要求 $s_k=1,s_{k+1}=0$。删去它，按 $k+1,k+2,\ldots,k-1$ 的顺序断环为链，就可以进行常规二维 dp。

设 $f_{i,j}$ 表示只考虑相对大小时，链上前 $i$ 个位置中，最后一个数排名为 $j$ 的方案数，初始 $f_{1,1}=1$。若前一个数小于当前数，则 $f_{i,j}=\sum_{t<j}f_{i-1,t}$；否则 $f_{i,j}=\sum_{t\ge j}f_{i-1,t}$。用前缀和优化，每个 $k$ 的计算为 $\mathcal{O}(n^2)$，将最后一层求和即可。

总复杂度为 $\mathcal{O}(n^3)$，滚动数组的空间复杂度为 $\mathcal{O}(n)$。计数对 $998244353$ 取模。

D - 环线规划（route）

树上不重复经过城市的路线只能是简单路径。所以每个要求 $(x,y)$，就是要让 $x\to y$ 的简单路径在某个方向的环线上连续出现。

对每个点 $v$，将它的邻点排成一个循环顺序：从 $a$ 进入 $v$ 后，从 $a$ 的后继离开。这就确定了每条有向边的后继。在树上，任意一组局部循环顺序都会得到一条完整的环游，删去叶子归纳即可：加回叶子只会在原环游中插入一次往返。反过来，合法环游也会在每个点给出一个这样的循环顺序。

如果要求路径经过 $a\to v\to b$，就需要 $a,b$ 在 $v$ 的循环顺序中相邻。对每个度数至少为 $3$ 的点 $v$ 建图 $H_v$，以它的邻点为点，将这些相邻要求连成无向边，重边去重。度数为 $2$ 的点只有一种局部循环顺序，两种通过方向都允许，不必处理。

$H_v$ 中每个点的度数不能超过 $2$；如果出现环，这个环必须包含 $v$ 的全部邻点，否则无法接入剩余的点。这两个条件也是充分的：没有环时，将各条链和孤立点作为若干块，拼成一个环；有环时直接使用它。

不过，只检查局部相邻是不够的。一条要求路径必须乘坐同一个方向的列车，不能在不同城市分别选择方向。

给 $H_v$ 中每个包含边的块任选一个基准方向，用变量 $z$ 表示是否翻转。给第 $i$ 条要求设置变量 $t_i$，表示从 $x_i$ 到 $y_i$ 乘坐正向还是反向列车。若某个转弯的基准方向与 $x_i\to y_i$ 相同，记 $b=0$，否则 $b=1$，则有 $z\oplus t_i=b$。这些异或等式用带权并查集维护，出现矛盾就无解。

剩下的问题是如何避免逐条展开路径。直接处理所有转弯会达到 $\mathcal{O}(nq)$。

将原树定根，记 $l=\operatorname{lca}(x,y)$。$l$ 处的“儿子—儿子”转弯每条要求至多一个，直接处理。其余都是祖先链上的“儿子—当前点—父亲”转弯，由那个儿子唯一确定，全树只有 $\mathcal{O}(n)$ 种。先用树上差分标记哪些转弯出现过，保留中间点度数至少为 $3$ 的那些，再加入对应的 $H_v$。这样建图只需处理 $\mathcal{O}(n+q)$ 条候选边。

对于每个有效的祖先链转弯，另设变量 $w$：向上转弯属于正向环线时为 $0$，属于反向环线时为 $1$。它与所属块的 $z$ 之间同样是一个异或等式。于是，$x$ 到 $l$ 的半链中，所有 $w$ 都应等于 $t_i$；$l$ 到 $y$ 的半链中，所有 $w$ 都应等于 $t_i\oplus1$。这里不包含端点和 $l$ 处的转弯，后者仍单独处理。

一段链上的变量相等，只需将相邻的有效转弯两两合并，再将其中一个与 $t_i$ 相连。预处理每个有效转弯上方最近的有效转弯，用另一个并查集跳过已经合并的相邻关系。每个关系最多处理一次，每段半链只额外连一个变量；没有有效转弯的半链不产生约束。

没有矛盾时，任意确定带权并查集各个根的取值，得到各块的方向。将它们拼成局部循环顺序，沿有向边的后继走一圈，就得到长度为 $2n-1$ 的答案。

使用倍增求 LCA，时间复杂度为 $\mathcal{O}((n+q)\log n)$，空间复杂度为 $\mathcal{O}(n\log n+q)$。