task19

[TOC]

1. 北大集训 2021 - 末日魔法少女计划 [E/K]

题面

给定 ，要求构造下标为 的 01 矩阵 ，使得：

• 对于所有 ，
• 对于任意满足 的位置，存在 满足
• 对于所有 ，都有

设 为 的数量，你需要使 ，其中 为题面中给定的常量

题解

Sol

首先观察一下题面：可以发现这是一个数据结构问题。即初始有信息 ，接下来你需要进行一些信息的合并，你可以将信息 和 合并为信息 ，你想要在预处理尽可能少的信息的情况下能够在不超过 个信息一起合并的情况下回答所有询问

可以使用猫树。

可以想到使用 sqrt tree，即分 个块，每个块预处理前后缀信息，然后处理所有整块区间的信息

那么具体地，按照如下方式进行问题的划分：

• 枚举一个块数 ，然后平均切块，每个块内部的询问递归进去继续做，最后在外面做一个长为 ，次数 的问题

直接写 dp 即可获得 ~80pts。

优化：

• 注意到开头和结尾的两个块分别只用处理前缀和后缀，并且做整块合并的时候我们实际上只用做长为 的问题，而开头结尾和中间的块的贡献不一样，因此我们可以将它们放长一点，在 dp 转移中可以加上这一点
• 一个长为 的块预处理了前后缀，相当于我们只需要递归中间长为 的块，只预处理其中一个相当于只需要递归 的块

加上这两个优化即可通过

---

2. QOJ7510 - Independent Set [E] ⭐

题面

有一张未知的 个点 条边的图，初始你只知道 ，图中可能有重边自环

每次你可以给出一个顶点序列 （可以有重复元素），交互库会从 到 扫描，依次执行如下过程：

• 维护一个集合 ，初始为空，以及一个长为 的 序列，初始所有
• 扫到 时， 会被更新为：一端是 ，另一端的端点属于 的边的数量
• 如果 ，那么 会被加入

最后你会得到 序列

你需要求出所有边，你可以询问的 上限为

题解

Sol

首先我们可以询问 次把所有自环全都问出来。

然后看起来没有什么头绪，所以我们先把所有点以任意顺序一起问一遍，这时我们可以拿出来所有 的点，这些点会形成一个独立集

因此我们产生一个想法：如果能求出这个独立集和剩下的点之间的所有连边，我们就可以把这个独立集扔掉，然后对剩下的部分继续做

由于不在独立集内的点，向独立集内的点至少有一条出边，所以我们的询问复杂度是有保障的

但是我们真正分治的时候会发现问题：如果我们要询问独立集 内的点到集合 内的点有无连边，这时若 内某个点没有连边，则 会被加入独立集，干扰我们后面的信息

因此我们可以进行调整：我们一开始先不断问独立集，得到独立集序列

然后倒序处理：每次询问出 到 内所有点的边，询问的时候，由于后面的边都已知，所以我们可以手动消除其影响

最后询问次数为

---

3. QOJ1884 - Mission Impossible: Grand Theft Auto [K] ✨

题面

给定一棵 个点的树，有一个人在某个点上，每一天你可以选定一条链 ，如果人在这条链上，那么他就会被抓住，否则这个人可以选择移动到任意相邻的点上，或者保持不动（可以移动到 链上）

设树上一共有 个叶子，你需要在 天内抓到这个人。

题解

Sol

注意到我们覆盖所有叶子需要 次操作，所以这个界很紧。

手玩一下这个操作，可以发现我们操作一条链 之后，等效于会把 出发的 度链清除，和 出发的 度链清楚，并且我们下一次操作需要继续经过向外连的位置，否则这个叶子会再被染回来

也就是说我们有一个大致的直觉是：操作的端点大概是 dfn 序上比较接近的点

再玩一玩，可以发现按 dfn 序排序为 后， 是一个看起来很有道理的构造，具体地，如果我们随便定一个根，所有 为偶数，且恰好使用 次操作的构造都可以通过某种 dfs 方式转化成这个构造

但是这种构造方式有一种情况下会爆掉：当存在一条边使得我们某个时刻遍历完了边的一个子树，然后另一个子树还没有遍历，这时候我们就会凭空多出一个叶子，称这种边为坏边

设我们按 dfn 序操作的为 （下标模 ）

对于每一条边，设它子树内的 dfn 序为 ，如果 为偶数，那么当 时它就会成为坏边，对于子树外同理

那么我们分 的奇偶性讨论：

• 为偶数，那么缩掉二度点之后最多有 条边，而这 条边中，叶子边都不会成为坏边，所以最多有 条可能成为坏边的边，因此一定存在一个 只会有不超过一条坏边，我们选取这个 ，然后操作到坏边的时候用额外的一次操作把新产生的叶子干掉，再继续操作

• 为奇数，那么每条边最多有一边的子树是偶数，因此每条边最多成为一次坏边，也就是说一定存在一个 只会有不超过一条坏边，我们选取这个

  可以发现对于任意 ，dfn 序为 的叶子的父边一定对 是坏边，所以我们按照这个方式构造，最后形成的情况就是只剩 一个叶子，用一次操作把它干掉即可

复杂度

---

4. QOJ1875 - Nein [E] ⭐

题面

给定 ，求第 小的满足 的十进制表示中不含 的正整数

题解

Flamire 做法

Sol

做麻烦了。

令 ，通过之后实测可以发现 ，求第 大可以转化为 次确定一个前缀，然后计数满足条件的 数量，因此我们下面解决这个问题

我们对 不含 计数。

这个问题不是很好处理，考虑对 的取值分类：

• 当 比较小的时候，我们可以直接从高到低填，只用保留 最近 位的值，以及上一位是否借位，这部分在所有前缀之间可以共享信息，总复杂度与 相关
• 当 比较大的时候，我们可以先填 ，然后再填 ，这样一直填下去，这样我们填的时候只需要记录第一组的位的进位，以及上一组的进位情况，总复杂度与 相关

取 的时候运行第一种做法， 的时候运行第二种做法即可通过

题解做法

Sol

令 ，我们计数有多少 满足 ，且 中不含

判断 可以每 位分一段，然后所有段加在一起的结果必须是 的倍数

这个就好办一些了，由于答案不会太大，所以我们设答案有 个段

确定一段前缀之后，相当于我们后面有 位待确定，并且这些位需要模 余某个可以算出来的数

而注意到一共 个段，这些段的和不超过 ，因此最后和只可能为

枚举最后的和是哪个，然后进行数位 dp 算出方案数，可以提前预处理出来 个 内的数和为 的方案数，然后 调用

这样我们数位 dp 的复杂度是 的，而我们总计需要进行 次这个东西，因此最后总复杂度是 ，但是根本跑不满，可以轻松通过。

---

5. QOJ1874 - Goldberg Machine 2 [K] ✨

题面

有一类机器：这类机器形如一个 的由 >v. 三种字符组成的字符矩阵，保证 不为 .

接下来，你可以在 处重复放入小球，放入小球之后，小球会不断根据当前格子是 > 还是 v，决定是向右走还是向下走，在小球离开这个格子之后，这个格子的方向会反转，即从 > 变 v，v 变 >

小球会一直运动直到走出矩阵或者走到某个 . 为止

给定两个机器 ，满足它们所有 . 的位置相同，现在你需要回答：最少往 中放入总计多少个小球，才能使它们变得完全一样，如果不可能则输出

次修改，每次修改翻转 或 中的一个箭头，修改在不同操作之间保留，所有修改之前以及每次修改之后你需要输出问题的答案

题解

暴力做法

Sol

解决单次问题。

显然状态的历程是一个环，因此我们实际要判断的是 和 是否在一个环上，若是则求出 到 需要的步数 ，对 取

设我们在 的开头输入了 个小球，那么根据 的奇偶性我们可以得到会有 个小球走向 指向的方向，有 个小球走向另一个方向

