← 返回题目列表

AtCoder · arc150_a

A. 连续 1

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

分数: 300 点

问题陈述

给你一个长度为 N, S=S_1S_2\dots S_N,包括 0, 1,和 ?.

我们喜欢更换每一个 ? 与 0 or 1 以便满足以下所有条件。

  • S 恰好包含 K 出现 1.
  • 这些 K 出现 1 是连续的。也就是说,有一个 i\ (1 \leq i \le N-K+1) 这样 S_i=S_{i+1}=\dots=S_{i+K-1}= 1.

确定是否只有一种方法可以替换字符以满足条件。

你有 T 测试用例解决。

约束

  • 1 \leq T \leq 10^5
  • 1 \leq K < N \leq 3 \times 10^5
  • S 是一个长度为 N 组成 0, 1,和 ?.
  • 总和 N 测试用例最多 3 \times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个案例的格式如下:

N K
S

输出

打印 T 行。的 i- 第行应包含 Yes 如果,对于 i-第一个测试用例,只有一种方法可以替换字符来满足条件,并且 No 否则。


示例输入 1

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

示例输出 1

Yes
No
No
Yes

对于第一个测试用例,车削 例如, S 进入 101不满足条件,因为 1s 不会是连续的。满足条件的唯一方法就是转 S 进入 110.

对于第二个测试用例,我们可以将 S 进入 1100 or 0110 满足条件,所以有两种方法来满足它们。

对于第三个测试用例,无法替换字符来满足条件。