自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

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

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

以下是正文

简要题意

给定一个长度为 $n$ 的序列 $a$，定义 $N(i)=\begin{cases}n&i=1\\i-1&\text{otherwise}\end{cases}$ 表示 $i$ 的前一个数。

你可以进行下述操作任意次：

• 选定一个 $i\in[1,n]$，令 $a_i\gets \max(a_i-2,0),a_{N(i)}\gets \max(a_{N(i)}-1,0)$。

你需要让 $a$ 中所有数均相等，输出此时 $a_1$ 的最大值。

$T$ 组数据，$2\leq \sum n\leq 2\times 10^5,0\leq a_i\leq 10^9$。

思路

先考虑一个问题：我们如何判断一个 $r=a_1$ 是否是一个合法的解（假设 $r\neq 0$）？

不妨令 $t_i$ 表示 $i$ 被选择的次数，那么我们实际上有了关于 $t_i$ 的 $n$ 个方程，第 $i$ 个方程形如：

其中 $N'(i)$ 满足 $N(N'(i))=N'(N(i))=i$，即 $i$ 的下一个数。

上面的方程是显然的。我们只需要解这个方程，就可以得到所有 $t_i$，然后验证 $t_i\in\mathbb{N}$ 是否成立即可。

至于这个解方程，朴素的高斯消元肯定是无法通过的，不过我们发现方程结构非常简单，可以手动消元一下。时间复杂度 $O(n)$。

现在我们会判定答案，但不会求出答案。这时我们回到题目本身，题目中有一句话：求最大值。

这引导我们思考，如果 $r$ 是一组合法的解（$r$ 充分大），我们能否构造一个非平凡的另解 $r'$？事实上是可以的，我们只需要对每个数都操作一次，这样 $r'=r-3$。同样的，对于解 $r'$，如果得到 $t_i$ 中，$\min t_i>0$，则可以让 $t_i\gets t_i-1$ 来获得一个较大的解 $r=r'+3$。

于是我们得到了重要引理：

若 $r$ 是解，则 $(r-1)\bmod 3+1$ 也是解（之所以不写成 $r\bmod 3$，是因为 $0$ 是平凡解，没有考虑的价值）。

然后我们只需要枚举 $r=1,2,3$，解出 $t$，令 $f=\min t_i$，令 $t_i\gets t_i-f$ 来让答案尽可能增大，最后对所有合法的 $3f+r$ 取最大值即可。

有一个小问题，在解方程时中间结果可能很大，可以选取一个合适的质数 $p$，在有限域 $\mathbb{Z}/p\mathbb{Z}$ 计算，但选取有限域进行计算的话，无法验证 $t_i\in\mathbb{N}$，可以改为模拟题目中的过程，验证所有数是否相等。

时间复杂度 $O(n)$。

QOJ Submission。