task21

[TOC]

1. QOJ11623 - Construct Point [E]

题面

组数据，每次给定一个二维平面上的非退化三角形，保证顶点为整点，请找到任意一个严格在三角形内部的整点，或报告不存在

，坐标范围在 内

题解

Flamire 做法

Sol

判断是容易的，使用皮克定理计算面积比较即可，但是这对解决这个题并没有什么用。

将三个点按照横坐标排序，拆成两部分，对于一边的情况，相当于我们有两个分数满足 ，我们要找到一个分数 满足 且 最小

这个可以在 Stern-Brocot Tree 上实现，细节略为繁琐，复杂度

题解做法

Sol

取整数 ，对所有点进行 的变换。可以发现进行这个变换之后，每个整点对应的还是整点，且每个非整点对应的还是非整点，并且由于我们只是将平面拉伸了一下，因此点和线的相对位置关系应该不改变。

那么我们就可以通过拉伸操作，把原三角形 拉成一个容易处理的形式。

首先，我们将 通过平移放到 。

然后，我们将 移动到坐标轴上，由于我们可以不断进行 和 ，所以我们可以通过类似辗转相除的方式将 放到坐标轴上

再使用一些翻转方式将 翻到 轴正半轴上，此时 ，那么我们可以不断执行 的操作，调整 的大小，我们再通过一系列这样的操作和翻转操作，令

此时这个三角形若不包含 ，则一定不包含任意整点，因此只要判断 ，再把所有操作求逆即可，复杂度

---

2. QOJ11622 - Colorful Doors [E]

题面

有一段长为 的桥，用 个门隔开，第 个门分割第 段桥和第 段桥。门有颜色，且 种颜色每种恰好有两个

当你在第 段桥时，你会进入第 个门，然后被传送到另一个颜色和第 个门相同的门右边那段桥

你会从第 段桥开始，一直这样走直到走到第 段桥为止。

现在给定一个长为 的 01 串 ，表示 中的每段桥有没有被你经过过，你需要构造一个匹配门的方式使得其成立

题解

Sol

认为 。把每个门按照其相邻的两段桥的 01 称呼。

那么不难发现，11 门只能内部连，00 门只能内部连，10 门必须连 01 门，因此奇偶性不对可以直接判掉。

00 门内部连显然怎么连都无所谓，随便连即可。

我们需要让 11 门和 10 门的连接方式使得所有 1 的位置都连通。

可以发现，当 11 门的数量是 的倍数时，我们可以直接将所有 10 门和下一个 01 门匹配，这样会等价于一个 全 1 的问题，而如果此时 11 门的数量是 的倍数，我们可以 1 2 1 2 地匹配，将相邻的四个门消掉，因此可以构造

否则，11 门的数量是模 余 的，可以发现此时全 1 是构造不出来的。证明可以考虑增量，每加一对门一定会导致连通块个数奇偶性变化。

因此，我们一定要在连 10 门的时候，把某些 11 门独立出来形成一个环，而可以发现只要我们将 11 门拆成了一个链和一个环之后，可以分类讨论环长模 的余数，总是可以构造出来解

实现即可。

---

3. QOJ10871 - Joy of Sushi [E]

题面

给定一个长为 的数列 和一个长为 的数列 ，依次进行如下三次操作，称为一轮：

• 对于 ，令
• 将 分别循环右移一位

求最少多少轮操作之后所有 同时为 的倍数

题解

Sol

想办法固定 不动，可以发现这个操作的周期是 。

对于 ，它前 次操作都是 ，接下来 次操作是 ，一直这样下去，最后 次操作 ，一共 次操作

而对于 ，可以发现，它的操作序列就是上述操作序列循环左移 次的结果

因此，我们可以定义一个序列 ，下标为 ，那么 的操作就是从第 次操作开始的循环位移

可以发现，一个整周期的效果相当于给所有 加上一个定值 ，因此我们只要判断前面的每一个时刻是否满足所有 均相等，然后判断即可

定义 的前缀和为 ，我们需要对每个 判断是否有，对于 ， 全部相等

转化为相邻项 和 的这个值差等于 ，可以发现我们就是要求 的值等于某个值，也就是说这个问题实际上是我们有一个序列 ，我们要对每个 判断是否有

对于模 相同的 ，这个就是循环位移，可以用多项式哈希维护，因此总复杂度为

---

4. QOJ10862 - Advanced Evolution Studies [E]

