D. 1D Eraser

这篇具有很好参考价值的文章主要介绍了D. 1D Eraser。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a strip of paper s that is n cells long. Each cell is either black or white. In an operation you can take any k consecutive cells and make them all white.

Find the minimum number of operations needed to remove all black cells.

Input

The first line contains a single integer t (1≤t≤1000) — the number of test cases.

The first line of each test case contains two integers n and k (1≤k≤n≤2⋅105) — the length of the paper and the integer used in the operation.

The second line of each test case contains a string s of length n consisting of characters B (representing a black cell) or W (representing a white cell).

The sum of n over all test cases does not exceed 2⋅105.

Output

For each test case, output a single integer — the minimum number of operations needed to remove all black cells.

Example

input

Copy

 

8

6 3

WBWWWB

7 3

WWBWBWW

5 4

BWBWB

5 5

BBBBB

8 2

BWBWBBBB

10 2

WBBWBBWBBW

4 1

BBBB

3 2

WWW

output

Copy

2
1
2
1
4
3
4
0

Note

In the first test case you can perform the following operations:WBWWWB→WWWWWB→WWWWWW

In the second test case you can perform the following operations:WWBWBWW→WWWWWWW

In the third test case you can perform the following operations:BWBWB→BWWWW→WWWWW

解题说明:此题是一道模拟题,每次只能修改连续K个位置,遍历查找其中的B字母位置,直接将其与后面K-1个位置全变成W即可。文章来源地址https://www.toymoban.com/news/detail-719985.html

#include <stdio.h>
int main()
{
	int t, n, k, i, j, b;
	scanf("%d", &t);
	for (i = 0; i < t; i++)
	{
		scanf("%d %d", &n, &k);
		char a[200005];
		scanf("%s", a);
		b = 0;
		for (j = 0; j < n; j++)
		{
			if (a[j] == 'W')
			{
				continue;
			}
			else 
			{
				j += (k - 1); 
				b += 1; 
			}
		}
		printf("%d\n", b);
	}
	return 0;
}

到了这里,关于D. 1D Eraser的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法&数据结构体系篇class32】:IndexTree & AC自动机

    特点: 1 )支持区间查询 2 )没有线段树那么强,但是非常容易改成一维、二维、三维的结构 3 )只支持单点更新   解决在一个大字符串中,找到多个候选字符串的问题   AC 自动机算法核心 : 1 )把所有匹配串生成一棵前缀树 2 )前缀树节点增加 fail 指针 3 ) fail 指针的含

    2023年04月25日
    浏览(43)
  • D. Bracket Coloring

    判断是否可以将字符串s分成若干字子串,使每个子串或每个翻转的子串是合法的括号序列。 首先要知道如何判断一个括号序列是否是合法,共有两个条件: 1.左括号数=右括号数 2.对于任意位置i,i前的左括号数一定大于等于右括号数(即右括号数不大于左括号数) 这个字符

    2024年02月10日
    浏览(29)
  • D. Lucky Permutation(置换环)

    D. Lucky Permutation 严格鸽题解大家可以看看这篇题解,有图片辅助,写的十分的好 题意:给我们一个数长度为n的数组,我们每次操作可以任选两个数进行交换。问我们最后得到满足逆序对是一的序列的最小操作次数是多少。 思路:我们不难知道每次交换两个相邻的数就会形成

    2023年04月16日
    浏览(65)
  • D. Maximum Distance(最小生成树)

    Problem - D - Codeforces   Chouti已经厌倦了乏味的作业,于是他打开了数年前创建的一个旧编程问题。 给定一个具有n个节点和m条加权边的连通无向图。其中有k个特殊节点:x1,x2,...,xk。 现在定义路径的成本为其边权的最大值。两个顶点之间的距离定义为连接它们的路径的最小成本

    2024年02月01日
    浏览(45)
  • D. Problem with Random Tests

    Problem - 1743D - Codeforces   思路:因为是或,所以答案一定会比原串更大,并且为了保留更多的1,我们可以选择原串作为其中一个串,另一个串则要找到第一个为0的位置,我们希望让这个为1,为了让这个位置在或之后为1,需要满足两个条件,假设这个位置为id,那么首先要满

    2024年02月12日
    浏览(41)
  • D. Paths on the Tree

    Problem - 1746D - Codeforces 思路:先分析一下题意,根据第一条性质,每次只能够从1开始,而第二条性质则表明对于每个节点来说,经过这个节点的子节点的路径条数应该尽量均衡,最大值与最小值相差不能超过1,所以我们考虑,如果当前要选择k个路径,而当前节点有cnt个子节

    2024年02月09日
    浏览(35)
  • pytorch之nn.Conv1d详解

    1、Conv1d 定义 class torch.nn.Conv1d(in_channels, out_channels, kernel_size, stride=1, padding=0, dilation=1, groups=1, bias=True) 自然语言处理中一个句子序列,一维的,所以使用Conv1d,此时卷积核(没有batch_size,参数是共享的)除去chanel,也是一维的。  2、参数  in_channels(int) – 输入信号的通道。在

    2024年02月16日
    浏览(42)
  • 第十三届蓝桥杯国赛 C++ C 组 Java A 组 C 组 Python C 组 E 题——斐波那契数组(三语言代码AC)

    如果数组 A = ( a 0 , a 1 , ⋯ . a n − 1 ) A=(a_0,a_1,⋯.a_{n-1}) A = ( a 0 ​ , a 1 ​ , ⋯ . a n − 1 ​ ) 满足以下条件, 就说它是一个斐波那契数组: n ≥ 2 ; n≥2; n ≥ 2 ; a 0 = a 1 a_0=a_1 a 0 ​ = a 1 ​ 对于所有的 i ( i ≥ 2 ) , i(i≥2), i ( i ≥ 2 ) , 都满足 a i = a i − 1 + a i − 2 。 a_i=a_{i-1}+a_{i-2

    2024年01月18日
    浏览(42)
  • pytorch中nn.Conv1d功能介绍

            在使用Conv1d函数时,pytorch默认你的数据是一维的,比如一句话“深度学习”可以用一个一维数组 [\\\'深\\\', \\\'度\\\', \\\'学\\\', \\\'习\\\'] 表示,这个数据就是一维的。图片是二维数据,它有长宽两个维度。         因此在使用 Conv1d 函数时,输入是一个三位数组,三个维度分别表

    2024年02月10日
    浏览(42)
  • D. Li Hua and Tree(set操作)

    Problem - D - Codeforces   李华有一个有n个顶点和n -1条边的树。树的根是顶点1。每个顶点i的重要性为a。将子树的大小表示为该子树中顶点的数量,将重要性表示为该子树中顶点的重要性之和。将非叶顶点的重子结点表示为具有最大子树大小的子结点。如果存在多个重子,则重子

    2023年04月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包