构造交互问题选讲

构造交互问题选讲

讲这个专题不只是因为构造，交互问题在赛场上更容易考了，还有一个非常重要的一点就是构造交互题往往可以与很多东西结合，考察对性质的发掘。而且往往这些题比较有意思(?，做法可能很多，让大家讨论讨论也是不错的。

构造交互类问题往往没有什么固定的模板，比较考察对于题目性质的分析能力，挖掘给定操作的性质或者结构往往是这类题的基本，通过小数据的情况推广到大数据的情况往往是这类题目的思路。

但是有很多可能有用的方法，最经典的就是调整法，考虑一种不优或者不正确的做法，然后进一步调整出正确的做法。其次是增量法，这个往往考虑增加一点东西如何构造，最有特点的就应该是倍增。

题目难度基本由易到难（但是交互构造题的难度个人差很大）。

个人认为，前8道题相对简单,欢迎来秒，我认为值得的题目会在编号后加上*。想到哪算哪。

CF1665D GCD Guess

题意

你需要猜测一个正整数 $1\leq x\leq10^9$。

在一次询问中，你可以选择两个正整数 $a \neq b$。对于这次询问，你将得到 $\gcd(x+a,x+b)$ 的结果.你最多可以进行 $30$ 次询问。

做法

考察关键性质 $\gcd(x+a,x+b) = \gcd(a-b,x+b)$ 辗转相减法，然后我们就发现 $a,b$ 由我们掌控，此外，注意到 $30$ 次操作，这提示我们用 $\log$ 次数试出 $x$,这提醒我们从低位到高位试出当前点的二进制位。

CF1174F Ehab and the Big Finale*

题意

给出一个以 $1$ 为根，大小为 $n\ \ (1\leq n\leq 10^5)$ 的树。你需要在 $36$ 次操作内找到一个隐藏的节点 $x$.你有如下两种操作：

1. d u交互库会回答节点 $u$ 与 $x$ 之间的距离。两个节点之间的距离是它们之间最短路径上的边数。

2. s u交互库会回答从 $u$ 到 $x$ 的路径上的第二个节点。你要保证 $u$ 为 $x$ 的祖先。

做法

首先次数限制为 $\log$，大概我们猜出大概算法为数剖或倍增，并且用两次操作为一组。

因为第二个操作，我们应该有一个自顶向下的做法，我们考虑优化。

注意关键性质：两个深度相同的点的路径中点为这两个点的 $\text{LCA}$。

因此我们有方法了我们先一次试出目标点深度，然后沿重链跳至深度相同的节点，随后求出路径距离，就能够求出它们的 $\text{LCA}$ 随后用一次 $2$ 操作找出应该到的轻链。

CF746G New Roads

题意

有一棵树，深度为 $t$，根为 $1$，对于每一个深度 $i$ 都有 $a_i$ 个节点，并且恰好有 $k$ 个叶子节点（不算根），问你能否还原出这棵树。

做法

我们不难想到，我们可以自底向上地去构造这棵树我们还会发现，如果一层必须添加叶子节点，那么它的上一层的节点个数必须大于这一层的节点个数，多出来的部分就是需要的叶子节点个数。特别的，最后一层的节点都为叶子节点。

这启示我们将从第一层到每一层必须需要的叶子节点个数计算出来，记作 $b_i$。那么无解的情况就很好判断了，当 $b_t > k$ 的时候就无解了。

接下来我们贪心的使用叶子节点（因为只会富余不会不够）直到上一层剩余的叶子节点等于上一层的 $b_i$ 或者当前层还剩下最后一个节点时为止（为了接收它的儿子，它不能是叶子节点）。

对于叶子节点不能占满的情况，我们分下一层的一个挂在当前节点上，这样它就不是叶子了。最后再把当前的剩下的儿子全都挂在最后一个节点上让它接盘。

最后第一层的再全连到根上，这道题就做完了，细节就是编号需要从 $2$ 开始 （因为 $1$ 是根）。

最后附一张图，是样例 $2$ 构造的：

CF1354G Find a Gift*

题意

有 $n\ (n\le1000)$ 个盒子。已知其中恰好有 $k\ (k\le \dfrac{n}2)$ 个盒子里装有真品，其余的都是假的。盒子的外观全部相同，假盒子的重量相同，真盒子重量与假盒子不同（但真盒子与真盒子之间不可能不同）。

你可以进行 $50$ 次查询，每一次你可以查询两个不相交盒子子集之间重量总和的关系。

要求找到最小的真品盒子。

思路

我们假设当先第一个盒子里面是假的,那么我们通过倍增可以用 $2\log n$ 的次数查询出盒子.

但是我们不知道第一个盒子是真是假,我们考虑随机化,我们随机 $30$ 次,每一次都是一个 $1$ 和另外一个随机盒子比较,如果出现小于,它就是真的,输出一,否则我们就认为它是假的,因为我们抽取最多有 $\frac{1}{2}$ 的概率抽到真盒子,如果当前盒子是真盒子且我们没有检测出来的概率也是 $\frac{1}{2}$ ,随机 $30$ 次失误概率就是 $(\frac{1}{2})^{30}$ 的,可以接受.

CF2134E Power Boxes*

题意

有一个未知的序列 $a_1,a_2,\cdots,a_n$，元素只能是 1 或 2，进行至多 $\left\lceil\dfrac{3n}{2}\right\rceil$ 次以下操作：

• swap x：交互库交换 $a_x$ 与 $a_{x+1}$；

• throw x：记录一个计数器 $s$，不断重复以下操作：

  • 令 $x\leftarrow x+a_x，s\leftarrow s+1$，直到 $x>n$为止。交互库会给出 $s$ 的最终值，

求出序列 $a$ 的初始值。

多组数据，$\sum n\leq1000$。

做法

次数告诉我们应该是用三次求出两个数。

从简单情况开始考虑：只有两个点,我们能够轻易求出第二个点的数，随后 swap 一下，然后就应该能求出第一个数了。

考虑推广，我们可以进行一个 $dp_{1/2,i}$ 代表当前 $a_i$ 为 $1/2$ 时的跳的步数。我们发现，当且仅当序列为 $a_i,2,1,\cdots$ 时，我们无论 $a_i$ 是什么步数都一样，否则我们试一下就可以知道 $a_i$ 的值。而上面那一种情况，我们可以与后一个一起，像求出第一二位时的方法求出来。

最坏情况三次操作试出两个数。

CF2109C3 Hacking Numbers (Hard Version)

题意

给你一个数，你需要使用加减乘除（整除）与按位求和将所有$x\ (1\leq x\leq10^9)$ 转变为给定的数（中间值不得超过 $10^{18}$），请求出最小步数并给出构造。

做法

其实可以先去做C1，C2.

本题思路 7->4->最小。

首先我们知道，除法看起来很没用，并且有一个神秘的按位加。

我们手玩按位加，发现它会使这个数下降很快，因此我们可以用这个性质过掉C1。

随后我们联想到 $3$ 的倍数的判定，随后想到 $9$ 的倍数，及 $9$ 的倍数按位求和后依旧是 $9$ 的倍数。因此我们可以先乘 $9$，随后作两次按位加就能够将任意一个数固定成 $9$,四次解决。

继续推广，但此时的方法很多，我们无法确定向哪里推广。我们注意到 $x\leq10^9$，并且形如 $99\cdots99$ 的数也有类似的性质，这启发我们将原数乘上一个 $10^9-1$.

简单证明：$x\times(10^9-1)=x10^9-x=(x-1)10^9+(10^9-1)-(x-1)$ 因为$x\leq10^9$ 因此这些位互不干扰，随后按位求和就把它们全消掉了，因此最后算出来永远是$81$,因此我们用了两步就把 $x$ 固定下来了。

我们发现当给出的数不是 $81$ 时是三步，是 $81$ 时为两步。不可能更小的原因是我们不能一步固定 $x$.

CF936C Lock Puzzle*

题意

你有一个长为 $n\ (n\leq2000)$,的字符串 $s$，你要通过若干次操作转为 $t$.

一次操作为选择一个小于 $n$ 的 $x$。设d当前字符串$p = \alpha\beta$（其中$\beta$的长度为$x$），那么这个字符串会变为$\beta^{R}\alpha$（$\beta^{R}$表示$\beta$反转后的结果）。

比如，如果当前$p=abcacb$，那么执行 $x=4$ 后$p=bcacab$，因为$\alpha=ab$，$\beta=cacb$，$\beta^{R}=baca$。

最多 $6100$ 次操作。

做法

分析性质

我们会发现，题目要求的 $6100$ 次实际上就是 $3\times n$ 次，也就是对于一位，我们要用三次将它转到正确的位置。

先分析操作，实际上就是将末尾的一段字符串翻转到开头，再继续手玩样例可以发现，这个翻转会使在里面的依旧在里面，靠外的依旧靠外。

尝试

我们再来试一试，设 $1,2,3,x,\cdots,4,\cdots$,那么我们这一步的操作是要将 $4$ 挪到 $3$ 的后面。

我们需要分析，什么时候 $4$ 能够接到 $3$ 后面，当且仅当 $3$ 为左端点，$4$ 为翻转区间的开始时用一步可以拼到一起。

那我们知道了我们的首要任务时将 $3$ 从中间挪到左边，我们发现只能先将 $x$ 之后的全部翻转过去，然后再整体反转，这样我们的序列就变成了:$3,2,1,x,\cdots,4,\cdots$ 但是这样把 $4$ 挪过去，我们发现在这段完成的区间两侧有没完成的区间，很烦。一次我们考虑怎么把这些东西搞掉。

我们发现其实并不需要将整体翻转，直接翻转一部分就可以了，也就是从 $\cdots,4,\cdots,x,1,2,3$ 可以只翻转 $4$ 之后的部分，这样就变成了 $3,2,1,x,\cdots,\cdots,4$ 那么再进行一次操作后就变成了 $4,3,2,1,x,\cdots,\cdots$ 非常好看，而且方便我们继续递推。

得到正解

但是我们只讨论了（已经排好的区域）正向的情况，得到的是反向的，因此我们在考虑一下反向的情况，类比之前的方法不难得到（其中标红的代表翻转的区间）:

$$[\color{red}3,2,1,x,\cdots,4,\cdots\color{black}] \rarr [\cdots,4,\color{red}\cdots,x,1,2,3\color{black}] \rarr [3,2,1,x,\cdots,\cdots,\color{red}4\color{black}]\rarr [4,3,2,1,x,\cdots,\cdots]$$

用了三步，并且得到的序列也是反向的，就可以直接进行递推了也就是说根本就出现不了正向的情况，最后再整体反转一下就可以了。

与此同时我们发现，第二部所翻转的数的个数就是 $4$ 在这组操作前在数组的位置，记录一下即可。

我们再看序列，中 $\cdots$ 的部分，这一部分可以根据样例手推得到，结果就是操作前 $4$ 前的 $\cdots$ 顺序不变，$4$ 后的 $\cdots$ 顺序相反。直接模拟修改即可。

对于无解，当我们向后找不到要放到这一位的字符时，就无解。

CF1205D Almost All

题意

给定一棵有 $n$ 个节点的树。你需要在树的每条边上写上非负整数，使得满足以下条件：

对于任意两个节点 $i$ 和 $j$，考虑它们之间的路径，并计算该路径上所有边的数字之和。将所有得到的和写在黑板上。要求从 $1$ 到 $\lfloor \frac{2n^2}{9} \rfloor$ 的每一个整数都至少出现在黑板上一次。

保证一定存在一种满足条件的方案。

做法

首先我们有个非常简单的方法构造出 $[1,n-1]$ 的答案,也就是进行 dfs，新加进来的点到根的距离为当前的 dfs 序,边权是好赋值的。

随后我们有一种可以构造两颗子树大小乘积的方法，就是将其中一颗子树的边权乘上另外一颗子树的大小。

我们观察到性质：$\dfrac{2n^2}{9}=\dfrac{2n}{3}\dfrac{n}{3}$,又有 $\dfrac{2n}{3}+\dfrac{n}{3}=n$，因此我们需要找到将其划分成两颗子树大小均在 $[\dfrac{n}{3},\dfrac{2n}{3}]$ 之间的节点。

通过重心的性质：每个子树大小不超过原树的一半。我们可知用重心作根是正确的。

证明：若最大子树大小大于 $\dfrac{n}{3}$,显然成立，若最大子树小于 $\dfrac{n}{3}$，则一定存在选取若干子树的加和不超过 $\dfrac{2n}{3}$，的选法。

**接下来的题目略有难度,**这些题目往往不止一种关键性质，可能需要很多有用的观察和细致的实现，但往往都是一环套一环，只要能够耐心将题目分析下去往往都可以得到结果。对代码实现能力可能会有些要求。

CF566E Restoring Map

题意

有一颗树，给出了每个节点距离小于等于二的所有节点，要求找到一颗可行的树。$n\leq1000$

思路

我们先观察特殊结构：

在本图中，一号和四号节点的交集为 $\{2,3\}$ 而二三号点之间有连边。五号点和三号点同理。

我们发现我们可以通过判断两个集合的交集来推断出所有非叶子节点之间的连边。

我们可以用bitset维护交集，这样时间复杂度就是 $O(\dfrac{n^3}\omega)$ .

接下来考虑叶子节点，我们怎么找到一个叶子节点的父亲，我们发现，如果当前叶子包含了所有与这个点距离为1的点而没有包含与这个点距离为2的点，那么这个叶子的父亲就是这个点。具体实现我们可以标记这个叶子节点中非叶子节点的编号，随后所有的点都push一步，被覆盖个数最多的即为这个叶子节点的父亲。在或者就是发现

此时我们发现上面这个做法依赖一个非叶子节点距离为2的非叶子节点，即非叶子节点个数至少为3.我们还需要特判非叶子节点个数小于三的情况。我们一步一步来分析。

当非叶子个数等于 $0$ 时，只有 $\leq2$ 个节点，特判即可。

当非叶子个数等于 $1$ 时，此图将是一个菊花，此时所有点集均相同，特判即可。

当非叶子个数等于 $2$ 时，此图将形如：

我们发现中间的边依旧可求，剩下的叶子节点形成了不相交的两部分，一部分放左，一部分放右即可。

CF1770H Koxia, Mahiru and Winter Festival*

题意

给定排列 $p$ 和 $q$。有一张 $n\times n$ 的网格图，$(i_1,j_1)$ 和 $(i_2,j_2)$ 有边当且仅当 $∣i_1−i_2∣+∣j_1−j_2∣=1\ (1\leq i_1,i_2,j_1,j_2\leq n)$。你需要构造 $2n$ 条路径，第 $i$ 条从 $(1,i)$ 到 $(n,p_i)$，第 $i+n$ 条从 $(i,1)$ 到 $(q_i,n)$，使得被路径覆盖次数最多的边被覆盖的次数最少。

数据范围：$n\leq200$。

思路

我们先考虑最简单的情况，就是 $p,q$,均为顺序的排列时我们答案一定为一。直接顺连即可。

我们可以证明这是唯一一种答案为一的情况，因为它将所有的边都覆盖了一次，而其余的情况要覆盖的边数只增不减。

我们考虑最劣的情况（即所需要覆盖的边数最多的情况），此时所有的 $p,q$ 均为逆序。我们有一种构造方式，如图。其中一个为行一个为列（ps:红色为走了两次的边,路径不全讲课的时候手画)。

