蓝桥 双周赛算法赛【小白场】

avatar
作者
猴君
阅读量:0
  • 博客主页:誓则盟约
  • 系列专栏:IT竞赛 专栏
  • 关注博主,后期持续更新系列文章
  • 如果有错误感谢请大家批评指出,及时修改
  • 感谢大家点赞👍收藏⭐评论✍ 

蓝桥第14场小白入门赛T1/T2/T3

题目:

T1照常还是送分题无需多言。

T2

问题描述

小蓝,一位热爱阅读的青年,常常沉浸在书的世界里。

这天在他逛书店的时候,发现书店里的每一类书籍都有一定的库存数量,而且部分书籍还被贴上了特别的标签。这些标签往往是一些负面评价,比如“印刷存在错误”或者“页码混乱”等等。

小蓝仔细观察了每个书架,并记录下了每类书籍的库存总数以及被贴特别标签的数量。现在,他需要你的帮助来分析这些数据,找出哪一类书籍被贴上特别标签的比例最低,即从该类书籍中随机选择一本时,拿到带有特别标签书籍的概率最小。

输入格式

输入的第一行包含一个整数 𝑁N (1≤𝑁≤1051≤N≤105),表示书籍的类别数量。

接下来的 𝑁N 行,每行包含两个整数 𝑡𝑖ti​ 和 𝑝𝑖pi​ (1≤𝑝𝑖≤𝑡𝑖≤1001≤pi​≤ti​≤100),分别表示第 𝑖i 类书籍的库存总数和被贴特别标签的数量。

输出格式

输出一个整数,表示被贴特别标签比例最低的书籍类别的索引(索引从 11 开始)。如果有多个答案,则输出索引值最小的那个。

样例输入

3 20 5 30 8 40 10

样例输出

1

样例说明

第 11 类书籍和第 33 类书籍被贴上特别标签的比例最低,为 25%25% 。由于 11 索引值更小,因此输出 11 。

送分题,无需多言。

代码实现:

import os import sys  # 请在此输入您的代码 t=int(input()) ls=1 a_min=0 for i in range(t):     a,b=map(int,input().split())     k=b/a          if k<ls:          ls=k         a_min=i+1 print(a_min)

T3

 

问题描述

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

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

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

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

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

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

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

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

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

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

输入格式

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

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

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

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

输出数据

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

样例输入

5 10110 4 1 2 1 3 2 4 2 5

样例输出 

1 1 0 1

说明

对于第 11 分钟,在重启后第 22 分钟变成 00,说明第 11 分钟重启成功。

对于第 33 分钟,在重启后第 44 分钟依旧是 11,说明第 33 分钟重启失败。

对于第 44 分钟,在重启后第 55 分钟变成 00,说明第 44 分钟重启成功。


思路:首先按照题目输入,如果直接暴力,那只能过8个,所以用到前缀和,根据题意,只要有10字符串,则cnt+=1,所以前缀和遍历,如果有,则+1,否则就是0,最后输出即可 请在此处填写你的解题思路 

代码实现:

import os import sys  # 请在此输入您的代码 # 读取输入   n = int(input().strip())  # 读取字符串长度   s = input().strip()  # 读取01字符串   m = int(input().strip())  # 读取查询次数      # 初始化前缀和数组,初始值为0   li = [0] * n      # 遍历字符串,计算每个位置之前的重启次数(即10对的数量)   for i in range(n - 1):       if s[i] == '1' and s[i + 1] == '0':           li[i] = 1      # 计算前缀和   for i in range(1, n):       li[i] += li[i - 1]      # 处理查询   for _ in range(m):       l, r = map(int, input().strip().split())  # 读取查询的起始和结束位置       l -= 1  # 转换为数组索引(从0开始)       r -= 1  # 同样,r也要转换为数组索引,并且是最后一个有效索引          # 如果l为0,则直接从0开始计数到r-1       # 否则,计算li[r-1] - li[l-1],即[l, r)区间内的重启次数       if l == r:         print(0)  # 注意这里可能会出现l == r的情况,因为左闭右开。     elif l == 0:           print(li[r - 1])       else:           print(li[r - 1] - li[l - 1])

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!