思路与算法

固定位置不能参与相邻交换，因此它是屏障；每个字符串分别切成“连续可交换段”与“固定单点”。自由段内相邻交换可以实现任意排列，所以一个段只需保存长度与1的数量。把两个字符串的段作为二分图两侧顶点，同一位置所属的两个段之间连边，并把连续相同段对合并为一条边，容量等于它们的重叠长度。

设两串1的总数合计为 $W$，同一位置同时放1的最大数为 $M$。不相等的位置恰有一个1，所以最大相等数为 $n-W+2M$。$M$ 是二分图的容量匹配：每个顶点容量为该段1数，每条边容量为重叠长度。

两侧都是有序且互不重叠的区间划分。沿位置扫描，每遇到新重叠边至少有一侧进入此前从未出现的新段，因此图是森林。用队列处理度1顶点：在唯一边上匹配两端剩余1数和边容量的最小值，扣除后删掉该边，邻点成为叶则入队。累计匹配数后套公式。

正确性说明

段内1数不变是相邻交换的必要条件，而同一自由段内任意两个等1数二进制串可通过相邻交换互达，所以分段表示完整覆盖所有可达状态。任意可达两串的11位置构成一个满足所有顶点与边容量的匹配，故匹配最优值是11数上界。

取最大容量匹配后，每个段剩余1可放到其尚未用于11的重叠位置。若某条还有空位的边两端都剩余1，就能直接增广一单位，与最大性矛盾；因此剩余1的两侧不会争抢同一空位。每个段的剩余位置总数不少于剩余1数，故能全部放下，其他位置填0，实现恰 $M$ 个11。所以容量模型的上界可达。

对于森林叶顶点 $v$ 的唯一边 $(v,u)$，令 $f=\min(c_{uv},s_u,s_v)$。任意最优匹配若该边少于 $f$，可增加这条边的匹配；若邻点容量已满，就从邻点其他边转移同样数量，匹配总数不减。叶没有其他边，转移不会损失其余可行性。因此存在最优解在该边匹配 $f$，删叶后的问题相同，归纳证明贪心最优。

复杂度

每组初始化段编号、供应量、邻接表为 $O(n)$。每个位置只扫描常数次，重叠边少于两侧顶点总数；每条边至多删一次，队列叶消元为 $O(n)$。每组总时间 $O(n)$，空间 $O(n)$；多组总时间为 $O(\sum n)$。

易错点

不能把整串所有 $t_i=1$ 的位置混成一个自由池；固定字符把它们隔成多个段。固定单点也要入图，1数为其实际字符。边容量是位置重叠长度，不是1数。答案可能为0，允许全固定、全自由和单字符。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int u, v, cap;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        string a, b, x, y;
        cin >> a >> b >> x >> y;
        vector<int> idA(n), idB(n), supply;
        auto partition = [&](const string &s, const string &t, vector<int> &id) {
            for (int l = 0; l < n;) {
                int r = l + 1;
                if (t[l] == '1')
                    while (r < n && t[r] == '1')
                        ++r;
                int u = supply.size(), one = 0;
                for (int i = l; i < r; i++) {
                    id[i] = u;
                    one += s[i] == '1';
                }
                supply.push_back(one);
                l = r;
            }
        };
        partition(a, x, idA);
        partition(b, y, idB);
        int V = supply.size(), ones = 0;
        for (int v : supply)
            ones += v;
        vector<Edge> edges;
        vector<vector<int>> adj(V);
        for (int l = 0; l < n;) {
            int r = l + 1;
            while (r < n && idA[r] == idA[l] && idB[r] == idB[l])
                ++r;
            int e = edges.size(), u = idA[l], v = idB[l];
            edges.push_back({u, v, r - l});
            adj[u].push_back(e);
            adj[v].push_back(e);
            l = r;
        }
        vector<int> deg(V);
        queue<int> q;
        for (int u = 0; u < V; u++) {
            deg[u] = adj[u].size();
            if (deg[u] == 1)
                q.push(u);
        }
        vector<char> removed(edges.size());
        int matched = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (deg[u] != 1)
                continue;
            for (int e : adj[u])
                if (!removed[e]) {
                    auto &z = edges[e];
                    int v = z.u ^ z.v ^ u;
                    int f = min(z.cap, min(supply[u], supply[v]));
                    matched += f;
                    supply[u] -= f;
                    supply[v] -= f;
                    removed[e] = 1;
                    --deg[u];
                    if (--deg[v] == 1)
                        q.push(v);
                    break;
                }
        }
        cout << n - ones + 2 * matched << '\n';
    }
}