题面

给定正整数 以及 个限制 ，保证 ，你需要构造一棵有根树 满足如下条件，或者判断无解：

• 其点数在 内
• 对于每个限制 ，都有 是 的严格子孙

题解

Sol

注意到我们可以使 中 的点都是叶子：如果一个点 不是叶子，那么我们将这个节点更改为一个新的编号，然后把 挂在这个节点下面不会改变任何点对的 LCA

把这棵树看成从一堆单点合并成全集的过程。正着操作的影响不好描述，因此我们考虑倒过来。

每个限制相当于合并出 前我们要么有 ，要么有

倒过来就相当于我们需要将全集拆成若干个小集合，而拆一个集合 的时候有如下限制：

• 若对于某个限制 ，满足 ，则 必须划分到同一个小集合内，且如果 在同一个小集合内，那么 必须都在同一个小集合内

而注意到把集合拆的更碎一定不会更劣，因此我们进行如下过程：

• 初始将 中每一个元素划分为一个小集合
• 将所有 的小集合合并
• 如果当前有某个限制的 在同一个小集合内，那么将 的小集合合并

最后如果得到的是全集，那么一定无法合法分割，返回无解，否则递归进行

第三步可以使用启发式合并，每次合并探测更小的那边的所有连边，复杂度

---

5. QOJ10697 - Judge Error [E]

题面

给定一个 个点的无向图 ，判断 是否有唯一的完美匹配，有则输出方案

，边数

题解

Sol

画一画可以发现看起来一个点双如果有完美匹配，则一定不唯一

可以发现这可以推出边双的完美匹配不唯一：我们建出圆方树，可以根据子树点数奇偶性判断每个割点要跟哪边匹配，我们把这个看成一个方向，那么一定存在一个所有相邻的方向都向内的点双，这个点双必须是一条边，这意味着图想要有解必须存在割边

这也为我们提供了一个对有解的图构造解的方式：我们每次找到任意一条割边，根据两边连通块的大小奇偶性判断是这条边是直接匹配还是删除，如此递归即可构造

朴素实现即为 ，使用一些手段将找割边优化到 可以做到总复杂度

---

6. QOJ10693 - Flappy Bird []

题面

二维平面上有一个高为 的通道， 和 为不可逾越的障碍

有 个额外障碍，这些额外障碍可以描述为：给定 ，表示 和 的两条线段为障碍

求 到 的最短路（可以在二维平面上以任意方向移动）

题解

Sol

同 ARC001D，摘录一下题解。

称 的线段为下障碍， 的线段为上障碍，可以发现我们的最短路一定是一条折线，每个折点都是障碍端点，并且我们只能在下障碍端点右转，上障碍端点左转

从起点出发，走出一个上边界 和一个下边界 ，满足 只能左转（且只经过上障碍端点）， 只能右转（且只经过下障碍端点）

分别是凸包，新加入一个障碍时，我们只要加入新的障碍端点，更新凸包即可

如果加入某个障碍后 和 相交，那么一定有 或 中的某一个只有一条直线，不妨设为 ，此时可以发现我们最优解一定会走 中第一条线段，将起点移动至这条线段的终点，继续执行上述过程

可以使用双端队列 维护。

---

7. QOJ10688 - AmazingTalker [E]

题面

给定 个二元组 ，请给这 个二元组之间连边，使得对于任意一个二元组 ，其邻居 有多于一半满足 ，或者报告无解

要求构造方案边数不超过 。

题解

Sol

意义不明。

画到二维平面上，如果两个点为左上-右下的关系的话，在不考虑边数限制的情况下连上它们一定是不劣的，称这样的边为实边，其余边为虚边

进一步发现，不会有一条长为 的递进的虚边链（即 的链，其中两步都在向右上走），因为我们可以替换为连接首尾的一个虚边

因此，连完所有实边之后，设一个点的度数为 ，那么此时不合法的即为 的点，这些点必须向左下角连至少一条虚边，而连一条虚边就足够了

只需要判断每次 是否能在左下角选出合法点即可，容易做到

接下来解决边数限制的问题，一个点如果被某个 选到了就给它的 加 ，那么最后每个 的点只要连 条实边即可

随便使用二维偏序数据结构连足够多的边即可，，因此所有点的实边度数之和不超过 ，而虚边最多 条，因此总共边数不超过

---

8. QOJ10543 - Square Stamping [E]

