题解：P12356 「HCOI-R2」Rabbit Panic (Hard Ver.)

· · 题解

验题人题解（？过了半年才写。

建议降蓝。。

先特判 n=1 操作 0 次、m=1 无解。

然后对于 m 为偶数，容易想到一个显然的构造且能顶到次数的理论下限，从两侧开始每次分别对称地选择一段，最后多余的选择之前操作过的不会影响平均数。

对于 m 为奇数，n 为偶数时最终平均数需要是 \frac{n+1}2，而无论进行什么操作，得出的数都一定是 \frac{p}{m^k},p\in\mathbb{N^+},k\in\mathbb{N} 的形式，所以一定无解。

都是奇数时，如果沿用以上的做法每次操作时都把 \lceil{\frac{n}2}\rceil 选上，达不到理论下限且事实上确实不够优。

考虑手玩 m=3 找规律输出方案。

类似于 1 5 6，2 3 7 的我们可以花费两次操作完成 6 个。以 n=6k+1,k\in \mathbb{N_+} 的情况为例，i、3k+i+1、6k-2i+2 和 k+i、2k+i、6k-2i+3 都能得到 3k+1，且没有重复。

那么除 \lceil{\frac{n}2}\rceil 外最后会剩下 2 个或者 4 个，可以一开始预留出两边对称的 2 个或者 4 个，这样最后也是选他们中对称的两个和 \lceil{\frac{n}2}\rceil 一起。虽然会有重复操作但一定能顶到理论下限 \lceil\frac{n-1}3\rceil。

发现 m>3 可以用多余的 m-3（偶数）个位置把左右最边上的部分对称消掉，于是做完了。