309504: CF1690D. Black and White Stripe
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Black and White Stripe
题意翻译
### 题意翻译 给出 $n$ 和 $m$，还有一个长度为 $n$ 且只包含 `B` 和 `W` 的字符串。 问在字符串中找出一个长度为 $m$ 且只包含 `B` 的子串最少需要修改多少个 `W`。 多组测试。题目描述
You have a stripe of checkered paper of length $ n $ . Each cell is either white or black. What is the minimum number of cells that must be recolored from white to black in order to have a segment of $ k $ consecutive black cells on the stripe? If the input data is such that a segment of $ k $ consecutive black cells already exists, then print 0.输入输出格式
输入格式
The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Next, descriptions of $ t $ test cases follow. The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 2\cdot10^5 $ ). The second line consists of the letters 'W' (white) and 'B' (black). The line length is $ n $ . It is guaranteed that the sum of values $ n $ does not exceed $ 2\cdot10^5 $ .
输出格式
For each of $ t $ test cases print an integer — the minimum number of cells that need to be repainted from white to black in order to have a segment of $ k $ consecutive black cells.
输入输出样例
输入样例 #1
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W输出样例 #1
1
2
0
1说明
In the first test case, $ s $ ="BBWBW" and $ k=3 $ . It is enough to recolor $ s_3 $ and get $ s $ ="BBBBW". This string contains a segment of length $ k=3 $ consisting of the letters 'B'. In the second test case of the example $ s $ ="BBWBW" and $ k=5 $ . It is enough to recolor $ s_3 $ and $ s_5 $ and get $ s $ ="BBBBB". This string contains a segment of length $ k=5 $ consisting of the letters 'B'. In the third test case of the example $ s $ ="BBWBW" and $ k=1 $ . The string $ s $ already contains a segment of length $ k=1 $ consisting of the letters 'B'.Input
题意翻译
### 题意翻译 给出 $n$ 和 $m$，还有一个长度为 $n$ 且只包含 `B` 和 `W` 的字符串。 问在字符串中找出一个长度为 $m$ 且只包含 `B` 的子串最少需要修改多少个 `W`。 多组测试。Output
**题意翻译**
给定 $n$ 和 $m$，以及一个长度为 $n$ 且只包含 `B`（黑色）和 `W`（白色）的字符串。问在字符串中找出一个长度为 $m$ 且只包含 `B` 的子串最少需要修改多少个 `W`。有多组测试数据。
**题目描述**
你有长度为 $n$ 的棋盘格纸条。每个单元格要么是白色要么是黑色。问最少需要将多少个单元格从白色重新涂成黑色，以便在纸条上有一个连续的 $k$ 个黑色单元格的段。如果输入数据中已经存在一个连续的 $k$ 个黑色单元格的段，则输出 0。
**输入输出格式**
**输入格式**
第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) —— 测试用例的数量。接下来是 $t$ 个测试用例的描述。每个测试用例的第一行包含两个整数 $n$ 和 $k$ ( $1 \le k \le n \le 2\cdot10^5$ )。第二行由字母 `W`（白色）和 `B`（黑色）组成，长度为 $n$。保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。
**输出格式**
对于每个测试用例，输出一个整数 —— 需要从白色重新涂成黑色以得到一个连续的 $k$ 个黑色单元格的段所需的最少单元格数量。
**输入输出样例**
**输入样例 #1**
```
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W
```
**输出样例 #1**
```
1
2
0
1
```
**说明**
在第一个测试用例中，$s$="BBWBW" 和 $k=3$。只需重新涂色 $s_3$ 并得到 $s$="BBBBW"。这个字符串包含一个长度为 $k=3$ 的由字母 `B` 组成的段。
在第二个测试用例中，$s$="BBWBW" 和 $k=5$。只需重新涂色 $s_3$ 和 $s_5$ 并得到 $s$="BBBBB"。这个字符串包含一个长度为 $k=5$ 的由字母 `B` 组成的段。
在第三个测试用例中，$s$="BBWBW" 和 $k=1$。字符串 $s$ 已经包含一个长度为 $k=1$ 的由字母 `B` 组成的段。**题意翻译** 给定 $n$ 和 $m$，以及一个长度为 $n$ 且只包含 `B`（黑色）和 `W`（白色）的字符串。问在字符串中找出一个长度为 $m$ 且只包含 `B` 的子串最少需要修改多少个 `W`。有多组测试数据。 **题目描述** 你有长度为 $n$ 的棋盘格纸条。每个单元格要么是白色要么是黑色。问最少需要将多少个单元格从白色重新涂成黑色，以便在纸条上有一个连续的 $k$ 个黑色单元格的段。如果输入数据中已经存在一个连续的 $k$ 个黑色单元格的段，则输出 0。 **输入输出格式** **输入格式** 第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) —— 测试用例的数量。接下来是 $t$ 个测试用例的描述。每个测试用例的第一行包含两个整数 $n$ 和 $k$ ( $1 \le k \le n \le 2\cdot10^5$ )。第二行由字母 `W`（白色）和 `B`（黑色）组成，长度为 $n$。保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。 **输出格式** 对于每个测试用例，输出一个整数 —— 需要从白色重新涂成黑色以得到一个连续的 $k$ 个黑色单元格的段所需的最少单元格数量。 **输入输出样例** **输入样例 #1** ``` 4 5 3 BBWBW 5 5 BBWBW 5 1 BBWBW 1 1 W ``` **输出样例 #1** ``` 1 2 0 1 ``` **说明** 在第一个测试用例中，$s$="BBWBW" 和 $k=3$。只需重新涂色 $s_3$ 并得到 $s$="BBBBW"。这个字符串包含一个长度为 $k=3$ 的由字母 `B` 组成的段。 在第二个测试用例中，$s$="BBWBW" 和 $k=5$。只需重新涂色 $s_3$ 和 $s_5$ 并得到 $s$="BBBBB"。这个字符串包含一个长度为 $k=5$ 的由字母 `B` 组成的段。 在第三个测试用例中，$s$="BBWBW" 和 $k=1$。字符串 $s$ 已经包含一个长度为 $k=1$ 的由字母 `B` 组成的段。
给定 $n$ 和 $m$，以及一个长度为 $n$ 且只包含 `B`（黑色）和 `W`（白色）的字符串。问在字符串中找出一个长度为 $m$ 且只包含 `B` 的子串最少需要修改多少个 `W`。有多组测试数据。
**题目描述**
你有长度为 $n$ 的棋盘格纸条。每个单元格要么是白色要么是黑色。问最少需要将多少个单元格从白色重新涂成黑色，以便在纸条上有一个连续的 $k$ 个黑色单元格的段。如果输入数据中已经存在一个连续的 $k$ 个黑色单元格的段，则输出 0。
**输入输出格式**
**输入格式**
第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) —— 测试用例的数量。接下来是 $t$ 个测试用例的描述。每个测试用例的第一行包含两个整数 $n$ 和 $k$ ( $1 \le k \le n \le 2\cdot10^5$ )。第二行由字母 `W`（白色）和 `B`（黑色）组成，长度为 $n$。保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。
**输出格式**
对于每个测试用例，输出一个整数 —— 需要从白色重新涂成黑色以得到一个连续的 $k$ 个黑色单元格的段所需的最少单元格数量。
**输入输出样例**
**输入样例 #1**
```
4
5 3
BBWBW
5 5
BBWBW
5 1
BBWBW
1 1
W
```
**输出样例 #1**
```
1
2
0
1
```
**说明**
在第一个测试用例中，$s$="BBWBW" 和 $k=3$。只需重新涂色 $s_3$ 并得到 $s$="BBBBW"。这个字符串包含一个长度为 $k=3$ 的由字母 `B` 组成的段。
在第二个测试用例中，$s$="BBWBW" 和 $k=5$。只需重新涂色 $s_3$ 和 $s_5$ 并得到 $s$="BBBBB"。这个字符串包含一个长度为 $k=5$ 的由字母 `B` 组成的段。
在第三个测试用例中，$s$="BBWBW" 和 $k=1$。字符串 $s$ 已经包含一个长度为 $k=1$ 的由字母 `B` 组成的段。**题意翻译** 给定 $n$ 和 $m$，以及一个长度为 $n$ 且只包含 `B`（黑色）和 `W`（白色）的字符串。问在字符串中找出一个长度为 $m$ 且只包含 `B` 的子串最少需要修改多少个 `W`。有多组测试数据。 **题目描述** 你有长度为 $n$ 的棋盘格纸条。每个单元格要么是白色要么是黑色。问最少需要将多少个单元格从白色重新涂成黑色，以便在纸条上有一个连续的 $k$ 个黑色单元格的段。如果输入数据中已经存在一个连续的 $k$ 个黑色单元格的段，则输出 0。 **输入输出格式** **输入格式** 第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) —— 测试用例的数量。接下来是 $t$ 个测试用例的描述。每个测试用例的第一行包含两个整数 $n$ 和 $k$ ( $1 \le k \le n \le 2\cdot10^5$ )。第二行由字母 `W`（白色）和 `B`（黑色）组成，长度为 $n$。保证所有测试用例的 $n$ 之和不超过 $2\cdot10^5$。 **输出格式** 对于每个测试用例，输出一个整数 —— 需要从白色重新涂成黑色以得到一个连续的 $k$ 个黑色单元格的段所需的最少单元格数量。 **输入输出样例** **输入样例 #1** ``` 4 5 3 BBWBW 5 5 BBWBW 5 1 BBWBW 1 1 W ``` **输出样例 #1** ``` 1 2 0 1 ``` **说明** 在第一个测试用例中，$s$="BBWBW" 和 $k=3$。只需重新涂色 $s_3$ 并得到 $s$="BBBBW"。这个字符串包含一个长度为 $k=3$ 的由字母 `B` 组成的段。 在第二个测试用例中，$s$="BBWBW" 和 $k=5$。只需重新涂色 $s_3$ 和 $s_5$ 并得到 $s$="BBBBB"。这个字符串包含一个长度为 $k=5$ 的由字母 `B` 组成的段。 在第三个测试用例中，$s$="BBWBW" 和 $k=1$。字符串 $s$ 已经包含一个长度为 $k=1$ 的由字母 `B` 组成的段。