问题2553--连续的1

2553: 连续的1

[命题人 : ]
时间限制 : 3 sec  内存限制 : 1024 MB

提交

题目描述

给你一个长度为 N 的字符串 S,仅含 0,1,?,聪明的你能不能通过把? 变成 0 或 1,有且仅有一种方案使得这个字符串有且仅有一段连续的 1,且长度为 K。

输入

第一行,一个整数,表示数据组数 T。
对于每组数据:
第一行,两个整数,表示  N,K。
第二行,一个长度为 N 的字符串,表示 S 。
$1≤  T≤  10^{5} $
$1 ≤ K < N ≤ 3 × 10^{5} $
对于所有测试用例, N 的和不超过 $3 × 10^{5}$

输出

对于每组数据:如果满足题目条件输出 Yes,否则输出 No 。

样例输入 Copy

4
3 2
1??
4 2
?1?0
6 3
011?1?
10 5
00?1???10?

样例输出 Copy

Yes
No
No
Yes

提示

第一个测试用例中,假设将 S 替换为 101,但由于 1 没有连续,因此不满足条件。为了使 S 满足条件,只能将 S 替换为 110。

第二个测试用例中,S 要满足条件,可以将 S 替换为 1100 或 0110,但满足条件的替换方式共有 2 种。

第三个测试用例中,无法通过任何替换方式使 S 满足条件。

来源/分类