task17

[TOC]

1. MX-X12H - 地铁 [E]

题面

给定 ，你有一张 的格点图，你需要构造 条折线，使得这些折线都只包含 LRUD 中两种垂直的方向

你需要使得每个点都被至少一条折线覆盖，求最小的 ，并且要求构造方案

对于仅求最小 的数据： 组询问，

对于要求构造的数据： 组询问，

题解

Sol

每条折线要么是左上到右下，要么是左下到右上，不难发现我们可以将其延长到四个角上

设 出发了 条到 ， 出发了 条到

那么最多覆盖的点数有一个上界：左上角和右下角边长为 的等腰三角形显然最多一共有 个点，另一边同理有 个点，而中间的部分两边会重复 个点，那么我们能覆盖的点数应该不超过：

$$y(n+m-2y+1)+x(n+m-2x+1)+x(x-1)+y(y-1)-xy\\=(m+n)(x+y)-x^2-xy-y^2$$

减去一个 后这个式子应该 ，我们称这个为 的判别式

可以猜测一下这个就是充要条件，写一下可以发现这是对的，注意到 越靠近越优，我们就能通过仅求最小 的部分分

接下来考虑构造。

经过充分长时间的手模，可以发现如下事情：

不妨假设 ，那么推一下式子可以发现 ，因此不妨假设 ，一定有

我们可以通过上面的操作把 减去 ，原问题会变成一个 的子问题

带入判别式求值发现 ，所以归纳构造即可，边界条件是 ，这时候是容易构造的

---

2. AGC020F - Arcs on a Circle [E]

题面

一个长为 的环上随机放 段弧，第 段弧的长度为 ，保证 为整数，每个弧被均匀独立随机地放在圆上的某个实数位置

求每个点都被弧覆盖的概率，输出浮点数

题解

Sol

首先我们可以把最大的 放在序列开头，断环成链

如果我们已经确定每个弧放的位置的整数部分，那么这个弧一定会覆盖一段 的长度，而它能不能覆盖一个小段就是检查不同弧之间的小数部分大小关系

因此，只要我们能够提前得知小数部分的大小关系，我们就可以转化成整数上的问题，而小数部分的大小关系可以提前枚举

枚举大小关系之后我们列一个 dp 状态： 表示考虑了前 个值域上的位置，当前选完的区间覆盖到的最远右端点为 ，并且使用的区间集合是 ，转移可以做到

复杂度

---

3. 集训队互测 2023 - 森林游戏 [E]

题面

给定一棵 个点的有根树，根为 ，点有正整数点权

两个人在上面博弈，每次每人选择一个没有父亲的点，将其删除，得分为自己删除的所有点的点权之和

两个人都要最大化自己的得分，求最优策略下先手的得分

题解

Sol

不会做，所以考虑大胆一点。首先把点权变成先手减去后手。

我们直接仿照树上打怪兽的贪心，每次选点权最大的点出来，认为它一定是紧跟着它父亲后面操作的。

但是有一点问题：我们合并完的点可能有两种，一种是选完会改变先后手，另一种是不会改变的

如果选完不会改变先后手，且它的点权还是正的，那么不管是谁操作，都一定会取这个点，这个看起来就很对，所以可以考虑直接和上面合并。

否则如果选完不会改变先后手，且它的点权是负的，那么这个东西就很没用，我们把这种东西放到最后合并

如果选完会改变先后手，那么我们就按点权从大到小合并

具体地，我们按照如下规则给点安排顺序：

• 首先是点权非负，且不会改变先后手的点，这些点按照权值从大到小排序
• 然后是会改变先后手的点，这些点按照权值从大到小排序
• 首先是点权为负，且不会改变先后手的点，这些点按照权值从大到小排序

每次选出最优先的点和父亲合并即可，正确性不知道

复杂度

---

4. QOJ4212 - Brackets [E]

题面

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

请构造一个字典序最小的长为 的合法括号序列 ，使得 相等的两个位置在 中也相等，或者判断无解

题解

Sol

