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