比赛：Educational Codeforces Round 189 (Rated for Div. 2) · 题目链接：C. Red-Black Pairs

题目大意

题面

有一张 $2 \times n$ 的格子表，每个格子涂红色 ® 或黑色 (B)。要重涂最少多少个格子，使得能把全部格子分成 $n$ 对，满足：

每对两个格子同色
每对两个格子 共边相邻

输出最少重涂次数。

输入格式

第一行 $t$ （ $1 \le t \le 10^4$ ）组测试。

每组：

第 1 行： $n$ （ $1 \le n \le 2 \cdot 10^5$ ）
第 2、3 行：长度为 $n$ 的字符串，描述上下两行的颜色

约束： $\sum n \le 2 \cdot 10^5$ 。

样例

输入：

5
1
R
B
2
BR
BR
3
RBR
BRB
4
RRBB
BBRB
5
RBRBR
BBBRB

输出：

第 4 个样例一种合法重涂是

1
2

RRBB
BBRR

思路讲解

一句话

每对配对就是一块 $1 \times 2$ 的多米诺骨牌； $2 \times n$ 网格用骨牌完整铺满只有两种局部砖型——整列竖砖 或 相邻两列上下各一块横砖。线性 DP 一遍扫过去就行， $O(n)$ 。

关键观察：配对结构 ≡ 2×n 多米诺铺法

题目要求「每对同色且相邻」。把「相邻」这一几何约束抽出来看，每对就是一块 $1 \times 2$ 的 多米诺骨牌。问题立刻翻译成：

把 $2 \times n$ 的网格用 $n$ 块 $1 \times 2$ 多米诺骨牌完全铺满。每块骨牌覆盖两个格子，要求两格同色——不同色就重涂一格，cost = 1。

而 $2 \times n$ 网格的多米诺铺法是经典结构：任意一种铺法，每一列要么是一块整列竖砖，要么和相邻列形成「上下两块横砖」的组合。

横砖一定 成对出现——上行的横砖跨第 $i$ 到第 $i+1$ 列时，下行同 $i$ 到 $i+1$ 列也必须放一块横砖；不能上行横、下行竖混搭，否则下行第 $i$ 列就剩一个孤立格子接不上。

殊途同归地，原题的「重涂使可配对」就成了：枚举所有 2×n 多米诺铺法，选总 cost 最低那一种。铺法数线性可枚举，于是 DP。

DP 转移

设 $\mathrm{dp}[i]$ = 前 $i$ 列已经合法铺完的最少重涂次数。两种转移：

1) 第 $i$ 列放整列竖砖：cost = (上下两格不同色 ? 1 : 0)

\mathrm{dp}[i] \;=\; \mathrm{dp}[i-1] + \bigl[\,s_0[i] \ne s_1[i]\,\bigr]

2) 第 $i-1, i$ 两列各放一块横砖（上下行各一块）：上行 cost + 下行 cost

\mathrm{dp}[i] \;=\; \mathrm{dp}[i-2] + \bigl[\,s_0[i-1] \ne s_0[i]\,\bigr] + \bigl[\,s_1[i-1] \ne s_1[i]\,\bigr]

两种转移取 min。边界 $\mathrm{dp}[0] = 0$ （空网格已铺好），答案 $\mathrm{dp}[n]$ 。

验证：样例 5

$n = 5$ ，上行 $s_0$ = RBRBR ，下行 $s_1$ = BBBRB ：

i	竖砖 cost	横砖 cost (上+下)	dp[i]
1	R≠B → 1	—	0 + 1 = 1
2	B = B → 0	R≠B + B = B → 1 + 0	min(1+0, 0+1) = 1
3	R≠B → 1	B≠R + B = B → 1 + 0	min(1+1, 1+1) = 2
4	B≠R → 1	R≠B + B≠R → 1 + 1	min(2+1, 1+2) = 3
5	R≠B → 1	B≠R + R≠B → 1 + 1	min(3+1, 2+2) = 4

输出 4 ✓

复杂度

时间 $O(n)$ ，空间 $O(n)$ （dp 数组其实只用最近两项可以滚到 $O(1)$ ，但 $n \le 2 \cdot 10^5$ 完全没必要省）。

AC 代码

AC 提交：373262009

核心 Solve() 就 7 行有效代码，DP 部分直接照公式翻译：

void Solve() {
	ll N;
	cin >> N;
	vector<array<char, 2> > s(N);
	for (int i = 0; i < N; ++i) cin >> s[i][0];
	for (int i = 0; i < N; ++i) cin >> s[i][1];
	vector<ll> dp(N + 1, INF);
	dp[0] = 0;
	for (int i = 0; i < N; ++i) {
		dp[i + 1] = min(dp[i + 1], dp[i] + (s[i][0] != s[i][1]));
		if (i >= 1) {
			dp[i + 1] = min(dp[i + 1], dp[i - 1] + (s[i][0] != s[i - 1][0]) + (s[i][1] != s[i - 1][1]));
		}
	}
	cout << dp[N] << "\n";
}

展开完整 C++ 源码（含调试模板）

// teamname: Gospel_rock
/**
 * Problem: C. Red-Black Pairs≈1100
 * Contest: Educational Codeforces Round 189 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2225/problem/C
 * Created: 2026-05-01 22:51:36
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

void Solve() {
	ll N;
	cin >> N;
	vector<array<char, 2> > s(N);
	for (int i = 0; i < N; ++i) cin >> s[i][0];
	for (int i = 0; i < N; ++i) cin >> s[i][1];
	vector<ll> dp(N + 1, INF);
	dp[0] = 0;
	for (int i = 0; i < N; ++i) {
		dp[i + 1] = min(dp[i + 1], dp[i] + (s[i][0] != s[i][1]));
		if (i >= 1) {
			dp[i + 1] = min(dp[i + 1], dp[i - 1] + (s[i][0] != s[i - 1][0]) + (s[i][1] != s[i - 1][1]));
		}
	}
	cout << dp[N] << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> lT;
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve();
	return 0;
}

心路历程（贪心 → DP）

第一版：邻居贪心（弃用）

刚开始想的是 局部贪心：扫每个格子，看它上下左右四个邻居有没有同色的——如果一个同色邻居都没有，就把它强制改成某个异色邻居的颜色，ans++。

代码挂在 C_Red_Black_Pairs.cpp ：

for (int x = 0; x < 2; ++x) {
	for (int y = 0; y < N; ++y) {
		ll cnt = 0; char ch;
		for (int i = 0; i < 4; ++i) {
			ll tox = x + dx[i], toy = y + dy[i];
			if (check(tox, toy)) {
				if (s[tox][toy] == s[x][y]) ++cnt;
				else ch = s[x][y];
			}
		}
		if (!cnt) { s[x][y] = ch; ++ans; }
	}
}

这个贪心 是错的。问题在于：

局部把一个孤立格子改色并不保证全局能成功配对；
「改 1 格」有时不如「换一种铺法多改 0 格但解锁后续更便宜的配对」。

第二版：DP（AC）

意识到结构本质就是 2×n 多米诺骨牌铺满 之后，DP 的状态和转移就一目了然——只剩两种砖型，按列扫一遍，AC（373262009）。

教训

看到「两行 / 网格配对」时的第一反应应该是 多米诺铺法，而不是「邻居贪心」——前者是结构化的（铺法只有两种局部规则），后者是临时拼凑的，没法保证全局最优。

附件

暂无（题目较短，没写 mentor.tex 录稿；动画也没做）。

Znzryb's Blog

CF Edu 189 C - Red-Black Pairs