我们猜测其它所有的方案一定都不比这个劣，因此我们考虑在这个构造方案上进行调整。

我们行列分开，在上图中的列，我们发现，交换相邻两个目标，就是交换一下他们交点之后的位置（并且我们发现每个点都有交点）。

行类似，但是稍微要比列简单一点。

此外，在本题的官方题解中，还有一种增量法的构造方式，sol是中文的，推荐大家看一看。

一道模拟赛题*

题意

这是一道交互题。

你有一个机器人，它被设定了一个长度为 $n\ (n\leq60)$ 的指令，这个指令由字母 D 和 R 构成。你想猜这个指令是什么。每次你能给机器人一个 $(n+1)\times(n+1)$ 的地图 $g$，机器人一开始在左上角 $(0,0)$ 的位置。如果 $g_{i,j}=1$，表示 $(i,j)$ 为障碍格，否则为可通行的。

机器人会按顺序去执行这个指令。如果指令的下一位为 D，机器人会尝试从 $(x,y)$ 走向 $(x+1,y)$。如果为 R，会尝试走向 $(x,y+1)$。如果对应的位置为障碍格，机器人会停在原地。

机器人会告诉你，执行完这个指令之后，它会停在什么地方。你想通过若干次交互得到指令。

交互次数小于 $21$。

