2018年蓝桥杯省赛试题-5道(Python)

---

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、日志统计

题目描述
小明维护着一个程序员论坛。
现在他收集了一份"点赞"日志，日志共有 N 行。其中每一行的格式是：
ts id
表示在 ts 时刻编号 id 的帖子收到一个"赞"。

现在小明想统计有哪些帖子曾经是"热帖"。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，
小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻 T 满足该帖在
[T,T+D) 这段时间内**(注意是左闭右开区间)**收到不少于 K 个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。

思考

以python角度来处理问题
首先输入的话，input接受参数，外套map来接受多个参数，并指定为int型

N, D, K = list(map(int, input().split()))

然后通过传入的n确定循环次数，将帖子时间和id用列表存储

whole = []
for i in range(N):whole.append(list(map(int, input().split())))

接着使用defaultdict来将键-值对序列转换为列表字典
collections.defaultdict()的使用

d = collections.defaultdict(list)
for i in whole:d[i[1]].append(i[0])

Python中通过Key访问字典，当Key不存在时，会引发‘KeyError’异常。为了避免这种情况的发生，可以使用collections类中的defaultdict()方法来为字典提供默认值。

解读以下代码

for key, value in d.items():if len(value) < K:continuetemp = []value.sort()for i in value:temp.append(i)while i - temp[0] >= D:temp.pop(0)if len(temp) >= K:result.append(key)break

先进行if判断，如果出现的时间点个数都少于所需赞的个数，那后续更难满足其条件了

    if len(value) < K:continue

之后的代码逻辑我是这样理解的
遍历循环时，temp存储临时的ts
while判断i和临时ts之间的差值是否大于题目时间要求，超过则pop出栈顶元素，也就是第一个元素

for i in value:temp.append(i)while i - temp[0] >= D:temp.pop(0)

这样最后的列表temp若存储个数能超过或等于K，说明满足要求
用result列表存储

完整代码

import collections
result = []
N, D, K = list(map(int, input().split()))
whole = []
for i in range(N):whole.append(list(map(int, input().split())))d = collections.defaultdict(list)
for i in whole:d[i[1]].append(i[0])print(d.items())
for key, value in d.items():if len(value) < K:continuetemp = []value.sort()for i in value:temp.append(i)while i - temp[0] >= D:temp.pop(0)if len(temp) >= K:result.append(key)breakresult.sort()
for i in result:print(i)

二、递增三元组

思考

import os
import sys
import bisect# 请在此输入您的代码
N = eval(input())
a = sorted(list(map(int,input().split())))
b = sorted(list(map(int,input().split())))
c = sorted(list(map(int,input().split())))s = 0
for i in range(N):n1 = bisect.bisect_left(a,b[i])n2 = N-bisect.bisect_right(c,b[i])s+=n1*n2
print(s)

三、螺旋折线

思考

import os
import sys# 请在此输入您的代码
x,y=map(int,input().split())
n=max(abs(x),abs(y))
if x==-n or y==n:t=n*(n*4-2)+x+y
elif x==n or y==-n:t=n*(n*4+2)-x-y
print(t)

四、乘积最大

思考

mo=int(1e9+9)
def mod(x):if x<0:return -((-x)%mo)return x%mo
n,k=map(int,input().split())
a=[]
for i in range(n):a.append(int(input()))
a.sort()
l,r=0,n-1
ans=1
sign=1
if k%2:ans=a[r]r-=1k-=1if ans<0:sign=-1
while k:x,y=a[l]*a[l+1],a[r]*a[r-1]if x*sign>=y*sign:ans*=x       l+=2else:ans*=yr-=2ans=mod(ans)k-=2
print(ans)

五、全球变暖

思考

import os
import syssys.setrecursionlimit(1000000)  # 修改深度限制，否则会出现段错误！！！ex死我了
n = int(input())
highlands = 0
islands = 0
note = [[0] * n for _ in range(n)]
flag = 0  # 确保回溯时重复确认highlands
picture = []
move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in range(n):picture.append(input())print(picture)
print(note)def DFS(x, y):global flagglobal highlandsif note[x][y] == 1:returnnote[x][y] = 1  # 记录已经遍历过if flag == 0:if picture[x + 1][y] == '#' and picture[x - 1][y] == '#' and picture[x][y + 1] == '#' and picture[x][y - 1] == '#':  # 找到高地highlands += 1flag = 1for i in range(4):xx = x + move[i][0]yy = y + move[i][1]if picture[xx][yy] == '#' and note[xx][yy] == 0:DFS(xx, yy)for x in range(n):for y in range(n):if picture[x][y] == '#' and note[x][y] == 0:print(x,y)islands += 1flag = 0DFS(x, y)print(islands - highlands)

尾声

其他的后续再跟进思路，感觉题目都好难救命