#P9644. [SNCPC2019] Turn It Off

[SNCPC2019] Turn It Off

题目描述

It's already 21:30 now, and it's time for BaoBao to go to bed. To ensure his sleeping quality, BaoBao decides to turn all the lights in his bedroom off.

There are nn lights, numbered from 1 to nn, arranged in a row in BaoBao's bedroom. Each time BaoBao can select an integer ii and turn all the lights numbered from ii to (i+L1)(i+L-1) (both inclusive) off, where LL is a predefined positive integer. Note that each time the value of LL must be the same.

Given the initial status of all the lights, please help BaoBao determine the smallest possible LL so that he can turn all the lights off within kk times.

输入格式

There are multiple test cases. The first line of the input contains an integer TT, indicating the number of test cases. For each test case:

The first line contains two integers nn and kk (1kn2×1051 \le k \le n \le 2 \times 10^5).

The second line contains a string ss (s=n|s| = n, s{‘0’,‘1’}s \in \{\text{`0'}, \text{`1'}\}) indicating the initial status of the lights. Let sis_i be the ii-th character in ss, if si=‘1’s_i = \text{`1'} then the ii-th light is initially on, otherwise it's initially off. It's guaranteed that there is at least one `1· in ss.

It's guaranteed that the sum of nn of all test cases will not exceed 2×1062 \times 10^6.

输出格式

For each test case output one line containing one integer, indicating the smallest possible LL.

题目大意

【题目描述】

现在已经是 21:30 了,宝宝该上床睡觉了。为了确保他的睡眠质量,宝宝决定关掉卧室里的所有灯。

宝宝的卧室里有 nn 盏灯,从1到 nn 排成一排。每次宝宝可以选择一个整数 ii,并将从第 ii 盏灯到第 (i+L1)(i+L-1) 盏灯(包括两端)之间的所有灯关掉,其中 LL 是一个预定义的正整数。注意,每次操作的 LL 值必须相同。

给定所有灯的初始状态,请帮助宝宝确定可能的最小 LL 使得他能在 kk 次操作内关掉所有的灯。

【输入格式】

有多个测试用例。输入的第一行包含一个整数 TT,表示测试用例的数量。对于每个测试用例:

第一行包含两个整数 nnkk1kn2×1051 \le k \le n \le 2 \times 10^5)。

第二行包含一个字符串 sss=n|s| = n, s{‘0’,‘1’}s \in \{\text{`0'}, \text{`1'}\})表示灯的初始状态。设 sis_i 为字符串 ss 的第 ii 个字符,如果 si=‘1’s_i = \text{`1'},则第 ii 盏灯初始是亮的,否则是灭的。保证 ss 中至少有一个 1

保证所有测试用例的 nn 之和不超过 2×1062 \times 10^6

【输出格式】

对于每个测试用例输出一行,包含一个整数,表示可能的最小 LL

翻译来自于:ChatGPT

2
10 4
0101011111
3 1
010
3
1