题解：P11218 【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天

youyou $\to$ Alice，yy $\to$ Bob。

Bob 交换的列一定一黑一白，否则没有意义。

如果这一列都是黑，Alice 都选择一定最优。

如果这一列都是白，Alice 能只选一个就只选一个。这里【能】指可以使得左右连通起来。

所以最难做的是一黑一白的列。

Alice 在一黑一白的列上，要么只选黑，要么都选（选黑白）。

于是对于这些列 Alice 有两种策略：

1. 每一列都选黑白；

2. 只选黑的列数 $\ge m$。（如果只选黑的列数 $< m$，那么 Bob 可以将这些列都操作。）

于是我们需要分别计算 Alice 用这两种策略能得到的最优解。

1. 每个一黑一白列都选黑白。

这样 Bob 无法操作。

构造这样一组策略：全黑列两个都选，全白列只选第一行的，一黑一白列都选。这样每一种列的贡献分别是 $2,-1,0$。不难发现这种策略能在保证连通的情况下最优。

2. 每个一黑一白列中，只选黑的列数 $\ge m$。

Bob 会在这些只选黑的列中选 $m$ 个操作。

若我们将**所有**这样只选黑的列的贡献视为 $1$，其余列的贡献仍然不变，这样计算后得到的答案**减去 $\mathbf {2m}$** 即为真实答案。因为这 $m$ 列的贡献我们都多算了 $2$（$-1 \to 1$）。

考虑这两种做法的答案具体如何求解。

1. 如上所述，将全黑列，一黑一白列，全白列的贡献分别视作 $2,0,-1$，然后变成了[最大子段和](https://www.luogu.com.cn/problem/P1115)问题。
2. 最后减去 $2m$ 是容易的。求最初答案可以 DP。设 $f(i, 0/1/2)$ 表示考虑连通块的右端点以 $i$ 结尾，且 $i$ 这一列只选上/只选下/上下都选。转移时需要保证连通。第 $i$ 列的具体贡献上面已提。

复杂度线性。代码：

```cpp
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

int n, m;
bool g[2][N];

int solve1() {
	int res = 0;
	int sum = 0;
	int mn = 0;
	for (int i = 1; i <= n; ++ i ) {
		if (g[0][i] && g[1][i]) sum += 2;
		else if (!g[0][i] && !g[1][i]) sum -- ;
		mn = min(mn, sum);
		res = max(res, sum - mn);
	}
	return res;
}

int f[N][3];

int solve2() {
	memset(f, -0x3f, sizeof f);
	f[0][0] = f[0][1] = f[0][2] = 0;
	
	for (int i = 1; i <= n; ++ i ) {
		if (!g[0][i] && !g[1][i]) {
			f[i][0] = max(f[i - 1][0], f[i - 1][2]) - 1;
			f[i][1] = max(f[i - 1][1], f[i - 1][2]) - 1;
			f[i][2] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2])) - 2;
			
			f[i][0] = max(f[i][0], -1);
			f[i][1] = max(f[i][1], -1);
			f[i][2] = max(f[i][2], -2);
		} else if (g[0][i] && g[1][i]) {
			f[i][0] = max(f[i - 1][0], f[i - 1][2]) + 1;
			f[i][1] = max(f[i - 1][1], f[i - 1][2]) + 1;
			f[i][2] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2])) + 2;
			
			f[i][0] = max(f[i][0], 1);
			f[i][1] = max(f[i][1], 1);
			f[i][2] = max(f[i][2], 2);
		} else {
			f[i][0] = max(f[i - 1][0], f[i - 1][2]) + (g[0][i] ? 1 : -1);
			f[i][1] = max(f[i - 1][1], f[i - 1][2]) + (g[1][i] ? 1 : -1);
			f[i][2] = max(f[i - 1][0], max(f[i - 1][1], f[i - 1][2]));
			
			f[i][0] = max(f[i][0], (g[0][i] ? 1 : -1));
			f[i][1] = max(f[i][1], (g[1][i] ? 1 : -1));
			f[i][2] = max(f[i][2], 0);
		}
	}
	
	int res = 0;
	for (int i = 1; i <= n; ++ i )
		for (int j : {0, 1, 2}) {
			res = max(res, f[i][j]);
		}
	return res;
}

int solve() {
	cin >> n >> m;
	for (int i = 0; i < 2; ++ i )
		for (int j = 1; j <= n; ++ j ) {
			char c;
			cin >> c;
			g[i][j] = c - '0';
		}
	
	return max(solve1(), solve2() - 2 * m);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int c, T;
	cin >> c >> T;
	while (T -- ) cout << solve() << '\n';
	return 0;
}
```

正在渲染内容...