[Easy-Medium] P12108 [NWRRC2024] Defective Script
xiezheyuan
·
·
题解
简要题意
给定一个长度为 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 的最大值。
### 思路
先考虑一个问题：我们如何判断一个 $r=a_1$ 是否是一个合法的解（假设 $r\neq 0$）？
不妨令 $t_i$ 表示 $i$ 被选择的次数，那么我们实际上有了关于 $t_i$ 的 $n$ 个方程，第 $i$ 个方程形如：
$$
r=a_i-2t_i-t_{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](https://qoj.ac/submission/987186)。