思路

第一步是容易想到用一步试出有多少个向下和向右。

此时有一个简单的构造就是将我们的机器人控制在第一行，然后在某个位置开一个口，这样就能试出这一行有多少个向右，精细实现为 $\min(x,y)$ 的，但是没有什么优化空间。（我考场上试图优化这个，做出来的我请他喝奶茶（

我们还容易想到一种构造方式：

形如这样的构造，可以一步试出至少一个向右/向下（也就是这个构造后的结果与最终点的坐标差），最坏情况一步试出两个指令。所以最坏次数为 $30$,感觉有优化空间。

我们考虑优化。

我们发现，当前这个做法最坏的情况就是这个东西不碰壁，这样我们无法试出更多的东西。所以我们试图让这种情况试出的数更多。

所以我么把它们翻倍，此时不碰壁的情况我们一次可以试出四步，如果碰壁次数超过两次，我们考虑这个操作序列形如：$$\text{R}^x\text{D}\text{D}^y\text{R}\text{R}^z\text{D}\text{D}^w\text{R}$$ 其中我们知道 $x,z$ , $y,w$ 的和。总共操作次数大于六，我们可以再用一次操作试出 $x,y$ 然后就能够得到 $x,y,z,w$ 的值。此时我们用两次知道了至少六步，符合条件。

