【题解】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;
}