[Easy-Medium] P12108 [NWRRC2024] Defective Script

xiezheyuan2025/4/20约 1004 字大约 5 分钟

简要题意

给定一个长度为 $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$ 个方程形如：

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)$ 。

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 9;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }
int fastpow(int x, int y){
    int ret = 1;
    for(;y;y>>=1,x=Mul(x, x)){ if(y & 1) ret = Mul(ret, x); }
    return ret;
}

const int N = 2e5 + 5;
int n, a[N], f[N], b[N];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    int ans = 0;
    for(int r=1;r<=3;r++){
        int A = mod - 2, B = mod - 1, C = Sub(a[1], r);
        for(int i=2;i<n;i++){
            int D = mod - 2, E = mod - 1, F = Sub(a[i], r);
            A = Mul(A, D);
            C = Sub(Mul(C, D), Mul(F, B));
            B = mod - Mul(B, E);
        }
        int D = mod - 1, E = mod - 2, F = Sub(a[n], r);
        f[1] = Mul(Sub(Mul(F, B), Mul(C, E)), fastpow(Sub(Mul(A, E), Mul(B, D)), mod - 2));
        for(int i=1;i<n;i++){
            A = mod - 2, B = mod - 1, C = Sub(a[i], r);
            f[i + 1] = Sub(0, Mul(Add(C, Mul(A, f[i])), fastpow(B, mod - 2)));
        }
        int t = *min_element(f + 1, f + n + 1);
        for(int i=1;i<=n;i++) f[i] -= t;
        copy(a + 1, a + n + 1, b + 1);
        for(int i=1;i<=n;i++){
            int pre = i == 1 ? n : i - 1;
            if((f[i] << 1) > a[i]) a[i] = 0;
            else a[i] -= (f[i] << 1);
            if(f[i] > a[pre]) a[pre] = 0;
            else a[pre] -= f[i];
        }
        if(all_of(a + 1, a + n + 1, [](int x){ return x == a[1]; })) ans = max(ans, a[1]);
        copy(b + 1, b + n + 1, a + 1);
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

// Written by xiezheyuan

QOJ Submission。