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

题目描述

youyou 有一个大小为 $2 \times n $ 的网格，每个格子可能是黑色或者白色。

现在 youyou 和 yy 要在这个网格上玩一个游戏：

• youyou 先选取出一个可以为空的连通块。
• 之后 yy 可以选择网格中最多 $m$ 列，将这些列上下行的格子颜色互换。

定义一个格子集合 $S$ 为一个连通块，当且仅当 $S$ 中任意两个格子可以通过集合 $S$ 内边相邻的若干个格子连通（即四连通）。

youyou 希望最大化最终连通块中黑色格子减白色格子的数量，而 yy 希望最小化之。

现在 youyou 希望你求出：在双方都采用最优策略的情况下，最终连通块黑色格子减白色格子的数量是多少？

$1 \le m \le n \le 2\times 10^6$ .

思路历程

先考虑 youyou 的决策，最大化黑块。

也就是先占 1，最好是上下都是 1。

11 全占，10 全占对贡献没影响，只占一个贡献在 yy 还有能力反转时或只占 0 时为 -1.

但是这样发现状态带个交换列数，而且复杂度消不掉。考虑优化。

考虑已经选好了连通块，若有 $k$ 个 10 选择了占黑，则答案减去 $2\min(k, m)$ 。

发现，如果 $k<m$ ，只占一个会有 $k$ 个 -1，那我还不如全占。

如果 $k\geq m$ ，答案减去 $2m$ 。

这样 $k$ 对答案不是具体数值和决策影响，所以状态根本不用带 $k$ 。

代码

const int N = 2e6 + 5;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int a[2][N];
	int f[2][3];
	int main () {
		for (int c = read(), T = read(); T--; ) {
			memset (f, 0, sizeof f);
			n = read(), m = read();
			for (int i = 0; i < 2; ++i)
				for (int j = 1; j <= n; j++)
					scanf ("%1d", &a[i][j]);
			int ans = 0, sum = 0;
			for (int i = 1; i <= n; ++i) {
				int cur = i & 1;
				sum = max(max(2 * (a[0][i] + a[1][i] - 1), -1) + sum, 0);
				f[cur][0] = max({0, f[cur ^ 1][0], f[cur ^ 1][2]}) + 2 * a[0][i] - 1;
				f[cur][1] = max({0, f[cur ^ 1][1], f[cur ^ 1][2]}) + 2 * a[1][i] - 1;
				f[cur][2] = max({0, f[cur ^ 1][0], f[cur ^ 1][1], f[cur ^ 1][2]}) + 2 * (a[0][i] + a[1][i] - 1);
				ans = max({ans, sum, max({f[cur][0], f[cur][1], f[cur][2]}) - 2 * m});
			}
			printf ("%d\n", ans);
				
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}