题解：CF2147B Multiple Construction

博客链接：link。

在很多同学心目中构造题一直很扑朔迷离，所以本题解着重讲答案的推导过程。

明显需要按某种特定顺序构造，又因为是 B 题，所以不会太复杂。因此，用可视化工具验证合法性就对快速解题很有帮助了。

观察题目要求：

我们将其转化为：对于每个整数 $x$ 两次出现的位置之间的距离是 $kx$，其中 $k$ 是正整数。那么两个 $x$ 夹着的数的个数必须是 $kx-1$。这样就发现题目要求其实是在对两个 $x$ 中间的数的个数做要求，可以想到合法数列应存在一定的嵌套结构，这里嵌套结构就是按一定方法把两个相同整数加到两侧并保持合法。容易想到尽量多的 $x$ 的 $k$ 相同时易构造简洁且合法的嵌套结构。

设两个数 $x,y$，满足 $x+1=y$ 且 $y\le n$。我们不妨假设 x a x 已经是个合法结构了，这里的 a 表示一个合法数列，长度为 $k_1x-1$。两个 $y$ 中间需要夹 $k_2y-1=k_2(x+1)-1=k_2x-1+k_2$ 个数。跟据上文的思考，我们不妨试着使 $k=k_1=k_2$ 来简化问题。若把已有的 x a x 夹到两个 $y$ 里面。那么 $y$ 中还需要夹 $(kx-1+k)-(kx-1+2)=k-2$ 个数，这时就很容易发现当 $k=2$ 时就可以把两个 $y$ 直接加到 x a x 两侧得到形如 y x a x y 的合法数列。对 y x a x y 进行扩展，可联想出形如 m−1 m−2 ... 1 x 1 2 ... m−1 的合法结构，其中 $x$ 表示任意大于等于 $m$ 的整数。

然后再思考 $x$ 处填什么，另一个 $x$ 放哪里。取上面结构的一半（即 x 的左侧或右侧）： m−1 m−2 ... 1 或 1 2 ... m−1 ，发现其长度都为 $m-1$，当 $k_m=1$ 时可以被合法地夹在两个 $m$ 里。所以可以用 $m$ 替换 $x$，并把另一个 $m$ 放在的该结构左边或右边得到 m m−1 m−2 ... 1 m 1 2 ... m−1 或 m−1 m−2 ... 1 m 1 2 ... m−1 m 这一合法结构。

可以贪心地想让 $m$ 尽可能大，且最大时 $m=n$。于是最终合法的构造为 n n−1 n−2 ... 2 1 n 1 2 ... n-2 n−1 或 n−1 n−2 ... 2 1 n 1 2 ... n-2 n−1 n。

提交记录。

以此题为例，我们可以找到简单构造题的通用思路：可以钦定已有一种部分合法方案，在思考将该方案可以如何拓展，从而到一种合法模板或直接得到最终答案。