当前位置：首页 > article >正文

蓝桥杯刷题DAY1：前缀和

article 2025/2/2 11:20:29

所谓刷题，讲究的就是细心

帕鲁服务器崩坏【算法赛】

“那个帕鲁我已经观察你很久了，我对你是有些失望的，进了这个营地，不是把事情做好就可以的，你需要有体系化思考的能力。”

《幻兽帕鲁》火遍全网，成为了一款现象级游戏。

猫猫作为顶级帕鲁自然是首当其冲搭好了游戏私服，叫上好兄弟开始了愉快私服开荒。

但是这个游戏好玩归好玩，服务器有一堆 bug。比如说众所周知的内存泄漏问题。猫猫很无奈，写了一个脚本去检测服务器的内存占用问题，当超过一定数值就自杀。

但是问题又来了，服务器自杀了之后还要猫猫亲自去手动重启，配置守护进程的诸多方法都不适合。

最终，猫猫决定一分钟监听一次服务器端口是否正常放通。并记录下日志。

具体如下：脚本每隔一分钟监听一次服务端口是否正常，如果服务没有正常运行，则输出 1 并重启服务，否则输出 0。

现在日志形如一段 01 字符串，0 代表正常运行，1 代表端口关闭。在定时任务监听中遇到端口关闭时会自动重启一次服务器。

现在拿到日志之后，猫猫想知道 [l,r) 区间内到底有多少次重启成功。（l 为起点时刻，r 为终点时刻。）

注：重启成功为服务从端口关闭状态转换为端口正常运行状态。如果日志的最后一分钟为 1，那么你可以视作最后一分钟为重启失败。

输入格式

第一行输入一个正整数 n。(1≤n≤2×105)

第二行输入一个长度为 n 的 01 字符串 S。(∣S∣=n,si∈{0,1},1≤i≤n)

第三行输入一个正整数 m。(1≤m≤2×105)

接下来 m 行，每行输入两个正整数 l,r，表示区间 [l,r)。(1≤l<r≤n+1)。

输出数据

输出 m 行，表示对于 m 次查询的结果。

样例输入

样例输出

说明

对于第 1 分钟，在重启后第 2 分钟变成 0，说明第 1 分钟重启成功。

对于第 3 分钟，在重启后第 4 分钟依旧是 1，说明第 3 分钟重启失败。

对于第 4 分钟，在重启后第 5 分钟变成 0，说明第 4 分钟重启成功。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M

import os
import sys

# 请在此输入您的代码

if __name__=="__main__":
  n=int(input())
  s=input()
  prefix =[0]*n
  for i in range(1,n):
    if s[i-1]=='1' and s[i]=='0':
      prefix[i]=prefix[i-1]+1
    else:
      prefix[i]=prefix[i-1]
  m=int(input())
  for i in range(m):
    a,b=map(int,input().split())
    if b==n+1:
      print(prefix[b-2]-prefix[a-1])
    else:
      print(prefix[b-1]-prefix[a-1])