但是还有一个例外情况就是碰壁次数为一次的情况，此时总步数为五步，用两次操作check显然不满足要求。我们先放一放。

加假如我们确定了所有的除了一次碰壁的情况，我们考虑统一处理这些。

蓝色为两个拥有碰壁一次的操作染的点，红色为新一次查询为障碍的点。我们发现，我们可以用这种方法试出在哪个位置向下，哪个位置向右（手动枚举可发现）。同时我们也可以用这个判定两个向下的情况。我们用了三次操作试出了 $10$ 步，因此满足条件。

于是我们这题就做完了。

funfact:这场模拟赛赛时本题无人AC。有很多比较厉害的人都没做出来（

P8374 [APIO2022] 火星

题意

有一个隐藏的 $(2n+1)\times(2n+1)$ 的 $01$ 地图。你有一个大小为 $(2n+1)\times(2n+1)$ 的寄存器，其中每一个格可以存储 $100$ bit的信息（即长度为 $100$ 的 $01$ 串），初始时每个寄存器最低位存的是地图，在一轮操作中，你将按从左到右，从上到下的顺序依次查看 $3\times3$ 的寄存器并可以修改这个寄存器左上角的信息。

在一轮操作后，可“看见”的寄存器的边长会减二。

如图，第一轮依次调用这些寄存器，绿色为可以被访问，蓝色为可以修改。

