【Coding】寒假每日一题Day.7. 翻转

题目来源

题目来自于AcWing平台：https://www.acwing.com/problem/content/4970/。
以blog的形式记录程序设计算法学习的过程，仅做学习记录之用。

题目描述 + 输入输出格式 + 数据范围

样例

思路

思路参考自题解：https://www.acwing.com/solution/content/186160/。

这道题是思维题，其实我已经想出来了，大体的思路是，如果第一个数或最后一个数在两个字符串中是不同的，那么一定不符合条件；然后就可以遍历字符串，记录一下总共操作了多少次，是否能够通过翻转来得到相同的字符串。具体来说，对于当前字母，如果它前一个字母和后一个字母相同，而二者都与它不同，则说明它可以翻转，再看一下它与目标串位置是否相同，不同则翻转并将答案res++。最后判断一下两个串是否相同，得到答案。

但是，这种做法过不了最后一个测试点，我百思不得其解，看到题解中说，最后一个点是卡常数，不能使用$string$和$cin$读入，需要使用$char$数组和$scanf$读入。算是一个小坑吧…

题解中的思路和我的处理方法不太一样，题解中不做特判，而是直接从第一个字母开始判断，如果遇到某个字符在两个字符串的相同位置上不同，那么对它进行判断：

如果这个字符前一个字符的位置$i?1\ge 0$而后一个字符的位置$i+1<n$（$n$表示字符串的长度）并且这两个字符与目标串中位置$i$的字符相同，而与当前串$i$位置的字符不同，就可以进行翻转操作，并将res++。

反之，不满足上述条件就说明不能够通过翻转完成转换，输出-1。

Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int maxn = 1e6 + 5;

char s1[maxn], s2[maxn];

int d;

int main(){
    cin >> d;
    while(d --){
        scanf("%s%s", s2, s1);
        int n = strlen(s1);
        int i = 0, res = 0;
        bool isOk = true;
        while(i < n){
            if(s1[i] != s2[i]){
                if(i - 1 >= 0 && i + 1 < n && s1[i-1] == s2[i] && s1[i+1] == s2[i]){
                    // 一个棋子如果和它两边的棋子都不一样，才能变色
                    s1[i] = s2[i];
                    res ++;
                }
                else{
                    printf("-1\n");
                    isOk = false;
                    break;
                }
            }
            i ++;
        }
        if(isOk){
            printf("%d\n", res);
        }
    }
    return 0;
}