题解：CF2147B Multiple Construction

chu_yh · 2025-09-30 17:05:23 · 题解

博客链接：link。

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

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

观察题目要求：

对于每个整数 x（1 \leq x \leq n），x 两次出现的位置之间的距离是 x 的倍数。也就是说，若 p_x 和 q_x 分别是 x 两次出现的位置下标，则 |q_x-p_x| 必须能被 x 整除。

我们将其转化为：对于每个整数 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。

提交记录。

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

::::info[AI 使用说明] 本题解并没有使用 AI。 ::::