蓝桥杯真题 - 翻转 - 题解

题目链接：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 ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::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;
}