← 返回题目列表

Codeforces · 1992/D

D. 爱情的考验

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

ErnKor 准备为 Julen 做任何事,甚至游过鳄鱼出没的沼泽。我们决定测试一下这段爱情。 ErnKor 必须游过一条宽度为 $$$1$$$ 米、长度为 $$$n$$$ 米的河流。

河水很冷。因此,总的来说(即从 $$$0$$$ 到 $$$n+1$$$ 的整个游泳过程)ErnKor 可以在水中游泳不超过 $$$k$$$ 米。为了人类的利益,我们不仅在河里添加了鳄鱼,还添加了可以让他跳跃的圆木。我们的测试如下:

最初,ErnKor 位于左岸,需要到达右岸。它们分别位于$$$0$$$ 和$$$n+1$$$ 米处。河流可以表示为 $$$n$$$ 段,每个段的长度为 $$$1$$$ 米。每个部分包含一根圆木“L”、一条鳄鱼“C”或只是水“W”。 ErnKor 可以按如下方式移动:

- 如果他在水面(即在岸边或圆木上),他可以向前跳跃不超过 $$$m$$$ ($$$1 \le m \le 10$$$) 米(他可以在岸边、圆木上或水中跳跃)。
- 如果他在水中,他只能游到下一个河段(如果他在第 $$$n$$$ 米处,则游到岸边)。
- ErnKor 无法以任何方式降落在有鳄鱼的区域。

确定 ErnKor 是否可以到达右岸。

输入

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

每个测试用例的第一行包含三个数字 $$$n, m, k$$$ ($$$0 \le k \le 2 \cdot 10^5$$$, $$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10$$$) — 河流的长度,ErnKor 可以跳跃的距离,以及米数ErnKor 可以游泳而不会冻僵。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$a$$$。 $$$a_i$$$ 表示位于第 $$$i$$$ 米处的对象。 ($$$a_i \in \{$$$'W','C','L'$$$\}$$$)

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果 ErnKor 能够通过测试,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

6
6 2 0
LWLLLW
6 1 1
LWLLLL
6 1 1
LWLLWL
6 2 15
LWLLCC
6 10 0
CCCCCC
6 6 1
WCCCCW

输出 #1

YES
YES
NO
NO
YES
YES

注意

让我们考虑一些例子:

- 第一个例子:我们从岸边跳到第一根圆木($$$0 \rightarrow 1$$$),从第一根圆木跳到第二根圆木($$$1 \rightarrow 3$$$),从第二根圆木跳到第四根圆木($$$3 \rightarrow 5$$$),然后从最后一根圆木跳到岸边($$$5 \rightarrow 7$$$)。所以,我们有 $$$0 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 7$$$。由于我们没有遇到鳄鱼并且游了不超过 k 米,所以答案是“是”。
- 第二个例子:$$$0 \rightarrow 1$$$,我们从第一根圆木($$$1 \rightarrow 2$$$)跳入水中,游一个细胞到圆木($$$2 \leadsto 3$$$),$$$3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7$$$。由于我们没有遇到鳄鱼并且游了不超过 k 米,所以答案是“是”。
- 在第三个示例中,ErnKor 需要游过两个单元格“W”,但只能游过一个单元格。因此,答案是“否”。
- 第六个例子:我们从岸边跳入水中($$$0 \rightarrow 6$$$)并在水中游动一个单元格($$$6 \leadsto 7$$$)。由于我们没有遇到鳄鱼并且游了不超过 k 米,所以答案是“是”。