蓝桥杯真题 - 翻转 - 题解

题目链接：https://www.lanqiao.cn/problems/3520/learning/

个人评价：难度 1 星（满星：5）
前置知识：无

整体思路

• 贪心，除了第一位跟最后一位，其它字符，每当 $S[i]\ne T[i]$ 时，能换则换；
• 为什么可以贪心？
  • 因为如果某段连续的数字为 $101$ 或者 $010$，在被修改之后变为 $111$ 或者 $000$，此时这三个数字都无法再被修改，所以连续的满足修改条件的数字只能被修改一次；
  • 当 $S$ 串的某一位与 $T$ 串的某一位不同时，由于每个字符只能被修改一次，所以一旦出现不同的字符必须立即修改。

过题代码

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn = 1000000 + 100;
int T, ans;
char s[maxn], t[maxn];int main() {
#ifdef ExRocfreopen("test.txt", "r", stdin);
#endif // ExRocios::sync_with_stdio(false);cin >> T;while (T--) {ans = 0;cin >> t >> s;for (int i = 1; s[i + 1] != '\0'; ++i) {if (s[i] == t[i]) {continue;}if (s[i - 1] != s[i] && s[i] != s[i + 1]) {++ans;s[i] = t[i];}}if (strcmp(s, t) == 0) {cout << ans << endl;} else {cout << -1 << endl;}}return 0;
}