Codeforces Round 898 (Div. 4) |
---|
Закончено |
У вас есть полоска бумаги $$$s$$$, которая имеет длину $$$n$$$ ячеек. Каждая ячейка может быть либо черной, либо белой. За одну операцию вы можете выбрать любые $$$k$$$ последовательных ячеек и сделать их все белыми.
Найдите минимальное количество операций, необходимых для удаления всех черных ячеек.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — длина полоски бумаги и целое число, используемое в операции.
Вторая строка каждого набора содержит строку $$$s$$$ длиной $$$n$$$, состоящую из символов $$$\texttt{B}$$$ (представляющего черную ячейку) и $$$\texttt{W}$$$ (представляющего белую ячейку).
Сумма $$$n$$$ по всем тестам не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для удаления всех черных ячеек.
86 3WBWWWB7 3WWBWBWW5 4BWBWB5 5BBBBB8 2BWBWBBBB10 2WBBWBBWBBW4 1BBBB3 2WWW
2 1 2 1 4 3 4 0
В первом наборе входных данных примера вы можете выполнить следующие операции: $$$$$$\color{red}{\texttt{WBW}}\texttt{WWB} \to \texttt{WWW}\color{red}{\texttt{WWB}} \to \texttt{WWWWWW}$$$$$$
Во втором наборе входных данных примера вы можете выполнить следующие операции: $$$$$$\texttt{WW}\color{red}{\texttt{BWB}}\texttt{WW} \to \texttt{WWWWWWW}$$$$$$
В третьем наборе входных данных примера вы можете выполнить следующие операции: $$$$$$\texttt{B}\color{red}{\texttt{WBWB}} \to \color{red}{\texttt{BWWW}}\texttt{W} \to \texttt{WWWWW}$$$$$$
Название |
---|