题面

给定 个纵坐标为 之一的点，求最少用多少个 的正方形（包含内部与边界），使得它们的并集覆盖所有点

题解

Sol

将三条线从上到下编号为 ，考虑最左边的点，如果最左边的点在 或 上，那么我们一定选 矩形，当在 上时我们可以选择取 还是 上的矩形

而不妨设取了一个 矩形，我们需要检查覆盖的这段横坐标的 上是否有点，有点的话我们再用一个矩形覆盖，然后再检查 的范围，一直这样重复下去

注意到每次 交替停下的时候，我们的状态都是某个横坐标之前的点都被覆盖完了，因此设状态 表示只考虑横坐标 以后的点，都覆盖需要用的最小矩形数

那么如果暴力转移，我们就得到了一个状态数 ，转移 ，总时间复杂度 的做法

考虑优化，注意到我们过程中所有的状态形如 被覆盖到了 ，然后 被覆盖到了 的一个位置（或者 和 ），不难发现 越大答案越小，且 的答案最多比 大

因此，我们再额外存 表示此时 覆盖到了横坐标 ， 至少要覆盖到多少才能使答案小于 ，如果 时答案仍为 ，我们就认为 ，同理存一个

转移 和 可以二分，经过一些处理可以使复杂度为

本题还有一个记忆化搜索做法，即直接按照这个贪心执行，记忆化所有状态。出题人在题解里声称这是 的，但是略去了证明，感觉多少有点毛病，令人火大。

目前我还没有找到任何有道理的证明，个人倾向于这个实际上是没有道理的，只不过不好卡。

---

9. QOJ10083 - Single-Crossing [E] ⭐

题面

给定 个 的排列 ，你需要重排这 个排列之间的顺序，得到 的方案，使得对于每对 ，按照 的顺序排列后， 和 的相对顺序只会变化一次

给出构造或判断无解

组数据。

题解

Sol

如果我们确定了 ，那么整个问题即可确定：我们将 变为 ，其余排列类似变换之后，一定按照字典序排列，并且每轮交换的两个数一定满足前面的更小，只需要顺次检查每对 是否合法

这个也是可以检查的，我们将条件重新表述为：对于每个值 ， 到 的过程中新运动到 前面的所有元素必须

这个可以扫描线+树状数组维护最值解决，因此我们固定 判断合法是可以做到 的

接下来，我们就是要求出 ，可以证明，合法的 只有两个，即一个合法顺序和它的 reverse

有若干种方式求出 ：

• 考察一对 ，如果 和 的相对关系都出现了，那么我们可以将其分为两个集合 ，第一次时可以任意将一个集合放在前面，而递归下去之后必须要判断在外面大小关系，决定要把哪个放在前面

  找到一对相对关系改变的 可以任意选两个排列 ，找到它们第一个不同的位置

  但我们找到 的层数可能很大，复杂度退化为

  我们选取 时采用随机，在最终的 中 和 有 的概率都在此时集合的前 ，这样能保证期望 次之后就能将问题规模除以 ，不符合概率判断无解即可

• 也是优化上面的过程，观察我们不一定要找到 ，只要我们找到任意一个 ，并且我们划分开哪些排列是 ，哪些是 ，分别运行上面的 check 算法即可。因此，我们在上述的分裂算法中，每次走小的一边即可

• 对两个排列 ，定义为 的逆序对个数，也可以视作将 和 排成一排，将相等元素之间连线的交点数

  可以发现如下结论：，证明可以考虑上述画线的理解，右式即为计数所有折线之间的交点数，而由于任意两个元素代表的折线只会相交一次，所以这就直接等于所有元素的交叉次数

  因此，我们任意固定一个排列 ，找到与其 值最大的排列，其一定为 或

总复杂度

---

10. CTT2023 - 士兵游戏 [E]

题面

构建一棵 个点的树，对于每个 ， 向 有连边，其中 表示 的最小质因子

求 个点两两路径长度之和

题解

Sol

考虑每条边被贡献了多少次，转化为统计子树大小。

对于一个数 ，它子树中的数一定都形如 ，且 的最大质因子要小于等于 的最小质因子，我们就是要计数满足 的 数量

枚举 ， 时这个值即为 ，因此我们可以一开始将所有点按照 算

当 时，设 ，那么 ，也就是说， 的所有 对我们后面的事情都是等价的，因此我们把这样的 放在一起算，进行整除分块