贪心：我们从前往后扫，如果将当前这个填成 ( 后存在后缀和 ，说明不能这样填，我们就填 )，否则就填 (

如果构造出来解了，那么显然这个解是最大的，否则我们可以说明原问题即无解

证明：令 表示与 位置 值相等的另一个位置，不妨假设

如果我们没有构造出来解，我们找到任意一组合法解，从左到右扫每一组相等位置的取值，找到第一个不同的位置，这个位置只能是我们的解构造了 (，而合法解构造了 )

此时我们要说明：我们可以调整合法解使得这个位置取了 )

设这个位置为 ，我们可以把合法括号串的判定看成每个左括号去匹配一个它右面的 位置

不难发现我们可以调整 中的相等对匹配的位置，使得它们匹配是合法位置中最严的

此时我们找到贪心解中 匹配的位置，假设它在合法解中匹配的是 ，那么 一定可以匹配 匹配的元素，也就是说我们可以把 换成

因此上面的贪心就是正确的，复杂度

---

5. ARC138F - KD Tree [E]

题面

给定一个 的排列 ，定义 个点，第 个点为

你会给一个集合 的点安排顺序，安排顺序的过程如下：

• 如果 ，那么只有一种安排顺序的方式，直接返回
• 否则，你可以选择一个 ，将所有横坐标 的放在前面递归安排顺序，剩下的东西放在后面递归安排顺序，或者选择一个 ，将所有纵坐标 的放在前面递归安排顺序，剩下的东西放在后面递归安顺序

题解

Sol

对第一步操作进行容斥。

我们选择一个操作的集合 ，认为它是第一步就可以操作的，那么这些操作会把平面切成若干个小矩形

那么可以发现，我们对点的要求就是如果我们把有点的小区域染成黑色，黑色应该是从左下不断向右上移动的

对这个跑 dp，我们强制一个路径是从左下出发，走到右上角，然后在两个黑色之间必须向上再向右

定义两个状态，一个 表示向上走， 表示向右走，假设我们要求矩形 的答案，固定 后 和 都只有三维，转移是 的

总复杂度

---

6. CF1710D - Recover the Tree [E] ⭐

题面

对于一棵 个点的树，对于每个 ，你知道编号在 内的点是否形成一个连通块

请构造一棵树，使得其满足条件，数据保证有解

题解

TBA

---

7. 集训队互测 2023 - 雷同 [E] ⭐

题面

给定 个物品，每个物品有两个属性 ，其中 由输入给定， 初始为

你每次可以指定两个物品 ，将它们合并，合并会花费 的代价，合并完之后新的 为 ，新的 为

求将所有物品合并到一起的最小代价

多组数据，

题解

Sol

合并过程是一棵二叉树，最后的贡献上是 ，其中 为深度

不难发现如果将 升序排序之后， 一定是递降的，而 确定之后，后面 带来的贡献就只和树的形态有关

那么我们只要能够对于一个固定的 值，快速求出最优的合并方式，使得 的贡献尽可能小

容易发现这是一个 从大到小合并的过程，每次我们会加入一些新点，然后将这些点匹配，从 个点变成 个点

最优的匹配方式就是按照优先深度大的互相匹配，因为可以注意到我们留到后面的子树一定 越小越优，而其它合并方式都会被深度大的贪心匹配偏序掉，所以这样就是最优的

在这种情况下，我们可以列出 dp 状态： 表示考虑完前 个 ，当前还有 个节点，一种转移是合并掉一层，从 转移到 ，另一种是加一个点，加的新的点会产生 的 值贡献

复杂度

---

8. 集训队互测 2023 - Permutation Counting 2 [E]

题面

给定 ，求有多少 的排列 使得：

对所有 求出答案，对给定质数 取模

题解

Sol

对两个限制同时容斥，那么相当于序列被分为了 和 个上升段

从小到大加入数，相当于我们有 个数组，我们需要选择一个 ，满足 ，每次递增地将它们加入到这 个数组中

方案数也即：

$$\sum_{a_1+a_2+\cdots+a_y=n-y}\prod_{i=1}^k\binom{a_i+x-1}{x-1}$$

可以用范德蒙德卷积发现这就是

但是这样会有些段是空的，那么再做一遍二项式反演即可