而给定 ，相当于我们知道了每个位置需要被经过次数的奇偶性

我们逐位从低到高确定 的每个二进制位 ：

• 考虑第 位时，我们进行预处理，初始 上放 个 ，当 个数为偶数的时候，我们两边一定可以当成平均分 ，用更低的位去处理上下取整的问题，但当 个数为奇数时，我们就需要知道 的取值，才能知道奇偶性，因此我们不知道分出去的方向是什么，我们把这后面的所有结果设为无效

• 此时，我们只需要找到任意一个有效拥有奇数个 的格子 ，即可通过这个格子此时的取值推断出 是什么

• 但是如果 ，我们还需要更新 ，即让 ，如果将所有格子重跑一遍复杂度太高

  观察到我们只关心后续考虑的格子的取值，没必要更新之前的格子，而我们实际上需要改变的就是 的所有边，给这些边补上 的权值，其余的依然满足 可以从 推过来，而这些边恰好是割掉了一个包含 的连通块向外的所有边

  或者说，我们可以按照一个格子最高的出现奇数次的位分类，每一类内部我们只需要在考虑完第 位后加一下值，然后递推一下，即可保证后续的值都正确

总复杂度 ，无法通过

正解做法

Sol

对这种操作的题目，我们可以考虑能不能找一个特征值，使得这个特征值在小球移动的时候不会改变，并且我们希望这个特征值最好是加性的，这样我们每放进去一个球就是给特征值加上一个定值

如果我们当前局面为 ，小球在 ，并且每一个箭头是否是 > 用 表示，那么我们令特征值为：

$$\Delta=B(c)+\sum_iH_S(i)A(i)$$

其中 为我们合理选定的值，只与格子有关，与 具体箭头的指向无关

那么根据小球的两种移动方式，我们可以得到：

可以解出

我们设每个 . 和出界的位置 的 值是一个变量 ，那么我们就可以递推出所有的 ，它们都是 的线性组合，并且显然系数的分母都是 的次幂

而小球出界之后会让特征值 ，因此我们只关心特征值 的结果，这样放一个小球之后，在小球移动过程中特征值都不会改变

我们可以发现：对于两个没有小球的局面， 当且仅当 ，这里 指它们箭头方向完全相同

若 且 ，我们找到字典序最小的箭头方向不同的位置 ，再找到它右面第一个没有箭头的位置 ， 中 的系数为 ，而字典序大于 的格子 值中 的系数都是 的倍数，因此 的区别必定会导致

那么接下来我们就可以注意到一些事情：

• 放一个小球相当于给特征值加上 ，若设 中最大的分母为 ，那么放球的最小周期一定是
• 我们要求的实际上就是一个 使得

对于求 的事情，我们可以任取一个 中分母最大的变量 ，然后用 和 中 的系数进行比对，这样可以解出 的值，再把这个 带入到其它 的系数中检验即可

但是这样复杂度太高了：我们有 个 变量，带着所有变量一起处理过于耗时，会让我们的复杂度变为

因此考虑随机：随机 次，每次随机将一些 设为 ，其余的设为

• 此时 的分母为 的概率至少为 ，因此我们直接取这之中分母最大的作为 即可
• 并且一个不合法的 在这样的计算方式下满足 的概率不超过

我们取 次中任意一个分母最大的，用它解出 的值，然后代入 组中的每一组检验一下，这样我们错误概率是

取 即可通过，复杂度为

---

6. 图灵杯 2025 - 旧事重提 [K] ✨

题面

有 个人比赛，两两比一轮，若分出胜负，则胜者得 分，负者得 分，否则平局双方都获得 分

给定 个人比分的区间 ，你需要进行若干次给 减 ，给 加 的操作，使得存在比赛结果使得第 个人的得分在 之间

次修改，每次修改一个 ，你需要在每次修改后求出，最少需要再进行多少次 操作

题解

Sol

类比兰道定理，我们可以得到一个比分序列 合法的充要条件：

• 将 从小到大排序，，且在 时取等

必要性比较显然，充分性可以通过构造左部 个点，右部 个点的二分图匹配来说明，左部的 点连向右边的点 ，所有左部点 的流量为 ，右部点 的流量为 ，我们即需要这张图有完美匹配，用 Hall 定理可以得到上述式子

那么我们再大胆猜测一下，一个区间序列合法的条件是对于 序列，所有前 小的和都 ，对于 序列，前 大的和都

事实上，这也是正确的。

我们只需要说明：对于所有 且满足上述性质的 序列，若 ，那么我们一定能选择一个 ，让其 之后仍然合法，即可归纳

我们选择最大的 的位置 将其 ，证明这样可行。

重新排列 ，设 ，在保持 升序的情况下，我们使 在值为 的当中排在第一个，这样 之后 仍然有序，不难发现此时的序列一定是前面一些 ，然后一段值为 ，然后一段

由于 ，那么 的段，可以根据 的限制推出其一定 ，因此我们只需要保证 段内， 之后前缀和依然合法

接下来，我们探讨 的前缀和，这个序列需要 。

这个 段内部一定是一段前缀的 ，一段后缀的 ，也就是说这段内的前缀和是一个单峰函数，并且这个单峰函数最右边的纵坐标 ：

• 若 ，那么前缀和一定从这个位置开始下降，直到最后下降到了一个 的位置，因此在这里 不会让后面的前缀和
• 若 ，那么前 个位置的前缀和 ，而由于单峰函数首尾都 ，可以说明整段

那么我们就得到了一种快速算答案的方式，只要找一下 即可，对 也做类似的事情然后相加

接下来，我们考虑快速维护这件事情。

首先我们提出一种新的计算 的方式，其中 递增：

• 将两个序列分别求前缀和得到 ，答案改写为
• 我们任选一个 ，强行将其从 中删除，设删完的序列叫做 ，其前缀和叫做
• 那么由于 递增，我们原来求的答案相当于
• 将 拆开：（舍弃掉出界的项）
• 按照 分类：
• 也就是说，我们可以直接将 中任意一个元素 删除，然后令 ，就可以转化成一个 的下标均为 的问题，一直这样递归下去到 ，答案即为 （注意这里 ，但 可能 ）

我们仔细分析 这步操作的影响：

• 单增，找到 中最后一个 的数 ，以及 中第一个 的数
• 若 不存在，那么我们就是直接删除
• 若 都存在，那么手模可以发现我们的操作相当于将 都删除，并在原来的位置插入一个
• 若 不存在，那么我们就是让 加上 ，然后将 删除

因此这个修改也是可以优美地进行的。

现在回到原问题，我们要支持 的单点修改，我们对值使用线段树分治，每次到一个节点的时候，用上述过程把这个节点上的 全都删除

可以发现，这样进入一个线段树节点时， 序列的长度就是所有区间修改的时候，经过这个节点的次数，因此 的总长是 的

在同一个节点上我们可以线性更新 ，使用指针扫一遍即可，最后递归到每个叶子答案就是

总复杂度

---

7. QOJ6545 - Connect the Dots [E] ⭐

题面

给定一个长为 的数列 ，你可以连一些边：边的左右端点必须 值不同，并且所有边代表的区间要么不交要么包含

要求输出最多的边数，并给出构造

题解

Sol

首先，可以转成三角剖分，最外圈的边显然能连的都连，并不影响。

随便画一画可以发现这个限制不是很强，具体地，似乎大于等于三种颜色的时候一定可以连满连出 条边

证明：当颜色 的时候，一定存在三个相邻的元素 满足 ，此时如果 只出现一次，我们就可以从 连向其它的所有点，否则我们可以连接 和 ，转化成规模更小的问题

用链表维护上述过程也可以得出颜色数 的构造。

对于颜色数 的情况，可以发现当不存在相邻相等的时候我们分的最碎只能分到环长为 ，无法分成环长为 ，因此这个和相邻相等有一些关系

