成绩分析#

预期：80+30=110 SX 1= 实际：45+30=75 SX 2=

问题分析#

预期与实际差距过大，实质原因是在考场上选择了错误的做题思路，且民间数据过水，导致预期过高。也证实了考场上不能拼运气，而应该脚踏实地想正确的解决方案。

考场复盘#

考试开始后感觉T1可做，先在纸上模拟，30min后发现看错题，这时候心态有点不太稳了，但依然选择继续死磕T1。先写出几个正确性无法证明的贪心，结果没过大样例，随后在不断的推倒重想之后，选择了玄学的多次重复求正解方法，随后决定开始看T2。

T2考场怎么想的记不太清了，大体是心态不太对，打完部分分就开始想尽可能求正解，但感觉思路一直不在线。随后1h回去看T1，测样例，推结论，只到考试结束也没想出正解，考场发挥太不稳定了。

总结#

此次失利主要还是心态炸了，以及基础的不扎实，导致出现了考场无思路，状态不良好的情况。而且考场的策略也不正确，这是很大的问题。

补题记录#

2025-2-21 14:27：开始补T1
2025-2-21 15:09：T1 AC
2025-2-21 17:14 T1题解完成

题解#

T1#

题意分析#

根据题意，考虑贪心做法，即每一位尽可能匹配上，这个策略显然正确，因为对于每一位来说，当前位匹配至多导致后面的一对无法匹配。

所以我们可以将字符串按无法交换的字符为界，分割为多个块，分别对于每一块进行操作。

一种做法为，先预处理出每一位字符所在的块的编号，并预处理出每一个块中，1和0的个数。然后遍历字符串，如果当前字符所在的两个块中，有相同的字符，则将两个块中对应字符的个数减一；如果没有，则将当前位的两个字符减去。过程中统计答案即可。

Code#

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
}