最后代码写出来就是 算一遍组合数，然后做四次二项式反演，很有意思。

复杂度

---

9. 集训队互测 2023 - 没有创意的题目名称 [E]

题面

给定一个正整数 和一个长为 的序列 ，求有多少长为 的整数序列 满足如下条件：

• 对于所有 ，
• 对于任意 ，都有 （我们认为 的位置都满足 ）

答案对 取模

题解

Sol

放弃思考，相信打表。

当 的时候答案为 ，所有合法的序列形如选择两个数 ，然后 后 内的数一直循环

的时候所有合法序列为选择三个数 ，然后先是 ，之后还是 个一循环，但是循环节内每个数可以选择加上若干倍的 ，使其仍然不超过

的时候，不妨设 ，那么所有合法的序列为，选择一个 ，然后 个一循环，循环节如下：

• 如果 ，循环节为
• 否则循环节为

循环节 位置上的数均可以加上若干倍的 ，需要满足仍然不超过

之后只要统计不超过 的限制方案数即可，复杂度可能可以做到 ，但 跑的太快了，我也懒得管了。

---

10. 集训队互测 2023 - 挑战积和式 [K] ⭐

题面

给定一个长为 的数组 ，请选择一个长为 的整数序列 满足 ，求最大的 的值

题解

Sol

设最优解的和为 ，积为 ，那么其中的一个元素 删掉换成 之后会变成 ，这样调整不优当且仅当 ，也就是说最优解的 应当

而 的数最多选 个，那么我们设一个状态 表示选了 个数，乘积为 的最大和，这样我们就获得了一个 的做法

但是这个还是太高了。

最后复杂度里不能带 ，因此我们可以考虑能不能怎么把乘积分成两半最后合并起来

引理：对于任意非负实数集合 ，满足 ，，一定存在一个子集 使得

证明：

• 如果 ，那么我们直接选 为这个最大的元素即可
• 否则我们将 的大小补到偶数，然后从小到大排序，取所有排名为偶数的数作为 的元素，此时 显然 ，而我们将 去掉之后可以说明其一定 ，即

那么我们的值域只用保留到 ，最后将两个数组合并起来可以用凸包做到线性

注意到我们上面的说明中只用到了 和 ，那么我们可以对选的个数快速幂算出，每次转移依然是调和级数的

那么总复杂度就是

---

11. CF1707E - Replace [E] ⭐

题面

给定长为 的数列 ，定义函数 ：输入一个区间 ，返回

次询问，每次给定一个 ，求 迭代多少次之后会变成 ，或者判断永远不会变成

题解

Sol

注意到如果两个区间 ，那么 ，且

证明是容易的。

那么我们就可以选择一些关键区间，然后倍增处理出这些关键区间经过若干步之后的结果，最后合并起来

具体地，我们预处理 表示 经过 步之后变成了哪个区间，这样每个询问区间都可以拆成两个关键区间，那么我们询问就是 的

总复杂度

---

12. CF793E - Problem of offices [S]

题面

给定一棵 个点的树，根为 ，给定四个节点 满足它们均为叶子，且两两 lca 为

现在取一个欧拉序将其循环无穷多遍，是否可能满足：

• 任意两次相邻的 出现之间间隔的其它叶子个数相等
• 任意两次相邻的 出现之间间隔的其它叶子个数相等

题解

Sol

设两个变量 ，分别表示 间的叶子个数和 间的叶子个数

可以发现每个子树是否要对 进行修改是独立的，因此可以分开跑两遍背包

复杂度 或 或

---

13. UNR6 - 小火车 [K] ⭐

题面

给定 个整数 ，求一个长为 的序列 ，满足 ，且

保证 。

题解

Sol

我们的问题实际上就是要找两个子集和相等，而 保证了一定存在这样的子集

在值域上二分。时刻维护一个区间 ，表示和在这个区间内的子集个数 ，每次从中间分开两边至少有一边个数大于长度

求子集和在一个区间内的数量可以折半+双指针

复杂度

---

14. CF1483E - Vabank [E]

题面

你想从银行里贪钱。

你每次操作可以指定一个正整数 ，表示你要从银行里贪 的钱。

