题解：CF2254C1 Marenol (easy version)

· · 题解

题意简述

给定两个长度均为 n 的二进制字符串 a 和 b。你可以对 a 执行以下两种操作任意次：

判断能否将 a 变换为 b。

思路

观察两种操作：

因此，每次操作都不改变每个 1 所在下标的奇偶性。也就是说，奇数位置上的 1 的数量和偶数位置上的 1 的数量都是不变量。

反过来，只要两个字符串在奇数位和偶数位上的 1 的数量分别相等，就一定能通过有限次操作互相转化（这两个操作恰好提供了在同奇偶位置之间移动 1 的所有可能方式）。

所以我们只需要分别统计 a 和 b 在奇数位和偶数位上 1 的个数，若都相等则输出 YES，否则输出 NO。

代码

#include <iostream>
#include <cstring>

using namespace std;

int T, n;
string s, t;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> T;
    while(T --)
    {
        cin >> n >> s >> t;
        int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
        for(int i = 0;i < n; ++ i)
        {
            if(s[i] == '1')
            {
                if(i & 1) a1 ++;
                else a2 ++;
            }
            if(t[i] == '1')
            {
                if(i & 1) b1 ++;
                else b2 ++;
            }
        }
        if(a1 == b1 && a2 == b2)
            cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

原题通过记录