分数: 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 满足条件,所以有两种方法来满足它们。
对于第三个测试用例,无法替换字符来满足条件。