自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 22:55:17，当前版本为作者最后更新于2024-02-17 18:45:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

比较恶心的一道题。

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

$$10101\cdots01\to01010\cdots10\to00101\cdots00\to\cdots\to00\cdots0100\cdots0 $$

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

$$10101101\to01010101$$

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

$$101011\to010101$$

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

$$1011\cdots101\to01011\cdots101\to\cdots$$

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

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

• $1(01)^k$ 是合法的 $(k\ge1)$。
• 若 $\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);
}