← 返回题目列表

Codeforces · 1774/C

C. 冰与火

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

Little09 和他的朋友们正在玩游戏。有$$$n$$$个玩家,$$$i$$$玩家的温度值为$$$i$$$。

环境类型表示为 $$$0$$$ 或 $$$1$$$。当两个玩家在特定环境中战斗时,如果其类型为$$$0$$$,则该环境中温度值较低的玩家总是获胜;如果是$$$1$$$,则在该环境下温度值较高的玩家总是获胜。 $$$n-1$$$ 环境的类型形成长度为$$$n-1$$$ 的二进制字符串$$$s$$$。

如果有$$$x$$$玩家参与游戏,则总共会有$$$x-1$$$场战斗,$$$x-1$$$环境类型将为$$$s$$$的前$$$x-1$$$角色。当比赛中剩下不止一名玩家时,选择任意两名剩余玩家进行战斗。输掉比赛的选手将被淘汰出局。战斗$$$i$$$的环境类型为$$$s_i$$$。

对于从$$$2$$$到$$$n$$$的每一个$$$x$$$,回答以下问题:如果所有温度值不超过$$$x$$$的玩家都参与游戏,那么有多少玩家有机会获胜?

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\le t \le 10^3$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — 玩家数量。

每个测试用例的第二行包含一个二进制字符串$$$s$$$,长度为$$$n-1$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3\cdot 10^5$$$。

输出

对于每个测试用例输出 $$$n-1$$$ 整数 - 对于从 $$$2$$$ 到 $$$n$$$ 的每个 $$$x$$$,输出有机会获胜的玩家数量。

示例

输入 #1

2
4
001
4
101

输出 #1

1 1 3 
1 2 3

注意

在第一个测试用例中,对于$$$x=2$$$和$$$x=3$$$,只有温度值为$$$1$$$的玩家才能成为获胜者。对于$$$x=4$$$,温度值为$$$2,3,4$$$的玩家可以获胜。