To solve the problem of maximizing the number of matching characters between two binary strings after applying specific swap operations, we can approach the problem using the Union-Find (Disjoint Set Union) data structure. Here's a step-by-step explanation of the solution:

Step-by-Step Reasoning:

1. Understanding Swap Operations:

   • For each string s1 and s2, we have swap regions defined by the binary strings t1 and t2.
   • Characters in s1 and s2 can be swapped within their respective substitute regions where the corresponding character in t1 or t2 is 1. This defines contiguous segments where characters can be rearranged freely.

2. Union-Find Structure:

   • We will use Union-Find to group positions together that can be part of the same swap operations.
   • Two characters will be part of the same connected component if they are part of the same swap region in either s1 or s2.

3. Counting Bits in Connected Components:

   • For each connected component, count the number of 0s and 1s in both s1 and s2.
   • The number of matches for each connected component is determined by the minimum number of 0s and 1s that can be matched between s1 and s2.

4. Implementation Details:

   • Initialize a Union-Find structure for each test case.
   • Traverse through t1 and t2 to union adjacent positions where swapping is allowed.
   • Once all unions are performed, count the occurrences of 0s and 1s in each connected component.
   • Sum up the minimum overlaps from each connected component to get the final result.

C++ Implementation:

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

typedef long long ll;

// Union-Find structure with path compression
struct UnionFind {
    vector<int> parent;
    UnionFind(int n){
        parent.resize(n+1);
        for(int i=0;i<=n;i++) parent[i]=i;
    }
    int find_set(int u){
        if(parent[u]!=u){
            parent[u] = find_set(parent[u]);
        }
        return parent[u];
    }
    void union_set(int u, int v){
        int pu = find_set(u);
        int pv = find_set(v);
        if(pu != pv){
            parent[pu] = pv;
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        string s1, s2, t1, t2;
        cin >> s1 >> s2 >> t1 >> t2;
        UnionFind uf(n);
        // Process s1 swap regions
        int l = 0;
        while(l < n){
            if(t1[l] == '1'){
                int r = l;
                while(r+1 < n && t1[r+1] == '1') r++;
                for(int i=l; i<r; i++) uf.union_set(i+1, i+2);
                l = r+1;
            }
            else{
                l++;
            }
        }
        // Process s2 swap regions
        l = 0;
        while(l < n){
            if(t2[l] == '1'){
                int r = l;
                while(r+1 < n && t2[r+1] == '1') r++;
                for(int i=l; i<r; i++) uf.union_set(i+1, i+2);
                l = r+1;
            }
            else{
                l++;
            }
        }
        // Prepare counts
        // To avoid multiple components, use arrays
        // Initialize counts to 0
        // Since n can be up to 1e5, use vectors
        vector<int> c1_0(n+1, 0), c1_1(n+1, 0);
        vector<int> c2_0(n+1, 0), c2_1(n+1, 0);
        for(int i=0; i<n; i++){
            int root = uf.find_set(i+1);
            if(s1[i] == '0') c1_0[root]++;
            else c1_1[root]++;
            if(s2[i] == '0') c2_0[root]++;
            else c2_1[root]++;
        }
        // To avoid processing the same root multiple times, iterate from 1 to n and process only when i is root
        ll total = 0;
        for(int i=1; i<=n; i++){
            if(uf.parent[i] == i){
                total += (ll)(min(c1_0[i], c2_0[i]) + min(c1_1[i], c2_1[i]));
            }
        }
        cout << total << "\n";
    }
}
//tested by LHQing

目前在熨斗上获得75分。

仅使用o1mini一次生成。多次询问通过t1概率很大。