而第二轮只会调用这一个寄存器。

你的目标是要计算出这个地图中的 $1$ 连通块个数，并在最后一轮中存在蓝色区域中。

注意：因为是通信题，因此你不能使用全局的变量来存储什么东西 。

$n\leq20$

思路

好玩，但是史。

因为只有蓝色的部分可以修改，因此我们直接bfs是不太现实的。

考虑到每一论边界会向里收缩 $2$,因此我们考虑维护收缩的部分的答案。

对于深绿的点我们存储这一行/列与后面的地图（不是连通性）对于深红的点，我们维护那一行和一列的连通性和浅红区域的答案。

如何维护连通性：考虑类似插头DP维护联通性，我们可以用括号序列来表示这个节点的连通性。

我们将一整个连通块划分成若干个匹配的括号，一个连通块最左端的点标记为(中间每个节点记为)(一个连通块最右端的点记为) ，(连续的段我们不记录，或者说只记一个)，我们可以用2bit表示一个节点的连通性，所以我们发现记录信息最多的左下角的深红节点记录的陆地个数为 $\dfrac{2(2n-1)}2=2n-1$ 个（因为我们不记录连续段和0），此时记录这些信息最多需要 $2(2n-1)=78$ bits，加上我门统计连通块个数的 $\log_2(\dfrac{(2n+1)^2}2)\leq2^{10}$ $10$ bits,我们需要 $88$ bits,有空余。

