← 返回题目列表

Codeforces · 1858/D

D. 树和线段

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

暑期信息学学校的老师们决定连续种植 $$$n$$$ 棵树,并且决定只种植橡树和冷杉。为此,他们制定了一个计划,该计划可以表示为长度为 $$$n$$$ 的二进制字符串 $$$s$$$。如果 $$$s_i = 0$$$,则该行中的第 $$$i$$$ 树应该是橡树,如果 $$$s_i = 1$$$,则该行中的第 $$$i$$$ 树应该是冷杉。

明天就是植树节,后天会有督学来学校。检验员非常热爱大自然,他会对这排行的美感做出如下评价:

- 首先,他将计算 $$$l_0$$$ 作为该行中连续橡树的最大数量(计划 $$$s$$$ 中由零组成的最大子串)。如果该行中没有橡树,则 $$$l_0 = 0$$$。
- 然后,他将计算$$$l_1$$$作为该行中连续第一个的最大数量(由计划$$$s$$$组成的最大子串)。如果行中没有第一个,则 $$$l_1 = 0$$$。
- 最后,他会将行的美度计算为 $$$a \cdot l_0 + l_1$$$ 对于某些 $$$a$$$ — 检查员最喜欢的数字。

老师知道参数 $$$a$$$ 的值,但出于安全原因他们不能告诉你。他们只告诉你 $$$a$$$ 是从 $$$1$$$ 到 $$$n$$$ 的整数。

由于树木尚未种下,老师们决定将不超过$$$k$$$的树木类型改为相反的类型(即将计划中的$$$s_i$$$从$$$0$$$改为$$$1$$$或从$$$1$$$改为$$$0$$$),以便根据督察的意见,将这排树的美丽最大化。

对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$j$$$,独立回答以下问题:

- 如果检查员最喜欢的数字 $$$a$$$ 等于 $$$j$$$,那么教师通过改变不超过 $$$k$$$ 棵树的类型可以实现的这排树的最大美感是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3000$$$, $$$0 \le k \le n$$$) — 该行中树的数量和最大更改数量。

第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,由零和一组成 - 计划描述。

保证所有测试用例的所有 $$$n$$$ 值的总和不超过 $$$3000$$$。

输出

对于每个测试用例,打印 $$$n$$$ 个整数,其中第 $$$j$$$ 个 ($$$1 \le j \le n$$$) 是在使用 $$$a = j$$$ 计算美观度时,变化不超过 $$$k$$$ 后该行树的最大美观度。

示例

输入 #1

5
3 0
111
4 1
0110
5 0
10000
6 2
101101
7 1
0001101

输出 #1

3 3 3 
4 5 7 9 
5 9 13 17 21 
6 9 13 17 21 25 
7 10 13 17 21 25 29

注意

在第一个测试用例中不允许进行任何更改,因此 $$$l_0 = 0$$$ 和 $$$l_1 = 3$$$ 始终成立。因此,无论 $$$a$$$ 的值是多少,这排树的美丽度都是 $$$3$$$。

在 $$$a \in \{1, 2\}$$$ 的第二个测试用例中,教师可以将计划 $$$s$$$ 更改为 $$$0111$$$(通过更改 $$$s_4$$$),并将 $$$a \in \{3, 4\}$$$ — 更改为 $$$0010$$$(通过更改$$$s_2$$$)。在这种情况下,每个 $$$a$$$ 的行的美观度计算如下:

- 对于 $$$a = 1$$$:$$$l_0 = 1$$$,$$$l_1 = 3$$$。该行的美妙之处在于$$$1\cdot 1 + 3 = 4$$$。
- 对于 $$$a = 2$$$:$$$l_0 = 1$$$,$$$l_1 = 3$$$。该行的美妙之处在于$$$2\cdot 1 + 3 = 5$$$。
- 对于 $$$a = 3$$$:$$$l_0 = 2$$$,$$$l_1 = 1$$$。该行的美妙之处在于$$$3\cdot 2 + 1 = 7$$$。
- 对于 $$$a = 4$$$:$$$l_0 = 2$$$,$$$l_1 = 1$$$。该行的美妙之处在于$$$4\cdot 2 + 1 = 9$$$。

可以证明,上述变化对于从 $$$1$$$ 到 $$$4$$$ 的所有 $$$a$$$ 都是最佳的。