P11361 [NOIP2024] 编辑字符串 题解#

1
// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
2
#include <bits/stdc++.h>
3
using namespace std;
4
#define ll long long
5
#define int ll
6
#define ONLINE_JUDGE
7
#define MULTI_CASES
8
#define endl '\n'
9
const int MaxN = 2e5 + 100;
10
const int INF = 1e9;
11
const int mod = 212370440130137957ll;
12
int T = 1, N, M;
13
// int a[MaxN];
14
int cnt1[MaxN], cnt2[MaxN];
15
pair<int, int> q1[MaxN], q2[MaxN];
16
inline void Solve()
17
{
18
    cin >> N;
19
    string s1, s2, a, b;
20
    memset(cnt1, 0, sizeof cnt1);
21
    memset(cnt2, 0, sizeof cnt2);
22
    memset(q1, 0, sizeof q1);
23
    memset(q2, 0, sizeof q2);
24
    int pos = 1;
25
    cnt1[0] = 1;
26
    cin >> s1 >> s2 >> a >> b;
27
    for (int i = 1; i < N; i++)
28
    {
29
        if (a[i] == a[i - 1] && a[i] == '1')
30
        {
31
            cnt1[i] = pos;
32
        }
33
        else
34
        {
35
            pos++;
36
            cnt1[i] = pos;
37
        }
38
        if (s1[i] == '1')
39
        {
40
            q1[cnt1[i]].first++;
41
        }
42
        else
43
        {
44
            q1[cnt1[i]].second++;
45
        }
46
    }
47
    pos = 1;
48
    cnt2[0] = 1;
49
    for (int i = 1; i < N; i++)
50
    {
51
        if (b[i] == b[i - 1] && b[i] == '1')
52
        {
53
            cnt2[i] = pos;
54
        }
55
        else
56
        {
57
            pos++;
58
            cnt2[i] = pos;
59
        }
60
        if (s2[i] == '1')
61
        {
62
            q2[cnt2[i]].first++;
63
        }
64
        else
65
        {
66
            q2[cnt2[i]].second++;
67
        }
68
    }
69
    if (s1[0] == '1')
70
    {
71
        q1[cnt1[0]].first++;
72
    }
73
    else
74
    {
75
        q1[cnt1[0]].second++;
76
    }
77
    if (s2[0] == '1')
78
    {
79
        q2[cnt2[0]].first++;
80
    }
81
    else
82
    {
83
        q2[cnt2[0]].second++;
84
    }
85
    int sum = 0;
86
    for (int i = 0; i < N; i++)
87
    {
88
        // cerr << cnt1[i] << " " << cnt2[i] << endl;
89

90
        // cerr << q1[cnt1[i]].first << " " << q2[cnt2[i]].first << " ";
91
        // cerr << q1[cnt1[i]].second << " " << q2[cnt2[i]].second << endl;
92

93
        if (q1[cnt1[i]].first > 0 && q2[cnt2[i]].first > 0)
94
        {
95
            q1[cnt1[i]].first--;
96
            q2[cnt2[i]].first--;
97
            sum++;
98
            continue;
99
        }
100
        if (q1[cnt1[i]].second > 0 && q2[cnt2[i]].second > 0)
101
        {
102
            q1[cnt1[i]].second--;
103
            q2[cnt2[i]].second--;
104
            sum++;
105
            continue;
106
        }
107
        if (q1[cnt1[i]].first)
108
        {
109
            q1[cnt1[i]].first--;
110
            q2[cnt2[i]].second--;
111
            continue;
112
        }
113
        if (q1[cnt1[i]].second)
114
        {
115
            q1[cnt1[i]].second--;
116
            q2[cnt2[i]].first--;
117
        }
118
    }
119
    cout << sum << endl;
120
}
121
signed main()
122
{
123
#ifndef ONLINE_JUDGE
124
    freopen(".in", "r", stdin);
125
    freopen(".out", "w", stdout);
126
#endif
127
    ios::sync_with_stdio(0);
128
    cin.tie(0), cout.tie(0);
129

130
#ifdef MULTI_CASES
131
    cin >> T;
132
    while (T--)
133
#endif
134
        Solve();
135
    // fclose(stdin);
136
    // fclose(stdout);
137
    return 0;
138
}