我们来考虑转移，边上的是好转移的，直接加上新的四个值即可，最重要的是左下角的转移我们从可以解码出

图中绿色区域的地图情况，然后我们还知道上上图中红色部分的联通情况，可以使用并查集实现。统计答案是容易的。

P12542 [APIO2025] 排列游戏 *(部分分)

题意

你有一个排列和一个简单连通无向图，你每一次操作需要给这个图的顶点标号，然后交互库会交换任意一对排列中以 图中相邻节点 为下标的节点。你希望是这个排列“归位”的点（即$p_i=i$）的点尽可能多，交互库希望尽可能少，你需要给出最多可以多少个并在 $3n$ 步内($n\leq400$ 为排列长度)达到它。

部分分：$e,m\ m\leq n$ 分别为图的边数和点数。

1. (6 分) $m=2$

2. (6 分) $e>m$

3. (10 分) $e=m−1$

4. (24 分) $e=m=3$

5. (24 分) $e=m=4$

6. (30 分) $e=m$

思路

本题最善良之处在于它的部分分提示性很强，我们跟着它的部分分一步一步来看。

首先看到排列，容易想到转为置换环，我们的目标就是希望分离出尽量多的大小1的置换环。

m=2

这个相当于我们可以任意交换选定的两个点，用这个归位所有的数是容易的。

e>m

这种情况好像有很多，那为什么只有6pts，显然这类的情况很简单。手玩阳历并加以分析，发现一个置换环上只有它指向的和指向它的边各一条。如果图上有度数大于等于三的点，其中必定有一个点与这个点无关，交互库可以耍无赖只交换这一个点你就寄了。因此最好的方案就是不动，立刻结束。

e=m-1

因为我们把所有度数大于三的情况全部判完了，因此我们这种情况只有链一种。

我们考虑从大的置换环上扣大小为 $1$ 的置换环，有两种情况：当前置换环大小大于 $m$，和小于 $m$,这对应两个操作。

如果当前环的大小大于等于 $m$ ，我们可以在这个环上放链，交互库只能交换一个相邻的点因此一定会归位一个点，然后那个环的大小减一。为了方便，我们称其为“强制归位”,简称归位。

如果当前环的大小小于 $m$，我们必须那其他环上的点放在这个链上，交互库也一定会交换这两个环之间的边，这个操作体现在环上就是两个小环合并成了一个大环。我们称其为“强制合并”,简称合并。

我们发现，最后只会剩下 $m-1$ 个点没有被归位，也无法归位。

