Pre

怎么都说 T1 好想但难调啊，简单贪心 + 小模拟评蓝还是太高了，这里就给出一种好写又好调的并查集做法。

Solution

根据题意可知，tk,i=1(k∈{1,2},1≤i≤n)t_{k, i} = 1(k \in \{ 1, 2\}, 1 \le i \le n) 的连续的 ii 所代表的 sk,is_{k, i} 之间可以任意互换，换句话说，字符串 tkt_k 将 sks_k 分割成了若干个连通块，属于同一个连通块中的不同字符可以互换，但应当保持 {0,1}\{ 0, 1\} 的个数不变。然后一个贪心的思路呼之欲出了：

从左往右遍历到第 ii 个字符时，如果 s1,is_{1, i} 和 s2,is_{2, i} 所处的连通块中存在个数大于 00 的字符 0/10 / 1 时，就将匹配数加一，同时将该字符在连通块中的计数减少一；否则匹配数不变化，连通块中字符数量不为 00 的计数减少一。

贪心比较显然，毕竟每个下标对于答案产生的贡献只有 00 或 11 两种，面临抉择时肯定是先选择后者。至于如果匹配失败删去两个连通块中剩余的字符个数，是因为此时两个连通块中一定存在一个字符数量为 00，而另一个不为 00，而这个位置必须有数，因此各删去一个。

关于并查集的具体做法：分别给 s1s_1 和 s2s_2 建一个并查集，维护好每一个连通块中 00 和 11 的数量。一旦有 tk,i=tk,i−1=1(k∈{1,2},1<i≤n)t_{k, i} = t_{k, i - 1} = 1 (k \in \{ 1, 2\}, 1 \lt i \le n)，就将这两个字符所在连通块合并起来。

细节详见代码，单次时间复杂度为 O(n×α(n))O(n \times \alpha(n) )，近似线性复杂度。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define x first
// #define y second
#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

inline void debug() { cerr << '\n'; }
template<typename Type, typename... Args>
inline void debug(const Type& x, const Args&... y) { cerr << x << ' ', debug(y...); }
#define DEBUG(a...) { cerr << "[" << #a << "] = ", debug(a); }

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100010;
const int INF = 0x3f3f3f3f;

template<typename Type>
inline void read(Type& res)
{
    res = 0;
    int ch = getchar(), flag = 0;
    while (!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    res = flag ? -res : res;
}
template<typename Type, typename... Args>
inline void read(Type& res, Args&... y) { read(res), read(y...); }

int n;
char str[N];
int s[2][N], t[2][N];
int pre[2][N], cnt[2][N][2];

int rt(int k, int x) { return pre[k][x] == x ? x : pre[k][x] = rt(k, pre[k][x]); }

inline void merge(int k, int x, int y)
{
    int px = rt(k, x), py = rt(k, y);
    if (px == py) return;
    pre[k][py] = px, cnt[k][px][0] += cnt[k][py][0], cnt[k][px][1] += cnt[k][py][1];
}

void solve()
{
    for (int k = 0; k < 2; k ++)
        for (int i = 0; i < N; i ++)
            pre[k][i] = i, cnt[k][i][0] = cnt[k][i][1] = 0;

    read(n);
    for (int k = 0; k < 2; k ++)
    {
        scanf("%s", str + 1);
        for (int i = 1; i <= n; i ++)
        {
            s[k][i] = str[i] == '1';
            cnt[k][i][s[k][i]] = 1;
        }
    }
    for (int k = 0; k < 2; k ++)
    {
        scanf("%s", str + 1);
        for (int i = 1; i <= n; i ++)
        {
            t[k][i] = str[i] == '1';
            if (t[k][i] == 1 && t[k][i - 1] == 1)
                merge(k, i - 1, i);
        }
    }

    int ans = 0;
    for (int cur = 1, i = rt(0, cur), j = rt(1, cur); cur <= n; cur ++, i = rt(0, cur), j = rt(1, cur))
    {
        if (cnt[0][i][0] > 0 && cnt[1][j][0] > 0) ans ++, cnt[0][i][0] --, cnt[1][j][0] --;
        else if (cnt[0][i][1] > 0 && cnt[1][j][1] > 0) ans ++, cnt[0][i][1] --, cnt[1][j][1] --;
        else
        {
            if (cnt[0][i][0] > 0) cnt[0][i][0] --, cnt[1][j][1] --;
            else cnt[0][i][1] --, cnt[1][j][0] --;
        }
    }
    cout << ans << '\n';
}

signed main()
{
    File("edit");
    int T; read(T);
    while (T --) solve();
    return 0;
}