题解：CF2254C2 Marenol (hard version)

· · 题解

题意简述

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

求将 a 变换为 b 所需的最少操作次数，若不可能则输出 -1。

思路

由 easy version 可知，每次操作等价于将一个 1 在同奇偶性的位置之间移动 2 个距离（例如 001 \rightarrow 100 将 1 右移 2 位，100 \rightarrow 001 将 1 左移 2 位）。因此，奇数位上的 1 的数量和偶数位上的 1 的数量分别保持不变。

若某个奇偶性下 1 的数量不相等，则不可能变换，输出 -1。

否则，对于同一奇偶性，我们需要将 a 中所有 1 的位置匹配到 b 中所有 1 的位置。为了最小化总移动距离，显然应该按顺序配对（排序后对应），因为所有 1 等价，且移动操作不改变相对顺序（在同奇偶性中位置可交换，但最优匹配即为排序配对）。

对于每个配对，位置差为 |pos_a - pos_b|，而一次操作移动 2 的距离，所以该配对所需操作数为 \frac{|pos_a - pos_b|}{2}。分别对奇数位和偶数位累加，即为答案。

代码

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 2e5 + 10;
int T, n;
string a, b;

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

    cin >> T;
    while(T --)
    {
        cin >> n >> a >> b;
        a = " " + a + "11";
        b = " " + b + "11";

        long long ans = 0;
        bool flag = true;

        int i = 1, j = 1;
        while(i <= n && j <= n)
        {
            while(i <= n && a[i] != '1') i += 2;
            while(j <= n && b[j] != '1') j += 2;
            if(i > n || j > n) break;
            ans += abs(i - j) / 2;
            i += 2, j += 2;
        }
        while(i <= n && a[i] != '1') i += 2;
        while(j <= n && b[j] != '1') j += 2;
        if(i <= n || j <= n) flag = false;

        i = 2, j = 2;
        while(i <= n && j <= n)
        {
            while(i <= n && a[i] != '1') i += 2;
            while(j <= n && b[j] != '1') j += 2;
            if(i > n || j > n) break;
            ans += abs(i - j) / 2;
            i += 2, j += 2;
        }
        while(i <= n && a[i] != '1') i += 2;
        while(j <= n && b[j] != '1') j += 2;
        if(i <= n || j <= n) flag = false;

        if(flag) cout << ans << endl;
        else cout << -1 << endl;
    }
    return 0;
}

原题通过记录