成绩分析

预期：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

// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ONLINE_JUDGE
#define MULTI_CASES
#define endl '\n'
const int MaxN = 2e5 + 100;
const int INF = 1e9;
const int mod = 212370440130137957ll;
int T = 1, N, M;
// int a[MaxN];
int cnt1[MaxN], cnt2[MaxN];
pair<int, int> q1[MaxN], q2[MaxN];
inline void Solve()
{
    cin >> N;
    string s1, s2, a, b;
    memset(cnt1, 0, sizeof cnt1);
    memset(cnt2, 0, sizeof cnt2);
    memset(q1, 0, sizeof q1);
    memset(q2, 0, sizeof q2);
    int pos = 1;
    cnt1[0] = 1;
    cin >> s1 >> s2 >> a >> b;
    for (int i = 1; i < N; i++)
    {
        if (a[i] == a[i - 1] && a[i] == '1')
        {
            cnt1[i] = pos;
        }
        else
        {
            pos++;
            cnt1[i] = pos;
        }
        if (s1[i] == '1')
        {
            q1[cnt1[i]].first++;
        }
        else
        {
            q1[cnt1[i]].second++;
        }
    }
    pos = 1;
    cnt2[0] = 1;
    for (int i = 1; i < N; i++)
    {
        if (b[i] == b[i - 1] && b[i] == '1')
        {
            cnt2[i] = pos;
        }
        else
        {
            pos++;
            cnt2[i] = pos;
        }
        if (s2[i] == '1')
        {
            q2[cnt2[i]].first++;
        }
        else
        {
            q2[cnt2[i]].second++;
        }
    }
    if (s1[0] == '1')
    {
        q1[cnt1[0]].first++;
    }
    else
    {
        q1[cnt1[0]].second++;
    }
    if (s2[0] == '1')
    {
        q2[cnt2[0]].first++;
    }
    else
    {
        q2[cnt2[0]].second++;
    }
    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        // cerr << cnt1[i] << " " << cnt2[i] << endl;

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

        if (q1[cnt1[i]].first > 0 && q2[cnt2[i]].first > 0)
        {
            q1[cnt1[i]].first--;
            q2[cnt2[i]].first--;
            sum++;
            continue;
        }
        if (q1[cnt1[i]].second > 0 && q2[cnt2[i]].second > 0)
        {
            q1[cnt1[i]].second--;
            q2[cnt2[i]].second--;
            sum++;
            continue;
        }
        if (q1[cnt1[i]].first)
        {
            q1[cnt1[i]].first--;
            q2[cnt2[i]].second--;
            continue;
        }
        if (q1[cnt1[i]].second)
        {
            q1[cnt1[i]].second--;
            q2[cnt2[i]].first--;
        }
    }
    cout << sum << endl;
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}

T2