银行有一个阈值 ，如果 ，那么你会得到 块钱，否则你会被罚 块钱，如果你的钱数 ，那么你会被警察抓走

你初始有一块钱，请在不被警察抓走的前提下， 次操作内求出 的值

题解

Sol

首先依次询问 ，如果被罚钱了立刻停止，这样我们就知道了 在 内

然后我们在这个区间内二分，假设我们现在知道了 ，我们找到 的中点 ，如果钱数不够 就一直询问 ，够 之后就可以询问

这样分析一下次数可以发现是 的，总共是 ，还是太大了

改变一下我们的策略，可以发现我们最劣的情况是 等于当前二分的左端点 ，这种时候我们每次询问 都会失败，钱都会变得很少，因此一个简单的想法就是我们将询问中点向左调一下，但是要怎么调呢？

由于我们是倍增二分，我们可以假设 是远大于 的，所以我们直接将任意剩下来的 量级的钱忽略不计

这时候我们的钱一定是 的形式，而注意到 ，所以我们可以将 变到

也就是说，我们将 看作 ， 看作 ，我们就可以得到当前的钱数大于多少倍的 ，而这个已经可以记到 dp 状态里了

令 表示长为 的区间，当前钱数是 的 倍，最少的最坏情况询问次数

翻转一下状态和值，可以得到一个 的 dp，运行这个 dp 我们就可以求出在这个假设下，一个区间长度的最少询问次数

每次按照 dp 告诉你的最优转移点去询问即可，实际数据里跑出来是 次询问，比官解稍劣一点。

---

15. KTSC2025 - evolution2 [E]

题面

给定一棵 个点的有根树，点有点权 ，满足 为 到 的排列，且父亲的权值小于儿子的权值。

你可以向交互库提出询问，每次给定两个整数 ，交互库会回答 是否成立

设树结构一共有 种可能的点权序列符合条件，你需要在 次操作内求出所有 的值

题解

green:Sol

考虑一些极端的情况：

如果整棵树是一条链，那么 ，我们需要立刻确定答案

如果整棵树是一条链，再拼上一个点，那么 ，我们需要把这个点放到序列里二分

进一步地，如果整棵树是两条链，长为 和 ，那么 ，我们需要将两个序列通过某种方式归并起来。

而我们发现，如果我们能在 次操作内归并两个序列，在原树上就直接可以将其变为一条长为 的链，这样总的 就除掉了 ，也就是说我们可以在 次操作内解决整个问题

归并两个序列我写的是，设 ，每次找到 序列中的中点，二分出其在 中的位置，然后将 序列各分为两半左右递归，这样能获得 分

注意到这种策略比较劣的情况是 和 比较接近的情况，此时我们可以 次操作直接归并

把 的情况判掉就可以通过了。

---

16. ARC199D - Limestone [K] ⭐

题面

给定 ，有一个初始全 的 矩阵 ，你可以不断将某一行的前几列赋值成 ，或者不断将某一列赋值成 ，求对于所有能得到的矩阵 ， 中所有元素之和的和是多少，答案对 取模

题解

Sol

考虑最后一行的状态，为了唯一计数，不妨假设我们是把第一段极长的 用行操作染掉了，那么右边会有一些额外位置是 ，这些位置必须一整列都是 ，那么我们就可以将这列删掉

即，我们枚举一个 ，分别表示极长 段的长度，和右边有多少 ，算一些系数从 转移过来

注意到可以不枚举 ，提前预处理系数，总复杂度

---

17. ARC199A - Flip Row or Col 2 [K]

题面

给定一个大小为 的 矩阵，以及两个序列 ，保证 ，请合适地进行若干次行或列取反操作，使得第 行的 的个数为 ，第 行 的个数为

给出构造或判断无解

题解

Sol

注意到我们可以 ban 掉第一行的操作，不改变答案。

将第一行消为 ，此时我们至多进行 次列操作，对于剩下的每行，如果其 的个数 ，那么我们必须将行取反，否则必须不能取反

那么现在我们就没有行操作了，每一列 的个数必须是 或 ，相应地执行操作即可

复杂度

---

