5-3 Ice and Fire

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Ice and Fire

链接:https://codeforces.com/problemset/problem/1774/C
来源:codeforces

时间限制:1 seconds
空间限制:256 megabytes

题目描述

小09和他的朋友在玩游戏。有\(n\)个玩家,其中玩家\(i\)的温度值是\(i\)。

环境的类型表示为\(0\)或\(1\)。当两个玩家在一个特定的环境中战斗时,如果其类型是\(0\),在这个环境中温度值较低的玩家总是获胜;如果是\(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\))--玩家的数量。

每个测试案例的第二行包含一个长度为\(n-1\)的二进制字符串\(s\)。

保证所有测试案例的\(n\)之和不超过\(3\cdot 10^5\)。

输出

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

样例

输入样例

2
4
001
4
101

输出样例

1 1 3 
1 2 3 

样例解释

在第一个测试案例中,对于\(x=2\)和\(x=3\),只有温度值为\(1\)的玩家可以成为赢家。对于\(x=4\),温度值为\(2,3,4\)的玩家可以成为赢家。

2023暑假集训7月10日训练题

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2023-07-10 09:00
结束于
2023-07-10 11:30
持续时间
2.5 小时
主持人
参赛人数
20