题解 P11361 [NOIP2024] 编辑字符串

Mr_罗 · 2024-12-02 19:15:37 · 题解

提供一个极简又好写的思路以及可以通过你谷民间数据的代码。

对于这道题，只需要注意到以下事实：

• 连续的 t_{0/1,i}=1 的段（即 11...1）中间的字符可以随意交换。
• 贪心地匹配不会更劣。

于是只要简单地统计，贪心地匹配就好了。时间复杂度 \mathcal O(Tn)。预计做题时间不超过 0.5h。

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

#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define vi vector<int>
#define vii vector<pii>
#define eb emplace_back
#define all(c) (c).begin(), (c).end()
#define bit(x) (1 << (x))
#define bin(s, x) ((s) >> (x) & 1)
#define mem(a, x) memset(a, x, sizeof(a))
#define req(i, l, r) for (int i(l), i##End(r); i < i##End; i = -~i)
#define qer(i, r, l) for (int i(r), i##End(l); i > i##End; i = ~-i)
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

#ifdef JYR
#define errs(x) fputs(x, stderr)
#define errm(x, ...) fprintf(stderr, x, __VA_ARGS__)
#else
#define errs(x)
#define errm(x, ...)
#endif

template<typename T, typename U> void chkmx(T &_a, U _b) { if (_a < _b) _a = _b; }
template<typename T, typename U> void chkmn(T &_a, U _b) { if (_a > _b) _a = _b; }

bool Mbe;

#define MC

#define N 100005
#define mod 998244353
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f

int n, ans;
char s[2][N], t[2][N];
int c[2][2];

void calc(int o, int i) {
    c[o][0] = c[o][1] = 0;
    while (++i <= n && t[o][i] != '0') c[o][s[o][i] - '0']++;
}

void mslv() {
    scanf("%d%s%s%s%s", &n, s[0] + 1, s[1] + 1, t[0] + 1, t[1] + 1);
    calc(0, 0), calc(1, 0);
    rep(i, 1, n) {
        if (t[0][i] == '1' && t[1][i] == '1') {
            if      (c[0][0] && c[1][0]) ans++, c[0][0]--, c[1][0]--;
            else if (c[0][1] && c[1][1]) ans++, c[0][1]--, c[1][1]--;
            else if (c[0][0] && c[1][1]) c[0][0]--, c[1][1]--;
            else                         c[0][1]--, c[1][0]--;
        }
        else if (t[0][i] == '1') {
            calc(1, i);
            int x = s[1][i] - '0';
            if (c[0][x]) ans++, c[0][x]--;
            else c[0][x ^ 1]--;
        }
        else if (t[1][i] == '1') {
            calc(0, i);
            int x = s[0][i] - '0';
            if (c[1][x]) ans++, c[1][x]--;
            else c[1][x ^ 1]--;
        }
        else {
            calc(0, i), calc(1, i), ans += s[0][i] == s[1][i];
        }
    }
    printf("%d\n", ans);
}

void sprw() {
    ans = 0;
}

void mprw() {}

bool Med;

int main() {
    #ifdef JYR
    freopen("Test.in", "r", stdin);
    freopen("Test.out", "w", stdout);
    #endif
    mprw();
    #ifdef MC
    int _; scanf("%d", &_);
    while (_--) sprw(), mslv();
    #else
    mslv();
    #endif
    #ifdef JYR
    fprintf(stderr, "%.3lfMB %.0lfms\n", abs(&Med - &Mbe) / 1048576., clock() * 1000. / CLOCKS_PER_SEC);
    #endif
    return 0;
}