526互联

AtCoder Regular Contest 109 F 1D Kingdom Builder

发布时间 2023-04-20 13:30:30作者: zltzlt

洛谷传送门

AtCoder 传送门

考虑判断一个终止态是否可达。如果只有一个棋子连续段那一定可达；否则就存在 \(\ge 2\) 个连续段。此时把放棋子看成删除，那么限制就是如果删除一个孤立的棋子（两边没有棋子）且还有别的格子有棋子，这个棋子的颜色 异于其他连续段的两边棋子的颜色 。

设第一个被删的段（最后一个放棋子的段）的最后一个棋子颜色为 \(c\)，记其补色为 \(c'\)。想删掉这个棋子就必须把其他连续段删成两边都是 \(c'\)。借这个机会可以把所有包含 \(c\) 的段都删除，剩下的段只会包含 \(c'\)。这样的段最多只有一个（多了就寄了），所以这个段就是最后被删除的段（第一个放棋子的段）。

可以发现删棋子和放棋子的方案是一一对应的，所以“存在一个合法的删棋子方案”就是“存在一个合法的放棋子方案”的充要条件。

考虑枚举 \(c\)，那么根据以上讨论有如下限制：

  • 第一个被删的段必须包含子序列 \(c\)。
  • 最后被删的段 和它两边 必须包含子序列 \(c'c'\)。
  • 其他段 和它两边 必须包含子序列 \(c'cc'\)。

考虑左边和右边扩充 \(3\) 位后大力 dp。设 \(f_{i,0/1,0/1}\) 表示钦定 \(i\) 不放棋子，当前是否存在 第一个被删的段 ，当前是否存在 最后被删的段 ，放棋子数量的最小值。转移大概是如果 \(i-1\) 不放棋子就是 \(f_{i,x,y} \gets f_{i-1,x,y}\)，否则枚举 \(i-1\) 所在段的左端点，考虑这一段是第一个被删的段、最后被删的段还是其他段。

直接做是 \(O(n^2)\) 的，考虑优化。容易通过子序列自动机找到以 \(i-1\) 为右端点的第一个合法的左端点，并且发现能转移的点是一段前缀。分三类记一下前缀最小值即可。这样是 \(O(n)\) 的。

code 
// Problem: F - 1D Kingdom  Builder
// Contest: AtCoder - AtCoder Regular Contest 109
// URL: https://atcoder.jp/contests/arc109/tasks/arc109_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;

int n, a[maxn], b[maxn], pre[maxn][2];
int f[maxn][2][2], fa[2], fb[2], fc[2][2];
char s[maxn], t[maxn];

inline int work(int c) {
	mems(f, 0x3f);
	mems(fa, 0x3f);
	mems(fb, 0x3f);
	mems(fc, 0x3f);
	f[1][0][0] = 0;
	for (int i = 2, ja = 1, jb = 1, jc = 1; i <= n; ++i) {
		if (b[i]) {
			continue;
		}
		while (pre[i + 1][c ^ 1] && ja <= pre[pre[i + 1][c ^ 1] - 1][c ^ 1]) {
			for (int x = 0; x <= 1; ++x) {
				fa[x] = min(fa[x], f[ja][0][x] - ja);
			}
			++ja;
		}
		while (jb < pre[i][c]) {
			for (int x = 0; x <= 1; ++x) {
				fb[x] = min(fb[x], f[jb][x][0] - jb);
			}
			++jb;
		}
		while (jc <= pre[pre[pre[i + 1][c ^ 1]][c]][c ^ 1]) {
			for (int x = 0; x <= 1; ++x) {
				for (int y = 0; y <= 1; ++y) {
					fc[x][y] = min(fc[x][y], f[jc][x][y] - jc);
				}
			}
			++jc;
		}
		// printf("i: %d %d %d %d\n", i, ja, jb, jc);
		f[i][0][0] = min(f[i - 1][0][0], fc[0][0] + i - 1);
		f[i][1][0] = min(f[i - 1][1][0], min(fc[1][0], fa[0]) + i - 1);
		f[i][0][1] = min(f[i - 1][0][1], min(fc[0][1], fb[0]) + i - 1);
		f[i][1][1] = min(f[i - 1][1][1], min({fc[1][1], fa[1], fb[1]}) + i - 1);
		// printf("i: %d %d %d %d %d\n", i, f[i][0][0], f[i][1][0], f[i][0][1], f[i][1][1]);
	}
	return f[n][1][1];
}

void solve() {
	scanf("%d%s%s", &n, s + 4, t + 4);
	for (int i = 4; i <= n + 3; ++i) {
		a[i] = (s[i] == 'b');
		b[i] = (t[i] == 'o');
	}
	a[n + 4] = a[n + 5] = a[n + 6] = 1;
	n += 6;
	pre[1][0] = pre[1][1] = 0;
	for (int i = 2; i <= n + 1; ++i) {
		for (int j = 0; j <= 1; ++j) {
			pre[i][j] = pre[i - 1][j];
		}
		pre[i][a[i - 1]] = i - 1;
	}
	int l = -1, r = -1;
	for (int i = 1; i <= n; ++i) {
		if (b[i]) {
			if (l == -1) {
				l = i;
			}
			r = i;
		}
	}
	printf("%d\n", min({r - l + 1, work(0), work(1)}));
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}