22pts就这么到手了，易如反掌啊，离正解还远吗

e=m=3

此时的情况为三元环。

我们发现为环的时候我的强制归位的手法只能用在大小为 $m$ 的置换环上。如果这个置换环的大小大于 $m$，交互库可以交换环上不相邻的两个点来划分出 $m-1$ 的环，而非归位一个点。

我们考虑如何从一个大环上扣下来一个长度为 $3$ 的小环，感觉不太可做，我们先考虑如何从大环上扣下来一个大小为 $2$ 的小环，这个是好做的。

所以对于所有奇环，我们都可以扣掉 $2$ 的小环来做到归位一个点。对于偶环呢？我们好像什么都做不了。

所以答案就是奇环的个数。次数是对的。

46pts就这么到手了，易如反掌啊，离正解还远吗

e=m=奇数

我们先来考虑奇数的情况如何推广。（因为偶数的更难）

首先我们考虑能否扣下来一个大小为 $2$ 的环，我们发现是可以的：我们可以构造跳两步跳两步，到一半之后再跳一步，折返，往回跳两步跳两步。如图，左边 $m$ 为偶数，右边为奇数。

我们似乎分析出了一种思路：我们将大环分成不是 $d$ 就是 $1$ 步，这样它就只能要么然归位一个点，要么然拆出一个 $d$。我们称其为“$d$强制拆分”，简称拆$d$。（注意这个需要特殊构造）

回到奇数的情况，我们考虑像上一个情况一样，将大奇环削成 $m$ 然后归位，对于偶环，我们一定能找到一个位置分成两个偶环，因此依旧无解。

有一个corner case:最大奇环小于 $m$，此时我们为了不影响答案，我们优先合并偶环，如果合并了偶环依旧小于，我们将挑选两个奇环进行合并并将答案 $-2$，可以发现，如果我们构造出了 $m$ 环，归位后变成 $m-1$ 偶环，随后合并奇环可以直接再次使用。

我们会发现 $m+1$ 个点是无法操作的，就死局了。

好了，我们现在只剩下偶数的情况了。离正解还远吗

e=m=4

我们先回到部分分，事情开始变得不对劲。

首先归位的条件没有改变，拆$2$依旧好用。

我们考虑死局的情况：

当剩余 $5$ 个点的时候，我们只能把它们拆成 $2$ 和 $3$，也是死局。

但是我们发现，对于两个 $2$ 可以合成一个 $4$,两个 $3$ 可以合成一个 $6$,好像又可以重复利用了。

好像依旧可做，但是我们的操作次数就有点危险了。我们试试看能不能直接拆4.

我们发现是可以的。具体就是 $1,5,6,2$,距离 $+4.+1,-4.-1$，容易发现这个是合法的。

所以所有大于 $6$ 的环我们都可以直接拆下来一个四。

整理以下：

1. 若有4环，可以归位

2. 最大环长大于等于 $6$ ，可以拆4。

3. 对于 $5$ 环，需要合并下一个环。

4. 对于 $2$ 环，需要合并下一个 $2$环。三环类似（即不合并 $2,3$ 环）。

我们发现最多三步就可以归位一个点。那么总操作次数是合理的。

70pts就这么到手了，离正解还远吗

e=m=偶数

我们根据上面的那组构造，我们可以推广出一组拆法：$1,1+m,2+m,\cdots,\dfrac{m}2+m,\dfrac{m}2,\dfrac{m}2-1,\dfrac{m}2-2\cdots,2$

这组拆法的距离大致长成 $m,1,1,1,1,-m,-1,-1,-1$ 显然正确。

由此我们可以从所有大于 $\dfrac{3m}2$ 的环上拆 $m$，而对于小于它的环我们还需要另想办法。

因为最大环长被限制住了，因此我们可以考虑继续使用奇数时的拆分方法：

对于 $m+2,m+4,m+6\cdots$ 的情况，我们可以拆2.