具体地，设相邻相等的数量为 ，那么我们可以说明，最多可以连 条弦

证明：随便连一条 之间的边，两部分的 之和不变， 之和 ，而我们又额外连了一条边，算出来一共可以连 条弦

这也意味着我们每次选一个 连起来即可，同样可以链表维护，复杂度

---

8. QOJ8086 - Cloyster [E] ⭐

题面

有一个 的矩形 ，保证如下条件：

• 所有 为互不相同的 内的整数
• 对于每个不为最大值的 ，其八连通范围内至少有一个元素大于它

给定 ，你可以对 矩阵进行不超过 次单点查询，查询之后你要求出最大值的位置

题解

Sol

考虑询问一条竖线，找到竖线上面的最大值 ，询问这个最大值左边的三个八连通格子，以及右边的三个八连通格子

如果两边都有比 大的，那么可以得到这并不合法，因为 的格子不连通

因此只有一边比 大，并且一定是八连通格子的 更大的一边，我们进入更大的那一边递归，就将问题转化为了 的问题

但是注意到“每个非最大值周围都有一个更大的格子”，这个性质在递归之后就被破坏了，因此我们需要进行特殊处理：

• 我们额外传进一个外圈上最大的位置 ，并且我们已经知道这个值为

  如果询问的一行最大值 ，那么就取 在的那一边下去递归，否则按照刚才的处理进行

横竖交替分治，我们可以用 次操作将问题规模变为 ，因此最后需要不超过 次操作

---

9. QOJ964 - Excluded Min [K] ✔️

题面

对于一个序列 ，定义其 为：你可以每次选择一个 中元素，满足 这个值在 中出现至少两次，然后将 改为 或 ，重复任意多次之后能达到的最大 mex

给定长为 的序列 ， 次询问，每次给定 ，查询

题解

Sol

水平低下了。

将所有数 ，注意到 值即为，将这个序列的数放到数轴上 的前缀和 ，最大的 满足

这个值没有什么更好的形式，因此我们考虑转变一下思路，对 从大到小扫描线，动态维护所有询问区间的 ，然后如果有 的就找出来把它删掉

但是这样我们扫的时候需要矩阵加，删除元素，查询最大值，这个不是很好做

而注意到 的答案一定大于等于它所有子区间的答案，所以我们可以只保留没有被其它区间包含的区间，这样处理之后，我们需要维护的 都是单调的，因此元素修改就变成了区间加

删除一个元素的时候，我们也可以通过线段树上二分，用 的时间找出接下来应该加入的 个区间

总复杂度

---

10. QOJ2626 - Kilk Not [E]

题面

给定一个长为 的包含 01? 的字符串 ，你需要将其中恰好 个 ? 填成 1，剩下的填成 0，最小化填完的 01 串中最长连续段的长度，并给出构造

题解

Flamire 做法

Sol

考虑二分答案，设我们要求最长连续段 ，可以得到能够使用的 1 的个数是一个区间。

证明：可以用前缀和将所有限制表述为差分约束，1 的个数即为 ，而可以证明差分约束中任意两个变量的差的取值范围是一个区间，因此能够使用的 1 的个数也是一个区间

那么我们只要求出这个最大值最小值就好了。

考虑求最少 1 的个数的一种贪心：

• 如果串中有长为 的连续段，那么两边的字符就已经确定，先不断把所有这样的限制处理掉
• 在这之后，我们从左到右扫，假设当前扫到 ，右端点为 的极长 0 连续段为 ，左端点为 的极长 0 连续段为 ，那么如果 就在这里填 0，否则填 1

构造正确性可以简单分析得出，最小性比较容易感性理解（

最多 1 的个数同理。

那么我们就会求出答案了，接下来考虑构造。

我们固定一个位置 ， 跑最大化 1 的个数， 跑最小化 1 的个数，当 时这个会取到最小的，当 的时候这个会取到最大，而可以分析到当 改变 1 的时候 1 的个数会 或 ，所以直接二分即可

我发现我好像什么都不会证，但是看起来真的很对！！！！

复杂度

题解做法

Sol

把上面的做法去贪心化一下。

首先，二分的时候求最大值最小值可以用 dp，一次转移一个连续段，设 表示以 结尾的连续段是 ，最小的 1 个数

然后根据这个我们可以得出两个串，分别取到最大值和最小值，命名为 和

而构造的时候，我们说明对于所有 1 的个数在区间内的 ，我们一定可以选出一个 使得 的 1 的个数为 ，且 ，当满足这个性质的时候我们不会多出任何连续段

证明：

考虑最后一个 的 1 的个数 的位置，那么一定有

而在这之后，如果 ，那么我们选择 即合法，否则 ，而由于 是最后一个 的位置，所以 也要是 ，因此可以继续这样推下去，得出后面都必须是 ，矛盾。

---

11. QOJ2214 - Link Cut Digraph [E] ✔️

题面

有 个点，初始点之间没有边，接下来会有 次操作，每次加入一条有向边 ，加入之后求此时图中满足 能到达 且 能到达 的点对数

题解

Sol

即为求强连通分量的 之和。

考虑加入一条边相当于合并若干个强连通分量，所以我们可以用并查集维护强连通分量内的点，只要求出所有合并操作即可。

我们进行分治，假设我们现在已经得到了 这些边加入之后缩完的强连通分量图，我们在这个图上再加 区间内的边。我们可以先加入 内的边得到图 ，对图 缩一遍强连通分量

如果一条边的两端被缩在了一起，就说明我们 的过程和这条边无关了，因此我们可以只将这条边传入 的过程（若这条边是 时间加入的则可以不传）

如果一条边的两端没被缩在一起，说明我们 的过程和这条边没有什么关系，因为它的端点连通性没有发生任何改变，因此我们可以只将这条边传入 的过程

可以发现一条边最多会在 次跑强连通分量内被跑到，因此总复杂度为

---

12. QOJ6537 - One, Two, Three [E] ✔️

题面

给定长为 的数组 ，保证 ，你需要从中选出尽可能多的不交的 或 子序列，并给出构造

题解

Sol

我们选一些 的区间，然后让它们去匹配区间内的 。

可以观察一些显然的性质：对于我们选的所有 ，我们一定是让它们的 尽可能靠前， 尽可能靠后，并且当出现 的情况时，交叉匹配一定比包含匹配更优，对于 同理

因此最后我们得到的解应该是，选择两个数 ，前 个 和后 个 匹配，前 个 和后 个 匹配

接下来就是要求这个解能匹配上 ，我们使用 Hall 定理，这是一个区间图，因此根据经典结论，所有需要考虑的 和 一定形如 是一段区间 内的所有点，而 是所有被 完全包含在内的区间

而 内有多少个区间是可以描述出来的，我们即要求如下式子对于所有 成立：

$$\max(0,A-pre1_{l-1}-suf3_{r+1})+\max(0,B-pre3_{l-1}-suf1_{r+1})\le s2_r-s2_{l-1}$$

式子中的 可以拆开，最后的会分别得到 的上界，每一个界都是形如某个值要 的形式，而 的最小值可以容易地算出，因此最后求出一组合法的 值，然后用优先队列贪心构造即可

复杂度

---

13. AGC072E - Flights [] ✔️

题面

给定一个 个点 条边的有向图，边有边权

你一开始在 ，你手里有一些钱。你走一条边需要花费 的钱，然后获得 的 miles。

每个点有一个汇率 ，保证 ，你在第 个点可以用 miles 兑换 的钱，你可以兑换非整数的 miles 或钱。

过程中你不能让钱或 miles 变为负数，请求你最少一开始要有多少钱才能从 到

题解

Sol

考虑确定路径之后，如何合理地兑换 miles 使得需要的钱数最少。

先一直走，走到钱用完为止，那么我们可以访问到路径的一段前缀，那么我们换 miles 也肯定是先在这里面最大的换，一直换直到前面的 miles 全被换完，此时如果还缺钱就接着换后面的最大的，这样一直换到钱够了为止。

