NOIP2024T1题解

DanielDingDang · 2025-10-27 10:02:07 · 个人记录

前言

去年考场当场报警，今年回来看发现 T1 简直是个橙题。

题解

考虑每个串 s_{id}(1\le id\le 2)，预处理出 \text{zeros}_{id,i} 表示在 i 所在的连续段中有多少个 \texttt{0}，且只关心 t_{id,i-1}=\texttt{0},t_{id,i}=\texttt{1} 的位置，\text{ones}_{id,i} 就是连续段中 \texttt{1} 的个数，和 \texttt{0} 是同理的。

靠前的位置尽可能使其相同，这一策略显然正确。因此，直接动态维护两个串目前连续段中的 \texttt{0} 以及 \texttt{1} 的个数即可。扫到 i 的时候，如果有一个 s_i 不能动，就尽量在另一个串中分配一个 s_i；如果两个都能动，就随便分配一个 \texttt{0}/\texttt{1}。如果两个都动不了，直接判断他们原来的是否相同即可。

代码是好写的。

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 100010;

string s[3], t[3];
int zeros[3][N], ones[3][N], n;

void solve()
{
    cin >> n;
    int res = 0;
    cin >> s[1] >> s[2] >> t[1] >> t[2];
    s[1] = ' ' + s[1], s[2] = ' ' + s[2];
    t[1] = '0' + t[1] + '0', t[2] = '0' + t[2] + '0';
    for (int id = 1; id <= 2; id ++ )
        for (int i = 0; i <= n + 1; i ++ )
            zeros[id][i] = ones[id][i] = 0;
    for (int id = 1; id <= 2; id ++ )
        for (int i = 1; i <= n; i ++ )
        {
            if (t[id][i] == '0') {
                ones[id][i] = zeros[id][i] = 0;
                continue;
            }
            if (t[id][i - 1] == '0') {
                int j = i;
                if (s[id][j] == '0') zeros[id][i] ++ ;
                else ones[id][i] ++ ;
                while (j < n && t[id][j + 1] == '1') {
                    j ++ ;
                    if (s[id][j] == '0') zeros[id][i] ++ ;
                    else ones[id][i] ++ ;
                }       
            }
        }
    for (int i = 1; i <= n; i ++ ) {
        if (t[1][i] == '0' && t[2][i] == '0') {
            res += s[1][i] == s[2][i];
            continue;
        }
        if      (t[1][i] == '0' && s[1][i] == '0' && zeros[2][i]) res ++ , zeros[2][i] -- ;
        else if (t[1][i] == '0' && s[1][i] == '1' && ones [2][i]) res ++ , ones [2][i] -- ;
        else if (t[2][i] == '0' && s[2][i] == '0' && zeros[1][i]) res ++ , zeros[1][i] -- ;
        else if (t[2][i] == '0' && s[2][i] == '1' && ones [1][i]) res ++ , ones [1][i] -- ;
        else if (zeros[1][i] && zeros[2][i]) res ++ , zeros[1][i] -- , zeros[2][i] -- ;
        else if (ones [1][i] && ones [2][i]) res ++ , ones [1][i] -- , ones [2][i] -- ;
        if (t[1][i] != '0' && t[1][i + 1] != '0') zeros[1][i + 1] = zeros[1][i], ones[1][i + 1] = ones[1][i];
        if (t[2][i] != '0' && t[2][i + 1] != '0') zeros[2][i + 1] = zeros[2][i], ones[2][i + 1] = ones[2][i];
    }
    cout << res << "\n";
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T -- ) solve();
    return 0;
}