而对于 $m+3,m+5,m+7\cdots$ 我们不能直接拆2变成 $m+1$（这样就真废了）,我们需要考虑一种拆3的方法（或判断无解）

事实上，我们在为偶数时确实有一种构造方法。（事实上，我感觉这一部分可以试图写一个搜索）

就是先用向前跳 $1$ 到 $m-i\equiv 0 \bmod3$ 的位置（注意下标从一开始），然后一步跳三，随后我们再向回跳 $-1 ,-3,+1,-3,\cdots$ 这样就能拆3.

我们发现这样构造可以到达上界 $m+1$，好像确实是最优解了。但操作次数够吗？

我们整理一下操作：

1. 有 $m$​ 环，归位。

2. 如果有两个环长和为 $m$,合并。

3. 有 $\geq\dfrac{3m}2$ 环，拆 $m$.

4. 有 $m+2\leq\ \leq\dfrac{3m}2$ 环，拆2/3。

5. $m+1$ 环合并次小环

6. $\leq m$ 环合并次小环，尽量别合并出 $m+1$，即如果能和出 $m+1$ 合并次次小环。

我们发现如果使当前最大环只能和出 $m+1$，我们就寄了，形如：$m-1,2,2,2,2,\cdots$

我们需要两次合并出 $m+3$，随后拆3归位，再合并出 $m+2$，再拆2归位

我们用七次操作归位两个点，归位一个点要 $3.5$ 次操作，死了。

优化

我们追忆 $m=4$ 的时候是怎么做的。此时的 $m-1$ 就相当与 $3$，我们将 $2$ 与 $2$ 进行合并，这样就避免了将 $2$ 与 $3$ 进行合并。

同理，我们可以用上面的方法，如果最大环为 $m-1$,那我们就先去合并次大环和次次大环。

但这依旧有问题，如果次大环也为 $m-1$ 就不好办了，但是我们发现，此时合并最大环和次大环，我们用三步归位一个点的同时，创造出了一个 $m-2$，这个可以与 $2$ 合并成一个环，这只用了两步归位一个点，这是好的。并且可以和 $3,m-1$ 用五步归位两个点，这也是好的。

这使我们想到要保留一下 $m-2$,于是整理一下得：

1. 有 $m$ 环，归位。

2. 如果有两个环长和为 $m$,合并。

3. 有 $\geq\dfrac{3m}2$ 环，拆 $m$.

4. 有 $m+2\leq\ \leq\dfrac{3m}2$ 环，拆2/3。

5. $m+1$ 环合并次小环

6. 最大环 $=m-1$ 看次大环

   1. 若为 $m-1$ 直接合并
   2. 若为 $m-2$ 最大环合并次次大环（如果有 $2$ 环就已经在第2步判掉了）
   3. 若小于 $m-2$ 将次大环与后面的环顺次合并

7. 若最大环小于 $m-1$ 直接向后顺次合并。

分析一下操作次数：

首先，绝大部分最多三步归位一个点是没有问题的，我们需要归位 $n-m$ 个点，因此我们可能还有 $3m$ 的多余的步骤。

最开始的合并，最大环小于 $m-1$ 的合并不超过 $m$ 次（准确说会更少）。

在剩余点大于 $2m$ 之前一直都可以维持三步归位一个点（拆3可以五步归位两个点，拆2可以两步归位一个点，因此我们从第四步拆下来的二三环都可以摊掉，注意这里的重复利用）。

在环长小于 $2m$ 时，我们的算法就退回了原先 $3.5$ 一个点的方法，但是此时我们需要归位的点只有 $m$ 个，因此我们只多余出了 $0.5m$ 的步骤，这个是我们可以接受的。可能还有一部分的四操作无法摊掉，因此可能有 $0.5m$ 的拆2/3.

因此我们最后还至少有 $m$ 的空余。这题就做完了。

最后一步细节就是注意拆2/3时，尽可能拆3,因为拆2出n-1后还需要合并两个2.

到这里剩下的代码就是大模拟了。