← 返回题目列表

Codeforces · 1398/F

F. 有争议的回合

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

Alice 和 Bob 玩游戏。比赛由几局组成,每局又由几轮组成。每轮由 Alice 或 Bob 获胜,当其中一名玩家连续赢得 $$$x$$$ 轮时,该组结束。例如,如果鲍勃连续赢得五轮且 $$$x = 2$$$,则两盘结束。

您知道 Alice 和 Bob 已经玩了 $$$n$$$ 轮,并且您知道某些轮的结果。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$x$$$,如果每组持续到其中一名玩家连续赢得 $$$x$$$ 轮,则计算可能已经完成的最大可能组数。最后一组可能还没有完成——在这种情况下,你不应该把它算在答案中。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 轮数。

第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$ — 回合的描述。如果字符串的第 $$$i$$$ 个元素为 0,则 Alice 赢得第 $$$i$$$ 轮;如果是 1,那么 Bob 赢得了第 $$$i$$$ 轮,如果是 ?,那么你不知道谁赢得了第 $$$i$$$ 轮。

输出

在唯一的行中打印 $$$n$$$ 整数。如果每组持续到其中一名玩家连续赢得 $$$i$$$ 轮,则第 $$$i$$$ 个整数应等于可能已经完成的最大可能组数。

示例

输入 #1

6
11?000

输出 #1

6 3 2 1 0 0

输入 #2

5
01?01

输出 #2

5 1 0 0 0

输入 #3

12
???1??????1?

输出 #3

12 6 4 3 2 2 1 1 1 1 1 1

注意

让我们考虑第一个测试用例:

- 如果 $$$x = 1$$$ 且 $$$s = 110000$$$ 或 $$$s = 111000$$$ 则有六组成品;
- 如果 $$$x = 2$$$ 且 $$$s = 110000$$$ 则有三组成品;
- 如果 $$$x = 3$$$ 且 $$$s = 111000$$$ 则有两套成品;
- 如果 $$$x = 4$$$ 并且 $$$s = 110000$$$ 则有一套完成的;
- 如果 $$$x = 5$$$ 则没有完成的集合;
- 如果 $$$x = 6$$$ 则没有完成的集合。