那么注意到我们在路径上很多地方，要么没钱，要么没 miles，所以我们可以设计如下两个状态：

• 表示从 出发，一开始没有 miles 的情况下至少需要多少钱才能走到
• 表示从 出发，一开始没有钱的情况下至少需要多少 miles 才能走到

那么考虑走路的过程。

对于 ，假设我们确定了路径，那么我们一定是在 先兑换若干 miles，然后往下走，接着兑换 的 miles，直到遇到一个 更大的点，那么分两种情况：

• 在下一个 更大的点之前，我们先把 的 miles 花完了，那么就可以一开始就将所有 miles 兑掉，转化为 ，转移为
• 在下一个 更大的点之前，我们没用完 的 miles，设这个点为 ，那么我们到达 的时候一定没有钱，所以 ，其中后面的 是因为我们额外获得了 miles

对于 ，类似地做，假设我们确定了路径，一定是走到某一个最小值点 之后，再走一段之后没钱了，依然分两种情况讨论：

• 在 之后下一个 更大的点之前，我们先把 的 miles 花完了，转移为
• 在 之后下一个 更大的点之前，我们没花完 的 miles，设这个点为 ，令 ，那么转移为：
  • 首先我们 获得的 miles 数应该要大于 ，否则转移将无意义
  • 然后我们需要钱数能够支撑我们先到 ，因此需要对 取
  • 我们需要钱数+兑换 miles 能够支撑我们到 ，也就是 ，移项可得
  • 我们需要剩余的 miles 数大于等于 ，即 ，移项可得
  • 也就是说最后的转移是

初始 ，此时我们只有 个状态，而单轮转移是 的，因此运行 bellman-ford 可以得到 做法。

考虑优化。

我们试图能不能把这个更新过程换成 dijkstra。我们发现阻碍我们这么做的原因是因为最小的点可能被更新，具体地，如果最小的点是某个 ，那么可能有其它的更大的 ，更新了 ， 再更新 ，让 变小。

但思考一下可以发现：

• 只有第一种转移会让值变小

• 我们每次更新完全之后，每个时刻最小的 一定不会再被更新了（因为我们显然不会从一个需要 miles 更多的点，绕着绕着需要的 miles 更少了）

相当于，我们把 Dijkstra 看成，对于某个点集 ，每次确定 内值最小的点，然后处理完所有 内的点走一条不经过 内点的路径，再回到 内点，这样的路径的转移，这样依然也是正确的

也就是说，我们每次拿出最小的 ，然后处理完所有 的转移。

相当于我们对 设置初值，跑一遍转移，再贡献回 。而注意到 内部的转移只会让 值变大，因此这部分我们也可以使用 dijkstra。

每一轮外层 dijkstra，我们会先做一次 固定的 的转移（），然后再运行内层 dijkstra（），再贡献回 （）。

最后我们使用形如 dijkstra 套 dijkstra 的算法，可以通过本题。

---

14. QOJ962 - Thanks to MikeMirzayanov [E]

题面

给定一个 的排列 ，你可以执行不超过 次如下操作，将序列排序：

• 将 分为若干连续段 ，然后再将这些段按照 的顺序拼接在一起，得到新的

请构造方案。

题解

Sol

首先，操作可以转化为 ，最后让操作奇偶性对即可。

考虑对于 01 串如何排序，我们不断对 01 连续段进行如下过程：

010101010101
0|10|1|01|0|10|1|01
0|01|1|10|0|01|1|10
001110001110

这样我们把 01 连续段的个数大约除以了

我们分治，每次固定一个 ，将 的排到前面， 的排到后面，这可以视作一个 01 串排序问题，我们可以在 次内解决

排序之后递归到两边分别处理，显然操作可以并行。

因此我们在 次操作内解决了这个问题

---

15. QOJ967 - Rectangle Painting [E]

题面

有一个在左右上无限延伸的正方形网格，最底部的一行方格的 ，初始所有方格均为白色

次操作，每次操作为一下两种中的一种：

• 1 y l r，将 ， 坐标为给定值的所有小方格染黑
• 2 l r，对每个 ，称其与 相连的黑色方格高度为 ，求 ， 的最大值

强制在线。

，坐标范围

题解

Sol

维护白色格子连续段，初始每一行都是一个极长的白色格子连续段。

每次颜色段均摊，删除一个白色连续段再加入一个白色连续段。

询问答案需要我们维护的问题是：维护 个 set，支持在 的 set 加入一个值 ，撤销某次之前的加入操作，以及询问 内每个 set 最小值的最大值

这个可以用线段树套 set 标记永久化维护，复杂度

---

16. QOJ8085 - Bulbasaur [] ✔️

题面

有一个有向图，点排列成 层，每层 个点，第 层第 列的点为 。

这张有向图中所有边形如：从某个 连向 ，保证没有重边

定义 为，以第 列的点为出发点，第 列的点为终止点，能连出的最多的点不交路径数量

求

题解

做法 1

Sol

考虑拆点最大流转最小割。令 表示从第 列出发，其中第 列 集合内的点和源点连通，在保持最小割 的情况下，最右可以延伸到哪一列

转移可以用高维一些东西优化，可以做到 的复杂度

做法 2

Sol

从第 列到第 列的若干不交路径可以用 LGV 引理计算

具体地，我们随机对每条边赋权，然后求出第 列点到第 列点每个点的边权乘积和，这个矩阵的秩即是答案（因为我们随机赋权了，所以路径权值大概率不会被 系数抵消掉，要找一个行列式不为 的最大子式就是秩）

而注意到区间越长秩越小，我们可以枚举秩，然后双指针，时刻维护区间内矩阵的乘积，可以做到总复杂度

做法 3

Sol

考虑拆点网络流。

首先求 。可以证明存在一组流从第一列开始，满足流到第 列及之后的至少有 条，即这些上界是可以同时取到的

证明：考虑先流到第 列，然后再把第 列删了，开始向第 列流，可以发现不会退掉原来已经选的点，以此类推

我们求答案也可以这么求，每次从起点开始搜索增广路，找到延伸到的最靠右的流，然后流过去（类似一个费用流的过程），这样显然也是正确的

对于每次增广，如果我们流到了第 列，那么我们至多会访问 个点，因此我们搜出左端点为 的答案，搜过的总点数是 的

令 ，那么我们现在会求 ，考虑扩展到求

注意我们可以利用原来跑完的残量网络，我们在 的残量网络上删除第一列，继续从第二列开始搜增广路，可以发现我们这样额外搜出来的答案是 ，而单个 是 的，最后加起来抵消之后可以发现我们总答案变化量是 量级的

而 的答案量意味着 次搜到点，直接暴力实现可以做到 ，用压位优化可以做到 ，或者在本题下可以当成

---

17. QOJ6538 - Lonely King [S]

题面

给定一棵 个点的树，边有向且方向为根到叶子。

初始的边都是蓝色的，接下来你每次可以选择树上一条蓝色路径 ，将这些边全部删除并加入一条 的红色边

点有点权 ，你需要操作若干次，最小化 满足 能到达 的 之和

题解

Sol

注意到我们可以忽略路径是蓝色的限制，因为如果路径上有一条红边，我们可以先把这个红边拆成蓝边

而如果最后存在 的边，我们显然可以将其替换为 的边更优，因此最后一定是若干个菊花

为了方便，我们设状态为： 表示 子树内及 到 的边，这棵树的最小值， 表示 子树内的最小值

转移就是 等于所有儿子 的和，然后 从子树中选一个叶子 ，从路径上所有 的和减去所有 的和加 转移过来

转移可以用李超树优化，向上合并的时候可以使用李超树合并或者启发式合并，总复杂度 或

---

18. QOJ2599 - Anti-stress [K] ⭐

