把 A 与 B 不同的位置分成连续段，每段连续不匹配区间恰好需要一次翻转。
OJ: usaco
题目 ID: 1012
难度:入门
标签:贪心字符串模拟
日期: 2026-07-11 14:17
题意
给定两个长度为 N 的字符串 A 和 B，字符只可能是 H 或 G。
一次操作可以选择 B 的一个连续子串，把其中所有 H 变成 G，所有 G 变成 H。
求最少多少次操作能把 B 变成 A。
思路
暴力想法
小数据可以把每个位置是否不匹配看成一个二进制状态，然后 BFS 枚举每次翻转哪个连续区间：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-11 14:17
* update_at: 2026-07-11 14:19
*/
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
int n;
string a, b;
int greedy_answer() {
int ans = 0;
bool in_bad_segment = false;
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
if (!in_bad_segment) {
ans++;
in_bad_segment = true;
}
} else {
in_bad_segment = false;
}
}
return ans;
}
int bfs_brute() {
int start = 0;
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
start |= (1 << i);
}
}
int total = 1 << n;
vector<int> dist(total, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int state = q.front();
q.pop();
if (state == 0) {
return dist[state];
}
// 枚举一次操作翻转的连续子串。
for (int l = 0; l < n; l++) {
int mask = 0;
for (int r = l; r < n; r++) {
mask |= (1 << r);
int next_state = state ^ mask;
if (dist[next_state] == -1) {
dist[next_state] = dist[state] + 1;
q.push(next_state);
}
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b;
// BFS 只用于小数据对拍；大数据退回到贪心，避免暴力数组过大。
if (n <= 12) {
cout << bfs_brute() << '\n';
} else {
cout << greedy_answer() << '\n';
}
return 0;
}这种写法能验证答案，但状态数是
连续不匹配段
真正需要关注的是哪些位置满足：
text
A[i] != B[i]如果一段连续位置都不匹配，那么翻转这一整段，就能一次把它们全部修好。
如果两个不匹配段之间夹着已经匹配的位置，就不应该用同一次翻转跨过去。否则中间正确的位置会被翻坏，还要额外修回来。
所以答案就是“连续不匹配段”的数量。
从左到右扫描，只有在“当前不匹配，并且前一个位置不是同一段不匹配”时，才把答案加一。
代码
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-11 14:17
* update_at: 2026-07-11 14:19
*/
#include <bits/stdc++.h>
using namespace std;
int n;
string a, b;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b;
int ans = 0;
bool in_bad_segment = false;
// 每一段连续不匹配的位置，需要一次翻转。
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) {
if (!in_bad_segment) {
ans++;
in_bad_segment = true;
}
} else {
in_bad_segment = false;
}
}
cout << ans << '\n';
return 0;
}复杂度
只扫描一次字符串，时间复杂度为
保存两个字符串，空间复杂度为
总结
这题不要真的去模拟翻转。
把 A 和 B 不同的位置标出来后，问题就变成数连续段：每段不匹配区间一次操作，段与段之间不能合并。