18. EC Final 2018 - Exotic … Ancient City [E/K] ✔️

题面

定义一个 个点的无向图，给定 个三元组 ，表示对于所有 ， 和 之间有一条边权为 的边

对每个 ，求只保留前 列点的图上，最小生成树的权值是多少，保证有解

题解

Sol

注意到 很小，最小生成树有一个求法是对每个 ，保留边权 的边，根据形成的连通块数就能判断出来最少连多少条 的边，全加起来就是最终答案

首先外层枚举一个 ，然后下面我们需要解决的就是加边，每个前缀的连通块数

如果暴力的话，我们就只需要用并查集不断维护出上一行的连通性，然后加上这一层的边，就知道有多少边是有用的，进而能够推算出连通块数

进行优化。

首先考虑如何从上一行的连通性推算出下一行的连通性，可以发现两个点 若能只通过 行的边联通，那么 也能只通过 行的边联通

考虑从第一行逐次扩展联通性的过程，第一行到第二行时，我们需要将 连向的所有 的点合并起来，这会在联通性上加一些边

而加的这些边，在第二行扩展到第三行的时候，就相当于我们需要把边端点的两个集合合并，从而又会新加一些边，这样不断扩展下去即可

而一共只会加 次边，因此使用并查集，复杂度是可以均摊的。

接下来考虑求出每一轮加的边有哪些是有用的，这个我们可以再维护一个并查集，有 个点，初始我们将所有 加入到并查集中，每次我们加一条边 的时候，就在 加一条边，此时可以通过两个并查集的连通块个数推算出有用的边数

总复杂度

---

19. AGC049F - Happy Sequence [K] ✨

题面

给定三个长为 的非负整数序列 ，你需要求一个对 中每个元素进行修改，使得对于任意 ，都有

将 修改为 会花费 的代价，需要满足 也是整数，求最小代价和

加强版：

题解

Sol

太魔法了。

将 排序

可以观察到最后的序列需要满足 ，也可以观察到

可以猜出一个性质：题目条件等价于，且

虽然不用这个性质也能做，但是用了会方便一点，称 ，

证明：

我们可以证明，

首先证明 取到的 满足 的 数量相等：画出 的折线，那么 一定开始结尾均斜率为 ，且在 向右移动的过程中，遇到一个 会使斜率 ，遇到一个 会使斜率 ，且开头结尾斜率都为 ，因此所有极小值的位置一定是某个斜率 的位置，也就是说 的 数量相等

然后证明 取到的值一定对应某个 ，满足 的 数量相等：考虑 的极小值位置 ，必然有 ，因此取 满足条件

最后可以验证当 的 数量相等时，由于 ， 和 的值确实是相等的，因此得证

接下来我们都用 考虑问题。

分析操作的性质，由于代价函数是凸的，所以我们可以直接将操作拆成代价为 的小操作

如果存在 ，且 的操作，那么我们把这两个操作删了一定更优

也就是说我们的操作一定满足存在一个分界点 ，使得 左边的东西都向右， 右边的东西都向左

此时可以发现，考察所有操作对每个位置的 值的改变， 是被增大最多的

进一步地，考虑最靠右的向右点 ，和最靠左的向左点 ，那么 内部都是被增大最多的 ，而最后这其中一定存在一个 满足 ，否则我们可以将 操作同时删去 ，仍然合法

而被增大最多却还是 ，说明这段区间一定是包含初始 的最小值的，因此我们可以找到最开始的最小值 ，然后将 左和 右分为两个单向的子问题

而对于单向的子问题，考虑固定一个代价 ，把所有 的操作全做掉，然后将每个点看作从此时的出发点，可以向左退掉一些步或向右多走一些步的双向问题，此时上面的结论依然是成立的，所以可以继续下去分治，每层代价范围会减半

总复杂度为

---

20. QOJ9080 - Item Exchange [K] ⭐

题面

有 个人，初始第 个人有物品 ，并且每个人都有一个 的排列 ， 表示第 个人对第 个物品的喜爱程度

你需要进行若干次如下操作，使得第 个人拥有第 个物品：

