CF Edu 189 C - Red-Black Pairs · znzryb
**比赛**：[Educational Codeforces Round 189 (Rated for Div. 2)](https://codeforces.com/contest/2225) · **题目链接**：[C. Red-Black Pairs](https://codeforces.com/contest/2225/problem/C)
# 题目大意
## 题面
有一张 $2 \times n$ 的格子表，每个格子涂红色 (R) 或黑色 (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
```
输出：
```
1
0
3
1
4
```
第 4 个样例一种合法重涂是
```
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**](https://codeforces.com/contest/2225/submission/373262009)
核心 `Solve()` 就 7 行有效代码，DP 部分直接照公式翻译：
```cpp
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\+\+ 源码（含调试模板）
```cpp
// 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` ：
```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](https://codeforces.com/contest/2225/submission/373262009)）。
## 教训
看到「两行 / 网格配对」时的第一反应应该是 **多米诺铺法**，而不是「邻居贪心」——前者是结构化的（铺法只有两种局部规则），后者是临时拼凑的，没法保证全局最优。
# 附件
暂无（题目较短，没写 mentor.tex 录稿；动画也没做）。