题面

给定二维平面上 个黑点以及 个白点，保证这些点不重合，你需要选择一个红点 ，然后将黑点和白点两两匹配，设黑点 和白点 进行了匹配，那么 ，也即该角不为锐角

特殊地，我们认为若 与 或 重合也算合法的情况

要求构造，或者判断无解

题解

Sol

考虑选一个十字，将平面划分为四个象限，然后我们只使用一三象限以及二四象限的配对，那么这个划分合法的条件是：上下点数一样、左右点数一样、一象限黑点数等于三象限白点数

可以发现前两个条件已经限制了我们十字 分别是对应的中位数，而我们还要满足第三个限制

注意到我们还没有使用非水平的十字，令 表示旋转 的角度之后，用中位数求出来的十字，一象限黑点数减三象限白点数

那么注意到 ，而 的变化是连续的（即每次只会变化 ），所以中间一定会有一个零点，那么我们可以通过二分找到一个令 的角度

总复杂度

---

19. QOJ1840 - K-onstruction [E]

题面

给定 ，要求构造一个大小不超过 ，元素都在 之间的可重集合，使得其恰好有 个和为 的子集（包括空集）

题解

做法 1

Sol

这个看起来是一个 量级的大小，所以我们首先考虑一下如何构造这个量级

注意到我们可以给 乘 ，如果原来的集合中负数和为 ，正数和为 ，那么加入 可以起到给 乘 的效果

而再注意到我们可以给 加 ，不妨设 ，那么加入 可以起到给 加 的效果

因此我们就有了一个 的构造。

而可以发现 的过程可以合起来，不妨设 ，那么我们加入 和 可以起到给 乘 加 的效果，注意这里 的情况我们就爆了

但我们可以一开始在集合内加入一个 ，注意到我们 和 的过程都是不改变集合的和的，因此我们就有了一个 的构造。

但注意到我们没必要只限定插入一个 和 ，我们可以插入任意元素是 的倍数的集合，可以得到不同的 的效果

具体地，设 ，那么我们加入一个元素都是 的倍数的集合 ， 表示 中和为 的子集数量， 表示 中和为 的子集数量，加入之后 会变成

那么我们暴力搜索出所有元素个数 ，集合内元素在 内的集合，算出 后用这些集合去在 上跑 dp 即可

接下来考虑我们需要满足 的限制，注意到如果我们当前有一个集合 ，不妨设 ，那么集合之和一定不是 的倍数，而下一次加的数一定都是 的倍数，所以加完之后依然有 ，因此归纳成立，我们只要一开始在集合内加入 即可

算出来最多需要 次

做法 2

Sol

随机 个 内的数，设所有数的和为 ，我们求出其和的分布 ，我们在 上跑背包，争取用 个数凑出

具体地，只要我们负数都 ，所有和为 的集合就至多包含一个负数，我们将 内的 排序，从大到小贪心取，如果取了 个就失败，否则就成功构造

不断随机直到合法即可。

---

20. QOJ14432 - Cyclic Topsort [E] ⭐

题面

给定 个点 条边的有向图，求最长的 序列满足：

• 中元素都在 内且互不相同
• 对于每个 ，满足对于任意一条边 ， 在 中出现过

求最长 序列的长度

题解

Sol

题目所求即为删除一个点，然后最大化能够拓扑排序掉的点的数量

考虑先把一开始就能拓扑排序掉的点删除，然后在剩下的图上做这个问题。

性质：任意两个点，删除之后能带掉的点的集合要么包含要么不交

证明比较显然。

有了这个之后，我们有若干种方法来做这道题：

• 使用启发式合并，每个点维护当前扩展出来的点集向外连边的集合，每次从一个点 开始拓扑排序，排到一个点 时将 点集向外连边的集合与 点集向外连边的集合启发式合并，这样不断进行即可，复杂度 或

• 缩点，每次将一个入度为 的点缩到唯一到它的点上，也需要使用启发式合并，复杂度 或

• 每次随机一个还没有被 ban 掉的起点，然后暴力跑一遍过程，将所有删除的点 ban 掉，之后不再考虑它们作为起点的情况，这样进行就是对的

  本质上是一棵树，每次我们付出 的代价 ban 掉一棵子树，将贡献摊到子树的每一个点上，一个点被贡献的次数就是到根链上前缀最大值数量，因此期望复杂度是 的

---

21. QOJ2210 - Hamilton Path [K] ⭐

题面

给定一张 个点 条边的有向图，你需要求出所有 的排列 ，满足：

• 对于所有 ， 存在当且仅当

具体地，如果总合法排列数 ，那么你需要输出排列数模 的结果，否则，你需要按照排列字典序，输出每个排列的哈希值，哈希函数为：

$$\left(\sum_{i=1}^n p_i10^{n-i}\right)\bmod(10^9+7)$$

题解

Sol

首先进行一些浅显的观察，我们可以发现一种暴力的方式是从一个起点开始，如果这个起点有解，那么走的过程一定都是唯一的，因此 是容易的

注意到如果存在解，那么对图的结构限制很强。那么我们不妨考虑知道一组解之后的情况。

我们按这条链将点标号为 ，考虑除了这条链之外还有哪些合法解。

可以画一下，发现此时如果想要从一个点出发经过所有点，走出的路径一定形如下图：

即从某个点出发，走到 然后不断走回边跳回 ，再走到某个点

那么如果红色路径是一条合法的解，考察这张图上还可以有哪些边：

可以发现可能的边一定形如图中绿色的边，而图中绿色的边都被红色路径经过的回边包含，因此我们得到结论：

• 确定一条合法路径之后，任意其它合法路径经过的回边一定恰好是所有没有被其它回边包含的边

当不存在 时，合法的起点最多有一个，即倒数第二个回边起点右边的第一个点

当存在 时，每条 的回边相当于 ban 掉 内所有点作为起点的可能性，其它点都是可以的

因此我们可以在求出一条路径之后，推出所有其它的可能的路径

那么问题在于我们如何求出第一个解。

做法 1

考虑维护 条链，初始每个点都是一条链，我们进行链的合并，时刻满足一条链只有链尾向链外有连边，合并的过程为：

• 如果一条链链尾向外的连边恰好有一条，并且这条边指向另一个链的链头，就把这两条链拼起来

合并的过程可以用并查集维护，在合并两条链的时候，我们只需要再 check 新链的链尾是否只有一条指向链外的出边，这个可以暴力扫，扫到一个指向自己链的出边就将其删除，找到两个指向外面的出边就停止

合并到合并不动为止，那么我们会剩下三种链：

• 链尾没有向外连边的链
• 链尾有 条向外连边的链
• 链尾恰有一条向外连边的链，并且这条出边指向的一定不是某个链的链头

如果只有一条链，那么我们就直接找到了一个解。

如果有多条链，我们对可能的起点进行分析。

性质 1：可能的起点一定在第三种链上

证明：只有从第三种链上的点出发，我们才可能走出自己的这条链

性质 2：可能的起点一定是链头

证明：

设我们从红色点出发，开始走路径，那么我们必定会从这条链唯一的出边走出，走到另一个不是链头的点

而此时，两段蓝色部分都满足，如果我们走进了这段链，那么我们就再也无法离开这段链，也即终点部分必须同时在两个蓝色部分中，矛盾

性质 3：如果有至少三条第三种路径，那么一定无解

证明：

设我们出发的链为 ， 必定为第三类链，我们会从 的唯一出边走到某个链 ，此时根据上面的分析我们知道终点一定在 链的蓝色区域内

分类讨论：

• 若 是第三类链，我们一定会从 走出， 连向其它链一定还会创建一个蓝色区域，因此不合法
• 若 不是第三类链，那么一定还有两个第三类链，而想要不创建出新的蓝色区域的话，这两条链一定都需要连向 的蓝色区域，而进入 的蓝色区域后一定无法离开，因此我们一定无法同时访问这两条链

