洛谷P8940 [SSOI 2023 easy Round] C. 不见故人题解

题目链接：P8940 [SSOI 2023 easy Round] C. 不见故人

题意：

给定 $n, k$ 和序列 $\{a_n\}$，你同时有一个临时变量 $x$，你可以进行以下操作若干次（也可以是 $0$ 次），一次操作的流程是：

选定一个区间 $[l,r]$，$\forall i\in[l,r]$，$x\leftarrow \gcd(a_l,a_{l+1},\cdots,a_r)$。

$\forall i\in[l,r]$，$a_i\leftarrow x$。

简而言之，你每次可以选定一个区间并将其中每个数变成这个区间的 $\gcd$。

一次操作的代价是 $r-l+1+k$，现在你希望把这个序列的每个数都变成相等的，求最小代价和。

输入格式：

第一行两个非负整数 $n,k$。

第二行 $n$ 个数，表示 $\{a_n\}$。

输出格式：

一行一个数，表示答案。

数据范围：

对于所有数据，保证 $1\leq n\leq 4\times 10^6$，$0\leq k\leq 10^9$，$1\leq a_i\leq 10^9$。

感觉这道题在各方面都非常有迷惑性，其实非常简单

这个 $k$ 的数据范围不禁让人怀疑，这个题跟 $k$ 有什么关系？

在这之前，我们先明确一个非常显然的性质：最终所有的数一定为 $c=\operatorname{gcd}\left(a_1, a_2, \ldots, a_n\right)$ 。

容易发现，$k\ge n$ 时，我们做任何多余操作都是浪费的，因此我们直接一步到位，答案就是 $n+k$ 。

接着考虑当 $k < n$ 时有什么影响。可以发现，每个数至多修改一次，否则一定不优。

那么我们就可以将原数组视为被连续若干个 $c$ 分隔的若干个需要修改的段。

这些段会通过吃掉隔壁的某个 $c$ 以完成修改，也可能直接与另一个段（包括中间的分隔段）合并以完成修改

可以明确的是，当分隔段长度小于 $k+1$ 时，它应当与两侧的修改段合并。

另外，即使长度没问题，如果两侧的修改段都有对它的要求（吃掉一个 $c$ ），它也应当与两侧的修改段合并。

然后这题就做完啦！（~~插图纯属无端联想~~）

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
int gcd(int a,int b) { return b == 0 ? a : gcd(b, a % b); }
#define N ((int)(4e6 + 15))

int n,k,tot,a[N],l[N],r[N],d1[N],d2[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int c = a[1];
    for(int i = 2; i <= n; i++) c = gcd(c, a[i]);
    for(int i = 1; i <= n; i++) if(a[i] == c)
    {
        if(a[i - 1] != c) l[++tot] = i;
        if(a[i + 1] != c) {
            if(l[tot] != 1 && i != n && i - l[tot] + 1 <= k) --tot;
            else r[tot] = i;
        }
    }
    if(l[1] == 1 && r[1] == n) return cout << "0\n", 0;
    for(int i = 1, L = 1; i <= tot; i++)
    {
        if(l[i] == 1) { L = r[i] + 1; continue; }
        int g = a[L];
        for(int j = L + 1; j < l[i]; j++) g = gcd(g, a[j]);
        if(g != c) {
            if(d1[i - 1] && r[i - 1] - l[i - 1] + 1 == k + 1) {
                d2[i - 1] = 1; continue;
            }else d1[i] = 1;
        }
        L = r[i] + 1;
    }
    if(r[tot] < n)
    {
        int g = a[r[tot] + 1];
        for(int i = r[tot] + 2; i <= n; i++) g = gcd(g, a[i]);
        if(g != c) d2[tot] = 1;
    }
    int res = n, cnt = 0;
    for(int i = 1; i <= tot; i++) if(!(d1[i] && d2[i])) {
        for(int j = l[i] + d1[i]; j <= r[i] - d2[i]; j++) --res;
        if(l[i] != 1 && r[i] != n) ++cnt;
    }
    cout << res + k * (cnt + 1) << '\n';
    return 0;
}