因此我们的流程就是：枚举一个 的块，然后求这个块内 的 数量，并且求 的 的 数量

因此，我们需要处理出 和 ，分别表示 的数中 和 的个数， 只用存块筛处的值， 只用存 的质数

的转移就是正常的 min25 筛，只用更新 的位置，暴力写即为 。

但 的转移无法跳过 的位置。

注意到 的转移为 ，因此我们可以枚举 ，然后使用树状数组快速更新 ，这样我们只需要枚举所有 的块筛，因此复杂度为

枚举 块的部分也是枚举所有 的块筛，可以类似分析

那么此时我们就得到了一个 的算法，已经可以通过。

进一步地，可以发现我们在枚举到 时，只需要算出 位置的 和 值，所以我们枚举 的块筛的时候只需要枚举 的即可

复杂度：

• 当 时不超过
• 当 时不超过

积分一下可以得到枚举量级为 ，再使用树状数组可以把这部分做到

因此总复杂度为 ，理论上求 的部分也可以优化到 ，但是毛估估一下已经跑得很快了。

---

11. CTT2023 - 解谜游戏 [E] ⭐

题面

交互题，有一个隐藏的 的排列 ，每次你可以询问一个 的排列 ，交互库会返回有多少位置满足

你需要在 次操作内确定 ，

题解

Flamire 做法

Sol

没有什么出发点，考虑随机直到找到错排为止。根据某些结论，期望随机 次之后就能找到一个错排

但手玩一下可以发现有一个错排之后还是有些困难。直观感受可以画到一个矩形上， 表示 是否为真

那么一个错排相当于我们排除掉了一条斜线，但在此基础上构造别的结构依然比较困难。

因此我们可以考虑随机直到 和 循环左移一位都是错排，这样随机依然是常数次。

这时，我们交换 的相邻两位，这两位会分别错位 和 ，而错位 的情况我们是知道的。

也就是说，此时我们可以选出一个 的独立集，然后询问这里面有多少个位置是对的

那么二分即可，一个环可以拆成三个独立集，询问次数是 ，会被卡常，加一个推断，如果一行一列有 个 0 就填出 1，填出 1 就 ban 掉该行该列的所有其它位置，这样就可以通过了

提交记录做法

Sol

考虑随机出一个错排。在错排上交换两个位置 ，询问相当于得到 ，也就是说询问相当于得到置换环上这条边是否存在

而可以发现，我们也可以找出一些互不影响的交换，然后得到它们的询问的和

换个方式重新表述一下我们的问题：现在有一张完全图，每次询问我们可以询问一个匹配中有多少条边，还原一个置换环图

那么解决方式就比较显然了，一个完全图可以拆成 或 组匹配，我们在每组匹配上分别二分出所有边即可

询问次数 ，常数很小，可以直接通过。

---

12. QOJ10045 - Permutation Recovery [K] ⭐

题面

给定一个 的矩阵 ，按照如下方式生成：选取 个 的排列 ，将这些排列排到 的前 行，将 排到 的后 行，然后再对 每列中的元素打乱

现在给定一个 ，你需要还原任何可能的

题解

Sol

将点 向第 列中的每个数连边，不难发现由于我们加入了每个排列及其逆排列，最终这张图会形成若干条重边双向边，缩完之后我们得到的应该是一个度数为 的正则无向图，而我们要做的就是将这个图拆为若干个排列图

如果这张图是二分图，我们就知道一定可以拆成 个排列，问题就马上解决了，但这不是二分图

如果 是偶数，那么我们可以求一个欧拉回路，然后将这张图拆成两张 -正则图，递归下去做，但是 不一定是偶数

那么我们可以尝试去给每个点匹配前驱和后继，我们把每个点拆成入点 和出点 ，将一条边 拆成 ，这样我们建出来了一个 -正则二分图

但是这样有一个问题：对于一条边 ，我们有可能把 和 相互匹配，但是这样的话 之间应该有两条边，这不合法

如果我们能对这个图定向的话，也许就能匹配了。

因此我们求出欧拉回路，将所有边按照欧拉回路定向。按照上述方式建出来的图是一个 -正则图，因为每个点都有 条入边和 条出边

因此这时我们跑一个二分图边染色，就能解决所有问题了。

复杂度 或者 ，取决于求最大匹配的方式，我不知道直接跑 的二分图边染色复杂度是否正确，但好像跑的挺快。