因此，这种情况无解。

那么我们说明了，有解的情况下最多有两个第三类链，并且只有这两条链的链头可能成为起点，因此直接 check 即可。

总复杂度

做法 2

考虑随机化。

每次随机一个起点，从这个起点开始走，直到走不动为止，如果找到一个合法的起点就可以 break 了

所有被经过的点就没有再搜的意义了，因此我们下次再随机找一个没有被经过的点

可以证明，在有解的情况下，我们期望用 的复杂度就可以搜到一个正确的起点

证明：

有解的情况下，将点按照这个解的编号顺序标号，可以发现，我们从任意起点开始，大部分搜出来的路径一定是这个解的一段区间，不满足这个条件的情况就是我们从某个起点开始一直走走到了 ，然后从 跳到了一些奇怪的位置

那么一旦我们搜到 ，我们就视作停止搜索，并直接给复杂度 ，显然这样算出来的复杂度一定大于实际的复杂度

而此时，所有点搜出的路径就是包含或不交的了，套用分析即可得到期望复杂度是

因此当搜耗费的时间大于 时直接判断无解即可。

---

22. QOJ14426 - Grid Problem [E/K]

题面

你有一个 的矩形，初始全部为 ，你可以进行如下两种操作：

• 选择一个 子矩形，给这个子矩形中的元素加上或减去
• 选择一个 子矩形，给这个子矩形中的元素加上或减去

操作将矩形视为 torus（即矩形上下左右均循环）

求能得到多少种不同的值域在 内的 矩形，操作过程中值域可以不在 内，答案对 取模

题解

Sol

注意到以 为左上角分别做一次一操作，以 为左上角分别做两次一操作，可以得到 ，也就是说我们可以给任意位置

进一步可以发现，只要每行每列之和 ，矩阵就一定可以造出

那么问题转化为， 分别有权值 ，求所有每行每列之和 的矩阵的权值乘积之和

使用单位根反演，给每行每列设变量 与 ，那么我们求的相当于是 的所有变量次数都为 的倍数的项

给每个 都带入 ，一共 种不同的情况，但可以发现实际上我们关心的即为 和 分别填了多少 ，记为 与

所求式子即为：

$$\sum\binom{n}{a_0,a_1,a_2}\binom{m}{b_0,b_1,b_2}(c_0+c_1+c_2)^{a_0b_0+a_2b_1+a_1b_2}\\(c_0+c_1\omega+c_2\omega^2)^{a_0b_1+a_1b_0+a_2b_2}(c_0+c_1\omega^2+c_2\omega)^{a_0b_2+a_1b_1+a_2b_0}\\$$

将指数上带 的分别提出，进行简单推式子可以得到：

$$d_0=(c_0+c_1+c_2)^{b_0}+(c_0+c_1\omega+c_2\omega^2)^{b_1}+(c_0+c_1\omega^2+c_2\omega)^{b_2}\\d_1=(c_0+c_1+c_2)^{b_2}+(c_0+c_1\omega+c_2\omega^2)^{b_0}+(c_0+c_1\omega^2+c_2\omega)^{b_1}\\d_2=(c_0+c_1+c_2)^{b_1}+(c_0+c_1\omega+c_2\omega^2)^{b_2}+(c_0+c_1\omega^2+c_2\omega)^{b_0}\\ans=\sum_b\binom{m}{b_0,b_1,b_2}(d_0+d_1+d_2)^n$$

暴力枚举计算即可，复杂度

---

23. QOJ833 - Cells Blocking [E] ⭐

题面

给定一个 的字符矩阵，字符为 * 和 . 中的一种，分别表示障碍与空地

求有多少种方式恰好将两个 . 改为 *，使得修改之后不存在从 到 ，只向下或向右的不经过 * 的路径

题解

Sol

称 ，首先我们可以把不能到达 的点视为障碍，那么在剩下的图上，我们可以求出 到 一条尽可能向右走的路径，以及一条尽可能向下走的路径

那么将一个 . 改为 * 就可以让 不连通的方式，就是这两条路径的交，因此我们可以容易地计算这部分答案，接下来我们只考虑割掉的两个位置，任意一个都不能让 不连通的方案

那么一定是右路径和下路径各割一个，枚举右路径上割了哪个，那么我们可以套用刚才的方式，只要再求出新的右路径即可

设 ban 掉的格子是 ，这里至少有两种思路：

• 现在我们就是在不断走的过程中，需要额外判断走过去的点 不能满足从 出发只有经过 才能到 ，可以发现这就是 的下路径不经过 的意思，容易发现所有下路径形成一棵树，递推出这棵树的 和 ，即可 判断 是否在 的子树内
• 找到与 的 相等的斜线上，向左下方向第一个空白位置，可以发现，新的右路径一定经过这个位置，那么从这个位置向 和 分别走，即可得到所求路径

总复杂度

---

24. QOJ850 - Edit Distance Yet Again [E] ⭐

题面

给定长分别为 的小写字符串 ，请判断 的编辑距离是否 ，如果是则求出编辑距离，并给出一种将 编辑为 的步数最小的方案

编辑距离定义为：一次操作可以插入、删除、替换一个字符，将 变为 的最小操作次数

组数据。

，20s

题解

Sol

做法是 Levenshtein Distance 的弱化版。

应该是，我也不记得了。

考虑求编辑距离的 dp： 表示我们当前将 和 匹配上的最小代价，转移有三种：

一般的情况现在还没有什么好的算法，而这题唯一的区别就是增加了对答案的限制

一件比较显然的事情是在 dp 过程中我们一定不会访问到 的状态，因此我们把状态限定在了 条斜线组成的区域上

我们尝试从小到大扩展，每次维护出 值 的所有状态集合，这个集合第一次包含 就意味着我们成功了。

可以发现，每条斜线上只有长度最大的 有用，即 一定时，我们只用保留 最大的状态，证明可以考虑如果 存在一条花费更小的路径到 ，而 和 在同一条斜线上且 更大，那么 可以模仿 的路径，每次切换斜线的时候都可以保证花费不超过 的花费，且一直比 更大，直到重合或者先到达

因此我们可以设状态 表示答案 ， 的状态 中， 最大是多少

转移时 可以转移到 ，然后再跳一段 从匹配到的位置开始的 lcp

使用 SA 实现单组复杂度为 ，使用二分哈希实现单组复杂度为

---

25. QOJ837 - Giant Penguin [E] ⭐

题面

给定一个 个点 条边的连通无向图，保证每个点最多属于 个简单环

次操作，每次操作染黑一个点，或者给定一个点 ，求距离所有黑点到 最短路的最小值

题解

Sol

这个询问看起来不好处理，首先我们考虑树上怎么做。

我们发现树上就已经需要使用点分治了，我们建出点分树之后，染黑一个点就是更新这个点到点分树上所有祖先的最短距离，查询就是遍历点分树上所有祖先

而在图上，我们发现这个图特殊保证了性质，但是这个性质看起来比较奇怪。

这个询问还是很难用别的方式处理，我们还是回到分治的思路，我们可以拓宽一下点分治的过程，改成每次选若干个关键点，把整张图切成若干个连通块，然后处理每个关键点到所有点的距离，对每个连通块递归下去处理

可以发现，我们任意取一个生成树，跨过生成树上任意一个点的非树边应该最多有 条，因此我们可以选择生成树的重心，然后把这个点，以及所有跨过这个非树边的边拿出来，对每条边任意选它的一个端点作为关键点，那么把关键点割掉之后图一定不连通，只要预处理这 个关键点到当前分治层中所有点的距离即可

复杂度

---

26. ATXmascon 2022 - Happy Game [K] ✔️

题面

给定一张 个点 条边的无向连通图，对于其中的每个点 ，定义 为：

• 初始将 染黑，接下来每次同时染黑一个或两个与之前就有黑色邻点的点，最少多少轮之后能将整张图染黑

