2024寒假每日一题全部题解传送门>>

这一题和$Acwing$第$1208$题翻硬币和第$95$题费解的开关思路都差不多，就是说前面的一个状态一旦确定下来了之后就不能够再改变了。换句话说，如果当前状态和目标状态不同，通过一次操作之后将其变成目标状态，那么在之后的操作中就不能再改变当前的状态了，否则一定会使得操作的次数增多。故从左到右枚举，如果发现当前状态和目标状态不同，就必须要做出改变，如果无法将其改变，那么就一定无解！值得注意的是，按照题目要求来操作的话，第一个位置和最后一个位置的状态是无法改变的，如果一开始这两个位置的状态就和目标状态不同的话，就直接输出无解。

C++代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
char s1[N], s2[N];
int T;

int main()
{
    scanf("%d", &T);

    while(T --)
    {
        scanf("%s%s", s1, s2);

        bool flag = true;
        int res = 0, len = strlen(s1);
        for(int i = 1; i < len - 1; i ++)
            if(s1[i] != s2[i]) 
                if(s2[i] != s2[i - 1] && s2[i] != s2[i + 1])
                {
                    res ++;
                    s2[i] ^= 1; // 将当前状态进行翻转
                }
                else flag = false; // 无法对当前位置进行改变，那么无解

        // 如果第一个位置和最后一个位置就和目标状态不同，直接无解
        if(s1[len - 1] != s2[len - 1] || s1[0] != s2[0]) flag = false; 

        if(flag) printf("%d\n", res);
        else puts("-1");
    }

    return 0;
}