← 返回题目列表

Codeforces · 1533/F

F. 二进制字符串分区

中文机器翻译题面 查看原题

如果字符 0 在此字符串中出现的次数不超过 $$$k$$$,或者字符 1 在此字符串中出现的次数不超过 $$$k$$$(或两者兼而有之),那么我们称由字符 0 和/或 1 组成的字符串 $$$t$$$ 为漂亮。例如,如果 $$$k = 3$$$,则字符串 101010, 111, 0, 00000, 1111111000 很漂亮,而字符串 1111110000, 01010101 则不漂亮。

给你一个字符串 $$$s$$$。你必须将它分成尽可能少的漂亮字符串,即。即,找到一个字符串序列 $$$t_1, t_2, \dots, t_m$$$,使得每个 $$$t_i$$$ 都很漂亮,$$$t_1 + t_2 + \dots + t_m = s$$$ (其中 $$$+$$$ 是连接运算符),并且 $$$m$$$ 是最小可能的。

对于从 $$$1$$$ 到 $$$|s|$$$ 的每个 $$$k$$$,找到可以将 $$$s$$$ 划分为这些字符串的最小可能数量(即分区中可能的最小 $$$m$$$)。

输入

唯一一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$)。 $$$s$$$ 的每个字符不是 0 就是 1。

输出

打印 $$$|s|$$$ 整数。当 $$$k = i$$$ 时,第 $$$i$$$ 个整数应等于 $$$s$$$ 分区中的最小字符串数。

示例

输入 #1

00100010

输出 #1

2 1 1 1 1 1 1 1

输入 #2

1001011100

输出 #2

3 2 2 2 1 1 1 1 1 1