P10160 题解

Register_int · 2024-02-17 18:45:38 · 题解

比较恶心的一道题。

先来找找规律：如果是 10101\cdots01 的序列，最少可以剩几个 1。

显然可以反复横跳到只剩一个。那如果是两个这样的序列拼起来呢？

可以发现套娃又开始了，显然也能只剩一个。同时我们可以发现，只要他接上的是一个 1，就有：

而且用 1 连接的两个序列也是可以合并的：

到最后中间的 1 一定会被削完。

此时我们发现了一些性质，可以直接尝试定义合法的序列。它满足以下条件：

• 若 \text A 是合法的，则 1\text A 与 \text A1 是合法的。
• 若 \text A,\text B 是合法的，则 \text{AB} 是合法的。

那么一个合法序列最终必定能缩成只剩一个 1。此时的合法序列已经涵盖了所有我们可操作的序列了，直接用双指针处理出原字符串中所有极长的合法序列，手动将每个区间中 1 全部删掉再补上一个即可，时间复杂度 O(n)。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

int n, ans; char s[MAXN];

int l[MAXN], r[MAXN], sum[MAXN], cnt;

int main() {
    scanf("%s", s + 1), n = strlen(s + 1);
    for (int i = 1; i <= n; i++) if (s[i] == '1') ans++;
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] & 1);
    for (int i = 1, j = 1, k = 0; i <= n; ) {
        if (s[i] != '1') { i++, k = 0; continue; }
        for (j = i; j + 2 <= n && s[j + 1] == '0' && s[j + 2] == '1'; j += 2);
        if (i != j) {
            if (cnt && r[cnt] + k + 1 == i) r[cnt] = j;
            else l[++cnt] = i - k, r[cnt] = j; k = 0;
        } else {
            if (cnt && l[cnt] != r[cnt] && r[cnt] + 1 == i) r[cnt]++;
            else k++;
        }
        i = j + 1;
    }
    for (int i = 1; i <= cnt; i++) ans -= sum[r[i]] - sum[l[i] - 1] - 1;
    printf("%d", ans);
}