题解：CF2029B Replacement

NEKO_Daze · 2024-11-16 18:51:09 · 题解

洛谷CF2029B || CodeForces 2029 B

题意翻译

给出一个长度为 n 的二进制字符串 s 和另一个长度为 n-1 的二进制字符串 r。对 s 执行 n-1 操作（1 \le i \le n-1），每次选择一个索引 k 满足 1\le k\le |s| - 1 和 s_ {k} \neq s_ {k+1}，否则输出 NO 并结束，然后将 s_ ks_ {k+1} 替换为 r_ i。

当所有 n-1 次操作完成后输出 YES。

思路

如果当前 s 只包含 0 或只包含 1，显然无法进行合法的操作。输出 NO。

在第 i 次操作中，如果 r_i=0，我们实际上减少了 1 个 1，反之亦然。因此，我们只需要不断更新 s 中 0 和 1 的数量，它们中的任何一个下降到 0，那么输出 NO，否则必然可以完成所有操作并输出 YES。

时间复杂度：\mathcal{O}(T\times n)。

#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()

using namespace std;
using ll = long long;

const int _N = 1e5 + 5;

void solve() {
    int n; cin >> n;
    string s, t; cin >> s >> t;
    int cnt0 = count(all(s), '0'), cnt1 = n - cnt0;
    for (int i = 0; i < n - 1; i++) {
        if (cnt0 == 0 || cnt1 == 0) {
            cout << "NO" << '\n';
            return;
        }
        if (t[i] == '1') cnt0--;
        else cnt1--;
    }
    cout << "YES" << '\n';
}

int main() {
    int T; cin >> T;
    while (T--) {
        solve();
    }
}