【思维】第十四届蓝桥杯省赛C++ C组/研究生组 Python A组/C组《翻转》(C++)

时间:2024-03-23 22:56:23

【题目描述】

小蓝用黑白棋的 n 个棋子排成了一行,他在脑海里想象出了一个长度为 n 的 01 串 T,他发现如果把黑棋当做 1,白棋当做 0,这一行棋子也是一个长度为 n 的 01 串 S。

小蓝决定,如果在 S 中发现一个棋子和它两边的棋子都不一样,就可以将其翻转变成另一个颜色。

也就是说,如果 S 中存在子串 101 或者 010,就可以选择将其分别变为 111 和 000,这样的操作可以无限重复。

小蓝想知道最少翻转多少次可以把 S 变成和 T 一模一样。

【输入格式】

输入包含多组数据。

输入的第一行包含一个正整数 D 表示数据组数。

后面 2D 行每行包含一个 01 串,每两行为一组数据,第 2i−1 行为第 i 组数据的 Ti,第 2i 行为第 i 组数据的 Si,Si 和 Ti 长度均为 ni。

【输出格式】

对于每组数据,输出一行包含一个整数,表示答案,如果答案不存在请输出 −1

【数据范围】

【输入样例】

2
1000111
1010101
01000
11000

【输出样例】

2

-1

【代码】

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n;
char s[N], t[N];

void solve() {
    scanf("%s%s", t + 1, s + 1);
    n = strlen(s + 1);

    int ans = 0;
    for (int i = 2; i < n; i ++ ) 
        if (s[i] != t[i] && s[i - 1] == s[i + 1] && s[i - 1] != s[i]) 
            ans ++ , s[i] ^= 1;

    if (strcmp(s + 1, t + 1)) ans = -1;
    printf("%d\n", ans);
}

int main() {
    int _; scanf("%d", &_);
    while (_ -- ) solve();
    return 0;
}