• 选择两个相邻的人 ，满足这两个人都更喜欢对方手上的物品，然后交换他们的物品

求是否可能达成， 组数据

，保证 的数据不超过 组

题解

Sol

注意到，每个人手上的物品一定是越变越喜欢的。

注意到，每个物品一定要么向右要么向左。

假设 ，注意到，找到最后一个向左的位置 ，那么 的位置一定不会动，并且中间一定有恰好 个向左， 个向右，并且我们如果确定了哪些点向左，进行的交换集合就是固定的

此时我们就有 的做法了，但我们性质还是太少了，难以优化

继续观察：对于任意一个 ，我们发现如果固定了它的方向，那么它在任意可行解内向左/向右走到的点都是唯一的

以向左的情况举例，那么 必定发生过一次交换，我们找到最大的 满足 ，且 中 比 优， 中 比 优，则 一定要在 处交换

假设 在某个 位置交换，显然 ，那么 都一定先被 经过后被 经过，也就是说 优于 ，而 中必须 优于 ，否则无法交换，因此上文中的 是唯一可以交换的位置，不存在则该物品无法向左

对于向右的情况同理。

现在我们知道每个 可以向左走到 ，或者向右走到 ，每个 只有两种情况，这启示我们使用 2-sat

考虑加哪些限制。

注意到选出来的方向一定满足 要互不相同，且 要互不相同，可以发现取值数加起来恰好为 ，那么我们只要让任意两个相等的最多选一个，最后一定会每种取值恰有一个

这之后，我们只要让每次交换都合法即可。

最后观察一个性质：对于 ，如果选择了 ，它们交换的位置是固定的

这是因为我们知道 相当于知道了 在所有向右中的排名，同理也知道了 在所有向左中的排名，它们交换的位置是可以推算出来的，即为

那么我们对每对 ，判断一下在 位置交换是否合法，不合法则连边限制它们不能同时取右左

可以发现这样如果有解，跑出来的解一定 两两不同，且每一步交换都是合法的，因此为合法方案

对每个 都做一遍，总复杂度

---

21. QOJ10042 - Scheduling [E/K] ✔️

题面

有 个区间 ，要求每个区间匹配到一个 中的位置 ，并且要求任意两个 绝对值之差 ，给出构造或判断无解

题解

Sol

如果没有不能相邻的限制，那么这个是容易的：我们只要从左到右扫，每次取出右端点最小的位置将其匹配掉

考虑强行改一下上面的做法，我们维护两个集合 ，分别表示第 个位置选和第 个位置不选，得到的右端点集合，那么会有转移：，前一种是好办的，后一种涉及两个状态的比较，不是很好处理

但是尝试一下可以发现，我们按照任何一种看起来比较有道理的方式比较两个集合，最后都对了

具体地，我们可以证明如下结论：

• 对于任意一个状态 ，如果其存在合法状态，那么一定有一个集合能够全维偏序同状态的其它所有集合
• 对于 都存在合法状态的情况， 一定能全维偏序

~~Proof~~

Proof 好像有点问题。

称可以取到状态 的所有匹配方式（即有哪些区间被选进了匹配）的集合为

我们证明如下事情：如果 ，则

对于任意 中的集合，设我们是通过选 这个集合中的 将其匹配出来的，我们可以说明可以通过一些调整使得 包含 ，且仍能匹配原集合

如果 不包含 ，那么我们直接加上 即可

现在 必定包含 ，如果 没有匹配区间或者匹配的区间右端点 ，那么我们也可以直接调整到

因此匹配 的区间一定右端点 ，则其左端点不能为 ，否则 就倒闭了，我们直接选上 ，用 替代 ，这之后如果我们删除掉 的位置，这个问题就变成了一个类似的，规模更小的问题，手玩一下可以发现前面的分析依然是成立的，因此得证

而一开始的两个结论也就可以归纳证明了，相当于是已知 内部有全维偏序，那么根据转移容易推出 内部也有全维偏序

这个直接写就是 的，瓶颈在于复制 ，那么额外维护一个 ，表示两个集合的交集，当我们需要执行一个复制给另一个时，我们就将两个都清空，将所有内容扔到 中，容易做到