洛谷 P10160 [DTCPC 2024] Ultra 题解

题意

给定一个01串，可以将串中的 1010101...010101 替换为 0101010...101010 反之亦然。求可能的最小的 1 的数量。

思路

我们可以发现，如果有连续的多个（\(\geq2\)）\(0\)，那么我们不可能将连续 \(0\) 左侧或右侧的一起处理。因此，为了方便，我们可以将左右两侧分开处理。当我们将左右两侧分到无法再分的程度时，我们再次观察。

容易发现，去除两侧的前导零和后缀零之后，如果剩下的部分中仍有 \(0\)，那么这个部分一定可以被化简为只有 \(1\) 个 \(1\) 的串；如果没有 \(0\)，那么这个部分不能再被任何方式化简，故该部分的 \(1\) 的数量为剩余的部分的长度。

实现

这道题的实现有一个巨大的坑。我们考虑使用 DFS 来处理。一开始，我将待处理的字符串作为参数传递进去，但是很显然这样会占用大量的内存，我赛时就是没有注意到这一点导致了 MLE 遗憾离场。为了解决这样的问题，我们可以只传递起始和结尾的下标，然后共用全局的字符串。这样就可以非常有效的避免 MLE 的问题，轻松又愉快的 AC。

#include <iostream>

#define int long long

using namespace std;

int n, a, b, cnt, ccnt, ans;
string s;

void dfs(int L, int R) {
    int cnt = 0;
    for (int i = L; i < R; i++) {
        if (s[i] == '1') {
            if (cnt > 1) {
                dfs(L, i - cnt);
                dfs(i, R);
                return;
            }
            cnt = 0;
        } else {
            cnt += 1;
        }
    }
    int l = L, r = R - 1;
    while (l <= r && l < R && s[l] == '0') {
        l += 1;
    }
    while (l <= r && r >= L && s[r] == '0') {
        r -= 1;
    }
    for (int i = l; i <= r; i++) {
        if (s[i] == '0') {
            ans += 1;
            return;
        }
    }
    ans += r - l + 1;
}

signed main() {
    cin >> s;
    dfs(0, s.size());
    cout << ans;
}