A1739 [NOIP2024.T1] 编辑字符串（非官方数据）

#include <bits/stdc++.h>
using namespace std;

// [NOIP2024 T1] 编辑字符串
//
// 关键思路：
//   1. 一个串被 t 切成若干「块」：t=1 的极长连续段是一个块，t=0 的位置单独成块。
//      块内相邻字符都能交换，所以块内可以任意重排；块之间换不了，
//      于是「每个块里 1 的个数」是固定的，块的长度也是固定的。
//   2. 设两个串里 1 的总数分别是 c1、c2，串长是 n。若有 F 个位置两个串都是 1，
//      则「对应位置相等」的个数 = n - c1 - c2 + 2F，所以只要让 F 最大。
//   3. F 是「块 × 块」二分图上的最大匹配：左边是 s1 的块，右边是 s2 的块，
//      每个位置是一条连接它所属的两个块的边（容量 1），块的容量是它含有的 1 的个数。
//      两个串的块都是区间，这张图必然是一片森林；而且可以按位置从左到右贪心：
//      当前位置若在两个串里所属的块都还有 1，就把它做成「双 1」。
//      （贪心正确性见 solution.md）

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s1, s2, t1, t2;
        cin >> n >> s1 >> s2 >> t1 >> t2;

        // 把一个串切成块：bid[k] 是位置 k 所属的块号，cap[id] 是该块里 1 的个数
        auto build = [&](const string& s, const string& t, vector<int>& bid, vector<int>& cap) {
            int i = 0;
            while (i < n) {
                int id = (int)cap.size();
                int ones = 0;
                int j = i;
                if (t[i] == '1') {
                    // t=1 的极长连续段：整段是一个可重排的块
                    while (j < n && t[j] == '1') {
                        ones += (s[j] == '1');
                        ++j;
                    }
                } else {
                    // t=0 的位置不能参与交换，单独成块
                    ones = (s[i] == '1');
                    ++j;
                }
                for (int k = i; k < j; ++k) bid[k] = id;
                cap.push_back(ones);
                i = j;
            }
        };

        vector<int> bid1(n), bid2(n), cap1, cap2;
        build(s1, t1, bid1, cap1);
        build(s2, t2, bid2, cap2);

        int c1 = 0, c2 = 0;
        for (char ch : s1) c1 += (ch == '1');
        for (char ch : s2) c2 += (ch == '1');

        // 从左到右贪心：两个串里所属的块都还有 1，就把这一位做成「双 1」
        vector<int> rem1 = cap1, rem2 = cap2;
        int F = 0;
        for (int i = 0; i < n; ++i) {
            int a = bid1[i], b = bid2[i];
            if (rem1[a] > 0 && rem2[b] > 0) {
                ++F;
                --rem1[a];
                --rem2[b];
            }
        }

        cout << n - c1 - c2 + 2 * F << "\n";
    }
    return 0;
}