求 。

题解

Sol

首先想办法发现结论：固定 ，其中 表示距离 最短路长度 的点个数

证明：

可以发现这是答案的一个下界，我们也可以证明答案能取到这个界

考虑倒过来，我们随便取一棵最短路树，然后每次找到最短路最大的点，以及下一个最短路最大的能删的点（若存在），然后证明这个式子一定会至少

设选择的两个点到 的最短路为 ：

• 如果 ，那么 的所有 都会 ，而对于 ，这些层在删之前只有一个点，因此删完之后算出来的值一定不超过 ，而第 层不存在了，原先的 就是 的，因此最大值一定小于等于原来
• 如果 ，那么原来 一定不是最大值，删完之后所有 的值一定会 ， 的值不变，因此最大值也小于等于原来

那么我们就说明了这个式子的正确性，接下来考虑计算这个式子的最大值

即求 使得 最大，可以注意到答案 ，所以我们可以先把这种情况判掉，之后不考虑

并且，当 的 有至少两个的时候，我们可以将选择的改为 ，一定不劣

同样地，对于 ，我们也可以将其忽略掉，我们找到最大的 使得 的点只有一个，那么 的部分至少有 个点，由于我们是 ，所以答案还是对的

而上面这些条件综合起来，意味着我们选的 一定恰好有一个点 ，并且这个点把图割成了 的部分和 的部分

设这个点为 ，我们直接把所求的式子改为 ，这样不会算大任何东西，并且一定能推回原来的答案

这个和割点相关了，因此我们可以建出圆方树。

这个问题显然有很多性质我们可以用，比如，如果我们选择了两个点 ，但还存在另一个圆点 满足 （ 表示圆方树上距离），且 和 ，在以 为根时没有祖孙关系，我们可以证明一定不需要考虑这样的

证明：

讨论 和 的 lca 是圆点还是方点。

如果是圆点，如左图，我们将 调到 和 的 lca，我们会损失路径上每个点双的 之和（不算点双的根节点），而每一个点双至多会让我们的值 ，但右侧 的路径现在被踢出了和 连通的连通块，因此每个点会贡献 ，加起来可以发现

如果是方点，如右图，我们将 调到 和 的 lca 的父亲，依然可以像刚才一样算，每个点双 ，但右侧至少会加回来这么多 ，因此调整收益

而这样调整会让 越来越小，因此调整一定会停止。

因此，我们需要考虑的 一定满足不存在 ，这个看起来和直径有点关系，所以我们求出直径，考虑 的形态有哪些可能：

• 如果 不在直径上，那么以直径为根后， 若不在 的子树内，由于我们一开始判掉了 ，因此 是叶子，那么一定有一个直径端点是一个合法的 ，能够把这个 干掉
• 如果 在直径上，我们不进行额外讨论

可以发现，此时 一定满足，从某一个直径端点， 是 的祖先

那么我们分别将两个直径端点定为根，首先固定 ，以及 在圆方树的哪个方点的子树，此时 的选取就是这个子树内距离最大的点，求一下子树最大值即可得出 是 祖先的所有情况最大值

对两个直径中点分别求一遍，即可求出答案

总复杂度

---

27. QOJ857 - Social Distancing [K]

题面

给定一棵 个点的树，以及两个点集 ，满足 且 均为独立集

每次你可以将 中一个点沿树上的边移动一步，但要求保证操作之后 仍为独立集

请在 次操作内将 变成 ，或者判断无解

题解

Sol

操作可逆，我们考虑给每个连通块选一个代表元。

每次尽可能把点往下放，按深度从大到小排成一个排列，我们按这个排列，将 分别调到字典序最大的可能的集合

那么每次就是选择一个点 ，然后判断是否能把任意一个点挪过去，当一个点到它应该在的位置的时候，可以大胆猜测这个点之后就不会再动了，我们就把这个点和它的邻点直接从树中删除

判断是否有一个点能走到 ，我们可以以 为根考虑：如果某一个点 到 的路径上有点 ，那么我们就可以不用 ，直接用 走到

因此我们只用考虑到根路径上没有其它在 内点的点，而假设说 要到 ，我们需要做的就是阻挡 到 路径的 内的点全都推到子树内，给 让出位置

那么我们就先进行一遍向下推的 dfs，然后再进行一次 dfs 看看有没有任何点能向上提即可

总时间复杂度

可以发现这个正确性哪哪都看着不那么严谨，但是我好像也没有找到人证过这个东西。为什么大家就都默认不需要证明了。

---

28. QOJ1166 - Designing a PCB [E]

题面

给定一个长为 的数列， 每个数恰好出现两次

这些点第 个点排在 ，你需要画 条折线，这些折线的拐点只能在整点，折线的每条线段只能平行于坐标轴，并且折线之间不相交

请构造方案或者判断无解

题解

Sol

如果直接把每两个 之间的连线，可能有八种连线方法，可以尝试建 2-sat 发现怎么建都建不出来。

考虑使用一下大脑。

首先，如果 ，容易手模发现 必须是在直线的一侧直接连起来

然后如果 ，可以手模发现不能出现 都向下连或者都向上连的情况

因此我们对每个点向下或者向上建 2-sat，所有限制都是相等或不等，因此，可以用并查集解决

然后，我们需要说明只要满足这些必要条件，我们就一定能构造出来解

事实上确实是这样的，我们对于所有 方向不同的配对，都让它们从左边绕过去，可以验证区间的三种位置关系，发现只要方向满足条件，这样构造就是不交的

复杂度

---

29. AGC070B - Odd Namori [E]

题面

给定一棵 个点的有根树，点 为根，图 满足如下条件：

• 中每个点出度恰好为
• 中没有偶环
• 对于任意 ， 中不存在 的有向边

求所有合法的 的 之和，对 取模

题解

Sol

这也太魔怔了。

考虑选择一些点，然后钦定它们最后组成若干个环，那么这些点最后对答案贡献的容斥系数应该是 ，这样奇环的系数是 ，偶环的系数是

但是这样还有不能选树边的限制，所以我们再对树边的限制进行容斥，也就是说，最后我们的形态应该是选出了若干条树上的点不交的链

考虑选出 条奇链， 条偶链的最后组合出 之和 ，其有转移式：

$$F_{a,b}=-F_{a,b-1}+(b-1)F_{a,b-1}+aF_{a,b-1}=(a+b-2)F_{a,b-1}\\F_{a,0}=F_{a-1,0}+(a-1)F_{a-2,1}=F_{a-1,0}+(a-1)(a-3)F_{a-2,0}$$

推一下可以发现 ，其余位置均为 ，而算一下可以发现再乘上钦定树边的 的若干次方之后选出一条奇链和偶链的系数应该都为

也就是说，我们只用考虑什么都不容斥，和容斥一条链的方案

$$ans=n(n-1)^{n-1}+\sum_{i=1}^n\left((n-1)^{n-dep_i}+\sum_{j=1}^{dep_i-1}n(n-1)^{n-j-1}\right)$$

容易 计算。

---

30. QOJ1173 - Knowledge Is… [K] ⭐

题面

给定 个区间 ，以及一个常数 ，你需要将尽可能多的区间分配给某个人，使得：

• 每个人被分配的区间数不超过 ，且一个人被分配的区间不交

构造方案。

题解

做法 1

Sol

很有道理的做法。

可以注意到即为求最大匹配。

我们称一组匹配里左边的区间叫做 集合，右边的区间叫做 集合，那么我们就是要选出合法的 集合，使得将 集合内所有的右端点视为 ， 集合内所有的左端点视为 ，这个前缀和

初始将所有区间都放入 集合，那么把一个区间选到 集合就是给两个区间端点分别

而前缀和 意味着我们选的点要被某个序列偏序，这个序列就是 [最后一次 的位置，最后一次 的位置，…… ] 这样一直下去，称这个序列为偏序点

