零一串 (string)
题目描述
给定一个长度为 \(n\) 的 01 串，你需要将它划分成若干段，每一段的长度都不超过 \(m\)，且满足以下两种条件之一：
- 这个段中全部为 \(0\) 或全部为 \(1\).
- 这个段中 \(0,1\) 数量之差不超过 \(k\).
你需要求出该 01 串合法的划分最少要多少段。
输入格式
第一行输入三个整数 \(n,m,k\)，分别表示 \(01\) 串的长度，段的长度限制，条件 \(2\) 中 \(0,1\) 数量差的限制。
接下来一行，输入一个长度为 \(n\) 的 \(01\) 串，表示该 \(01\) 串。
输出格式
一行，输出一个正整数，最少划分段数。
样例 #1
样例输入 #1
5 4 1 01110样例输出 #1
2样例 #2
样例输入 #2
20 5 1 10111101010011000100样例输出 #2
6提示
样例 1 解释：
一种符合条件的划分方式是 (01,110).
数据范围：
subtask score \(n\) \(k\) 性质A 0 10 \(\le 2 \times 10^3\) \(\le n\) 1 1 30 $\le 2 \times 10^5 $ \(\le n\) 0 2 20 \(\le 10^7\) \(\le n\) 1 3 15 \(\le 10^7\) \(=0\) 0 4 25 \(\le 10^7\) \(\le n\) 0 其中，性质 A 为：\(01\) 串随机生成，每一位均有一半的概率为 \(0\),一半的概率为 \(1\).
表中性质 A 一栏为 \(1\) 则表示数据满足该性质。对于 \(100\%\) 的数据，满足 \(1 \le n,m,k \le 10^7\)
-
\(0 \rightarrow -1,1 \rightarrow 1\) ，dp 是 simple 的，\(O(n \log n)\) 即线段树每个节点维护单调队列，然后扫描线问题变成二维数点，加上 \(K = 0\) 可以拿到 55pts 。然后赛时就想不下去了，但至少觉得相邻前缀和之差为 \(1\) 是解决问题的关键
-
正解：在单调队列的过程中，每个队列中最多只有两个值，因为他们肯定是互相转移的，否则一定不优，因此我们不用单调队列，只用维护最大和次大即可
-
但区间 \(\min\) 还是很难做到线性。我们考虑这题有哪些特殊性质
- 相邻两个前缀和之差 \(\leq 1\)
- \(f_i \leq n\)
- \(f_{i+1} - f_i \leq 1\) (即把 \(i+1\) 单独看成一段)
-
因此我们可以开一个桶存每个 \(f_i\) 的值，然后用一个指针指向最大的 \(f_i\) ，每次插入或删除数时暴力移动指针即可。最终复杂度 \(O(n)\)