游戏机本当下手

NC213390. 游戏机本当下手

描述

藤原妹红拿到了一个游戏机，游戏机上有'1'和'0'两个按钮。

妹红发现，只要按住某个按钮不放，屏幕上就能一直不断打印那个字符。

比如对于"11111111100000000001111111111"，只需要按住1、再按住0、再按住1就可以打印出来了。这样妹红最少只需要按3次按钮就可以打印这个字符串。

现在妹红拿到了一个01字符串，她想截取其中的一个子串，这个子串最少按 $k\$ 次按钮就可以打印出来。

（01字符串指仅由字符'0'和字符'1'组成的字符串）

注意这里“最少按 $k\$ 次”的含义是：按 $k\$ 次可以打印出这个子串，但按 $k-1\$ 次就一定打印不出这个子串。

妹红想知道，一共有多少子串符合要求？

注：一个字符串的子串为该字符串删掉前面和后面部分字符（也可以不删）生成的字符串。
两个子串只要在字符串中位置不同则认为是不同的（哪怕字符串相等）。

输入描述

第一行两个正整数 和 ，分别代表字符串的长度、和妹红按下按钮的次数。
第二行为一个仅由字符“0”和“1”组成的字符串。

输出描述

妹红至少按 次就能按出来的子串的数量。

示例1

输入:

6 2
001100

输出:

说明:

注意到k=2，因此要寻找最少按2次就能打印的子串。

s[0,2]="001"，妹红最少按2次就能按出来，先按0再按1。

s[0,3]="0011"，妹红最少按2次就能按出来，先按0再按1。
s[1,2]="01"，妹红最少按2次就能按出来，先按0再按1。
s[0,3]="011"，妹红最少按2次就能按出来，先按0再按1。
s[2,4]="110"，妹红最少按2次就能按出来，先按1再按0。
s[2,5]="1100"，妹红最少按2次就能按出来，先按1再按0。
s[3,4]="10"，妹红最少按2次就能按出来，先按1再按0。
s[3,5]="100"，妹红最少按2次就能按出来，先按1再按0。
共有8个子串符合要求。

示例2

输入:

3 1
110

输出:

说明:

注意到k=1，因此要寻找按1次就能打印的子串。

s[0,0]="1"，妹红按住1就可以打印出来，只按了1次按钮

s[0,1]="11"，妹红按住1就可以打印出来，只按了1次按钮
s[1,1]="1"，妹红按住1就可以打印出来，只按了1次按钮
s[2,2]="0"，妹红按住0就可以打印出来，只按了1次按钮
共有4个子串符合要求。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

pypy3 解法, 执行用时: 183ms, 内存消耗: 36560K, 提交时间: 2022-09-25 19:32:42

n,k=map(int,input().split())
ssa=input()
cn=[]
c=1
sn=1
for i in range(len(ssa)-1):
    if ssa[i]==ssa[i+1]:
        c +=1
    else:
        cn.append(c)
        c=1
    sn +=c
cn.append(c)
if k==1:
    print(sn)
else:
    sn=0
    for i in range(len(cn)-k+1):
        sn +=cn[i]*cn[i+k-1]
    print(sn)

Python3 解法, 执行用时: 404ms, 内存消耗: 15152K, 提交时间: 2022-07-27 21:01:38

n, k = map(int, input().split())
str1 = input()
cnt = [1]
for i in range(1,n):
    if str1[i] == str1[i-1]:
        cnt[-1] += 1
    else:
        cnt.append(1)

if k == 1:
    print(sum(map(lambda x:int(x*(x+1)/2), cnt)))
else:
    print(sum(map(lambda x:x[0]*x[1], zip(cnt, cnt[k-1:]))))

上一题

下一题

详情