考虑二分，假设我们选了 个区间作为 ，那么我们的要求就是这 个区间端点被上面序列中前 个偏序点偏序

而这个是可以处理的，考虑倒序枚举上面的 个偏序点，每遇到一个偏序点，显然我们一定要有一个区间右端点在这个点靠右，那么我们就选择此时可以选择的左端点最大的区间，可以证明这个区间一定在最优解内，然后根据经典结论，我们如果选择的区间是 ，可以直接分别将 前第一个偏序点和它们匹配上，将这两个偏序点删除，然后继续做上面的问题

过程需要使用堆来维护，因此时间复杂度 。

做法 2

Sol

还是求最大匹配，考虑直接贪心。

将区间按右端点从大到小排序，维护一组未匹配的点左端点尽可能大的匹配，以及一些不在匹配中的点，扫到一个新区间时，执行如下操作：

• 如果存在一个未匹配区间能和新区间匹配上，那么能匹配的未匹配区间左端点显然都大于之后的任意一个区间，所以任取一个和新区间匹配上即可
• 否则，考虑新区间一定能和任意此时匹配好的右区间匹配，因此我们可以用这个新区间置换出来任意一个左区间。我们选择一个最大的置换出来（我们不会置换出右区间，因为如果新区间能和左区间匹配，那么左区间的左端点就已经可以自由匹配了，置换出右区间和左区间没有区别）

直接用 set 维护即可，复杂度

---

31. QOJ2554 - AND PLUS OR [E] ⭐

题面

给定一个长为 的数列 ，求任意一对 使得 ，或者判断无解

题解

Sol

太难了。

即要求 。

考虑转化为选三个不交集合 ，满足 非空且

那么所求即为 ，若 ，则设 ，其等于

同理，那么我们不断这样拆，可以把原式拆成许多满足 的式子之和，而原式 意味着至少有一个 的式子 ，因此我们只要检查所有 的情况即可

复杂度

---

32. 集训队互测 2025 - 携春同行 [K] ✔️

题面

交互题。

给定 ，交互库隐藏了 个正整数 。

你可以进行如下两次询问：

• 一次性给定 棵点集为 的无根树，交互库会返回每一棵无根树的带权直径
• 给定一棵点集为 的无根树，以及一个整数 ，交互库会返回这棵无根树的带权直径是否等于

，想要达到满分，你需要保证第一种询问进行 次，，第二种询问经过 次

题解

Sol

考虑询问一个菊花，如果中心不等于 或 ，我们得到的是 ，否则得到的是

因此我们可以询问一边以每个点为根的菊花的值，这时候只要求出 我们就能初步确定所有节点的权值

我们再查询一个 sum，这时候排除掉两个 ，求其余所有菊花的和就可以得到 ，因此我们可以解出

那么我们就可以求出所有 的点的点权，以及剩下一堆

现在我们就需要求出一堆 中求出 在哪个位置

考虑二分：如果我们想检验一个集合 中的点是否有 的点，那么我们建一条长 的 的链，链编号为 ，然后把 中的点挂在 的位置挂一个菊花

此时如果 中有 的数，那么直径损失的一定小于 ，因此我们可以判断是否等于损失 的值即可

注意到上述二分需要满足 ，因此我们对 较小的时候特殊处理：

当 较小时，我们可以找出三个 的点 ，首先询问以 为根的菊花，然后把 接到每个叶子上，如果得到的新直径等于 ，那么就说明接上去的这个点 可能成为直径端点

这时我们尝试找到另一个直径端点，询问以 为根的菊花，然后把 接到 上， 接到另一个其它点 上，如果 是直径，那么新直径应该等于

因此我们可以用 次定位出直径

取 分治即可

---

33. QOJ6501 - Graph Partitioning [E] ⭐

题面

有两棵树 ， 满足根为 ，且每个 的点 的父亲都 ， 满足根为 ，且每个 的点 的父亲都

现在给定一张 条边的图，可能有重边，求有多少种方法将其拆分为两个边集 ， 满足 的限制， 满足 的限制

题解

Sol

我们相当于要给每个点分配一个向左的父亲和一个向右的父亲

那么每条边 ，我们要么用它满足 右，要么用它满足 左，我们可以将它看成 右和 左之间连了一条边

那么问题就是给定一张 个点， 条边的图，我们要给每条边定向使得每个点恰有一条出边，可以发现这个意思就是每个连通块都是基环树，且答案就是 ，其中 表示连通块个数

直接 check 即可，复杂度

---

34. UR32 - 王之钦定 [K] ✔️

题面

给定一个长为 ，值域为 的序列 ，你可以耗费 的代价将 修改为任意 的值

求最后颜色数 的子区间数减去代价和的最大值

题解

Sol

考虑颜色数 的子区间是什么样的，最后的结构一定形如，若干个极长的合法子区间，相邻两个合法子区间之间有一个“交段”：

[ab...ab][a...a][ac...ac][c...c][cd...cd][d...d][bd...bd]
----------------         -----------------------
         -----------------------         ----------------

容易发现的事情是交段一定是纯色的，且一定等于两边的合法段的颜色的交

考虑通过交段刻画这个结构，我们在交段之间转移，定义 表示考虑到了交段 ，颜色最后填成了 ，区间数减代价的最大值

但是直接转移只能得到很高次方的做法，因此我们考虑优化

观察性质：一个交段 ，要么下一个交段的左端点为 ，要么 没有被改过，因为如果 被改过，我们直接将其改为 最后的颜色一定不劣

也就是说对于状态 ，如果右边不是下一个交段，那么另一种颜色一定为

那么我们现在可以考虑重新开始设计转移了，从 出发，我们可以有以下转移：

• 下一个交段从 开始，那么枚举 和 ，转移到

  这部分首先可以分步转移，容易发现状态转移与 无关，对同一对 取最大的 去掉枚举 的复杂度，设辅助状态 ，去掉枚举 的复杂度，此时复杂度

  可以凸包优化做到

• 下一个交段不从 开始，那么设下一个交段为 ，那么 等于 或 ，为了优化转移，我们设一个辅助状态 ，先从 转移到 ，再从 转移到

  从 到 的过程中，我们希望规避掉枚举 的复杂度，由于 一定等于 或 ，这可以通过让 每次转移到下一个颜色等于 或 的位置实现，然后用一个颜色维记录另一种颜色是什么

  从 到 的过程中，知道这个新段的颜色是什么，可以用凸包优化掉枚举 的复杂度

总复杂度

---

35. QOJ1357 - Stone Catch Game [] ⭐

题面

有一个 的网格，初始有一个白棋在 处，有 个黑棋在 的位置

白方先手，每次可以将白棋从 移动到 或 ，黑方每一步可以选择一个黑棋，将其从 移动到 或 ，棋子可以重复

白棋与某个黑棋重合则黑方胜，若白棋先走出网格则白方胜，求胜者

题解

Sol

注意到 的情况黑方胜当且仅当 ，这时黑方容易一直控制和白棋在一条斜线上

那么对于 大的情况，相当于每个黑棋会引出一条斜线，最后黑棋的目标就是用斜线将白棋夹住，迫使白棋走到某一条斜线上

那么毛估估一下，看起来我们只会选择两条斜线，然后直接用这个斜线去夹

考虑对于两个黑棋 ，其中 ，能在白棋越过某一个黑棋之前将白棋夹住的条件，这看起来像是能用简单的式子描述的事情，所以我们列一些必要条件：

• 首先，白棋一直走 不能直接越过 ，即
• 其次，白棋一直走 不能直接越过 ，即
• 最后，白棋如果一直走到 ，两个黑棋恰好能抓到它的情况是分别在 和 ，因此我们要求

对所有 对检查即可做到 的复杂度

这些信息容易转化成三维偏序存在性问题，可以用二维偏序最值解决，复杂度

---