• [1665] 夜神的思考

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • 最近夜神对二进制很感兴趣,于是他每次看到一串只包含1和0的字符串的时候就会想,这串字符串有多少子串是含有k个1的呢。

    你们能不能快速的解决这个问题。

  • 输入
  • 输入数据包含多组,先输入k ( 0 =< k <= 10^6 ) , 再在接下来的一行输入一串只包含1和0的字符串,字符串的长度不超过10^6.
  • 输出
  • 输出一个整数,这个整数就是这串字符串有多少子串是含有k个1的。
  • 样例输入
  • 1
    1010
    2
    01010
    100
    01010
  • 样例输出
  • 6
    4
    0
  • 提示
  • 第一串字符串中,“1”,“1”,“10”,“01”,“10”,“010”都只含有一个1,所以答案输出6
    第二串字符串中,"101", "0101", "1010", "01010",都含有2个1,所以答案为4。
  • 来源
  • hkhv
  • 操作

显示春菜