自动搬运

查看原文

来自洛谷，原作者为

	dehsirehC 一个人的命运啊，

搬运于2025-08-24 22:52:06，当前版本为作者最后更新于2023-10-23 22:15:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$n$ 为质数

解法：其中一种答案序列为 $n$ 个 $1$ 或一个 $n$ ，将两者的较大值输出即可。

证明：对于一个恰好包含 $m$ 个 $1$ 的序列，它的乱斗值不超过 $f(m)=m(k-1)^2+(n-m-k)^2$ 。

容易发现上述解法的答案即为 $\max(f(0),f(n))$ 。考虑随着 $m$ 的增大 $f(m)$ 的变化规律。

根据上式容易得到当某一个 $m'$ 满足 $f(m')\ge f(m'-1)$ 时，对于任意 $m\ge m'$ 都满足 $f(m)\ge f(m-1)$ 。

换句话说，函数 $f(m)$ 是一个单谷函数，而对于它的极值，必定会在其定义域的两个极值处取到，即 $f(0)$ 或 $f(n)$ 。

$k=1$

现在我们不需要考虑 $p_i-k<0$ 的情况。感觉一下，发现 $p_i$ 越大性价比越高。

设不超过 $n$ 的最大质数为 $P$ ，如果答案序列包含 $P$ ，我们将问题递归到 $(n-P,k)$ ，否则 $p_i<P$ 。

我们首先忽略掉 $p_i$ 为质数这一条件，若一个序列存在两个数 $1\le p_i\le p_j<P-1$ ，将 $p_j\gets p_j+1$ ， $p_i\gets p_i-1$ 一定更优。

这样一直调整下去，当 $n-P+1<P$ 时，最终一定会调整到 $p=(P-1,n-P+1)$ 。

容易发现当 $n$ 比较大时， $P$ 远大于 $n-\sqrt n$ ，即 $(P-1)^2\ge (P-2)^2+(n-P)^2$ 。

具体而言 $n-P$ 的最大值取决于质数间隙，在 $n$ 取到 $10^9$ 时最大质数间隙也不过几百。

当 $n$ 比较小的时候可以暴力 DP ，但实践证明答案序列必定包含 $P$ 。

至于 $P$ 怎么找，可以直接暴力枚举，再 $O(\frac{\sqrt n}{\ln n})$ 判断是否为质数，由于质数间隙很小且跑不满，故可以通过。

顺带一提，如果 $O(\sqrt n)$ 判断是否为质数也可以通过，感觉很难卡......

正解

我们延续 $k=1$ 时的思路，找到不超过 $n$ 的最大质数 $P$ 。

若答案序列包含超过 $n-P$ 个 $1$ ，则答案序列必定为 $n$ 个 $1$ ，证明类似 $n$ 为质数时的思路。

接下来考虑答案序列中 $1$ 的数量不超过 $n-P$ 的情况，如果答案序列包含 $P$ 则依旧将问题递归到 $(n-P,k)$ 。

否则的话首先忽略掉 $p_i$ 为质数这一条件，还是按照 $k=1$ 的思路不断调整序列 $p$ 。

注意可以忽略掉 $1<p_i<k$ 时的情况，因为可以将它们调成 $1$ 使乱斗值更大。

设序列 $p$ 中有 $m$ 个 $1$ ，当 $n-m-P+1<P$ 时，最终 $p$ 除 $1$ 外仅包含 $P-1$ 和 $n-m-P+1$ 。

根据 $n$ 为质数中的思路，容易得到若 $p$ 包含 $P-1$ 时，剩下的数必定为 $n-P+1$ 个 $1$ 或一个 $n-P+1$ ， $m\ge 1$ 时矛盾。

现在我们说明了该情况下 $m$ 必定为 $0$ ，接下来考虑 $(P-k)^2$ 与 $(P-k-1)^2+(n-P-k+1)^2$ 的大小关系。

考虑当 $n\le (k-1)^2$ 时， $n^2\le n(k-1)^2$ ，即答案序列必定由 $n$ 个 $1$ 组成。

当 $n>(k-1)^2$ 时且 $n$ 比较大时，依旧由于质数间隙很小，故 $(P-k)^2$ 必定大于 $(P-k-1)^2+(n-P-k+1)^2$ 。

当 $n$ 比较小的时候可以暴力 DP ，但实践证明答案序列在这种情况下必定包含 $P$ 。