自动搬运

查看原文

来自洛谷，原作者为

	IvanZhang2009 ?

搬运于2025-08-24 23:14:54，当前版本为作者最后更新于2025-04-26 21:29:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个题两三年前出出来的时候还是我做出来的。

翻了一下之前的题解。

除了 $n,m$ 都是奇数的情况都是简单的，直接去看 easy version 的题解即可。

不妨仅考虑 $m=3$。对于 $m>3$ 的情况，我们仿照 $m$ 是偶数的情况，我们对中间的区间求解 $m=3$，然后在每次操作都加入 $\frac{m-3}{2}$ 对 $i$ 和 $n-i+1$ 即可。

$m=3$ 时答案是 $\lceil\frac{n-1}{3}\rceil$。这个在 $n=6x+1$ 的时候是最严的（$x$ 是整数），再次只考虑 $n$ 模 $6$ 余 $1$ 因为剩下的很简单。

我们需要把 $1\sim(6x+1)$ 的所有数除了 $3x+1$ 分成 $2x$ 组，每组有三个数，且和都相等。我的思路是将这些数先分成三组：$[1,2x]$ 的数分为第一组，$[4x+2,6x+1]$ 分为第三组，剩下的是第二组。可以构造出每个三元组的三个数分别选自三个组的方案。

列出限制 $a\in [1,2x],b\in[2x+1,4x+1],c\in[4x+2,6x+1],b\neq 3x+1,a+b+c=9x+3$。

稍加变化得到：$a\in [-x+1,x],b\in[-x,x],c\in[-x,x-1],b\neq 0,a+b+c=0$。（这一步只需要把 $a,b,c$ 各自减掉一个常数）

把 $b,c$ 取反得到：$a,c\in[-x+1,x],b\in[-x,x],b\neq 0,a-c=b$。

这个形式就很好看了。这相当于我们要求一个长度为 $2x$ 的排列 $p_{1\dots 2x}$ 使得 $p_i-i$ 恰好是 $\pm [1,x]$ 的所有数。

手玩一下可以发现 $2,4,6,\dots,2x,1,3,5,\dots 2x-1$ 恰好符合条件。那么做完了。

代码找不到了。