111211121212222322232323333433343434444444444444

D2T1 · 2023-11-13 19:13:34 · 题解

【题解】CF1891E - Brukhovich and Exams

https://www.luogu.com.cn/problem/CF1891E

我们考虑把区间分段：若两个相邻的数不互素，中间分开；若两个相邻的数中有且仅有一个 1，中间分开。那么我们得到了两种区间：全 1 区间与无 1 区间。若两个相邻数在同一区间内，那么就在区间内考虑；否则在两个区间的交点处，归到旁边的全 1 区间考虑；若旁边两个区间都是无 1 区间，那么这两个数一定不互素，不用考虑。

首先考虑无 1 区间：设长度为 len，则有 len-1 对相邻数。显然可以先通过 \lfloor \dfrac{len-1}2\rfloor 次操作，每次答案减少 2，然后可能还剩一个，使用一次操作使得答案减少 1。

接着考虑全 1 区间：设长度为 len，分三类讨论。

• 如果两端都非 1 或 n，那么有 len+1 对相邻数。可以通过 len-1 次操作每次答案减少 1，最后一次操作答案减少 2。
• 如果有一段为 1 或 n，那么从更靠中间的点的那端开始，len 次操作每次答案减少 1。
• 否则就是 1\sim n 全部都是 1，易得答案是 n-k，特判即可。

然后现在会有若干种操作：减 2，先减若干次 1 最后减一次 2，减 1。

贪心地操作即可。

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

const int N = 1e5 + 10;
int T, n, k, a[N], ot[N], ans[N];

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &k);
        bool flg = true;
        for(int i = 1; i <= n; ++ i){
            scanf("%d", &a[i]);
            if(a[i] != 1){
                flg = false;
            }
        }
        if(flg){
            printf("%d\n", n - k);
            continue;
        }
        int le = 1, two = 0, one = 0, tp = 0;
        ans[0] = 0;
        for(int i = 1; i <= n; ++ i){
            if(i != 1 && __gcd(a[i-1], a[i]) == 1){
                ++ ans[0];
            }
            if(a[i] == 1 && a[i+1] != 1){
                int len = i - le + 1;
                if(le == 1 || i == n){
                    one += len;
                } else {
                    ot[++tp] = len;
                }
                le = i + 1;
            } else if(__gcd(a[i], a[i+1]) != 1 || (a[i+1] == 1 && a[i] != 1)){
                int len = i - le;
                two += len / 2;
                one += len % 2;
                le = i + 1;
            }
        }
        sort(ot + 1, ot + tp + 1);
        for(int i = 1; i <= two; ++ i){
            ans[i] = ans[i-1] - 2;
        }
        int ps = two;
        for(int i = 1; i <= tp; ++ i){
            for(int j = 1; j < ot[i]; ++ j){
                ans[ps+1] = ans[ps] - 1;
                ++ ps;
            }
            ans[ps+1] = ans[ps] - 2;
            ++ ps;
        }
        for(int i = 1; i <= one; ++ i){
            ans[ps+i] = ans[ps+i-1] - 1;
        }
        printf("%d\n", ans[k]);
        for(int i = 0; i <= n; ++ i){
            ans[i] = 0;
            ot[i] = 0;
            a[i] = 0;
        }
    }
    return 0;
}