蓝桥杯真题

注意点：
计算机算法：枚举、排序、搜索、计数、贪心、动态规划、图论、数论、博奔论、概率论、计算几何、字符串算法等。
数据结构：数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树、复杂数据结构、嵌套数据结构等。

门牌制作

【问题描述】
小蓝要为一条街的住户制作门牌号。这条街一共有 2020 位住户，门牌号从 1 到 2020 编号。小蓝制作门牌的方法是先制作 0 到 9 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、0、1、7，即需要 1 个字符 0，2 个字符 1，1 个字符 7。
请问要制作所有的 1 到 2020 号门牌，总共需要多少个字符 2？

k=0
for i in range(1, 2021):
    for j in str(i):
        if j=='2':
            k+=1
print(k) # 624

网友解法：

ans = 0
for i in range(1,2021):
    ans += str(i).count("2")
print(ans)

跑步锻炼

【问题描述】
小蓝每天都锻炼身体。正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？
先算出总天数：

或者使用datetime库：

import datetime
sday = datetime.datetime.strptime('2000-1-1', '%Y-%m-%d')
eday = datetime.datetime.strptime('2020-10-1', '%Y-%m-%d')
print(eday-sday)
# 7579 days, 0:00:00

不过，这里的7579只是天数差，而不是总天数。因为本题特别指明了起始日和终止日都是包含着的。而按上述两种算法都会少加一天，如图所示，实际上的总天数应该为天数差+1，如下图的总天数应该为3天：

所以，总天数实际上为7580天。
我的想法很简单，分别算出周一的天数A，月初的天数B，同时为周一和月初的天数C，则A+B-C即为跑2km的天数。
周一的天数A，直接用7579/7取整计算，即A为1082。
月初的天数B直接计算总月份即可表达。注意，2000年到2019年共有20年，240个月；2020年单独有10个月，所以共有250个月份，即250个月初日。
同时为周一和月初的天数C可以借助calendar库计算：

import calendar
count = 0
# 先计算2000年-2019年，每年有12个月
for year in range(2000, 2020):
    for month in range(1, 13):
        a = calendar.monthcalendar(year, month)
        if(a[0][0] == 1):
            count += 1
# 再单独计算2020年，仅有10个月
for month in range(1, 11):
    a = calendar.monthcalendar(2020, month)
    if(a[0][0] == 1):
            count += 1
print(count)
# 34

所以A+B-C为1298天。
那么7580+1298 = 8878天。

标准答案是8879，到底是哪里出了问题？？

蛇形填数

【问题描述】
如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。
1 2 6 7 15 …
3 5 8 14 …
4 9 13 …
10 12 …
11 …
…
容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列的数是多少？

import math
def get_mid_value(k):
    result = 0
    for i in range(k):
        result += i
    result += math.ceil(k/2)
    print(result)
get_mid_value(2*20-1)  # 761

成绩统计

【问题描述】
小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。
如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整数。
【输入格式】
输入的第一行包含一个整数 n，表示考试人数。
接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。
【输出格式】
输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分
四舍五入保留整数。
【样例输入】
7
80
92
56
74
88
100
0
【样例输出】
71%
43%

n = int(input())
num = []
for i in range(0, n):
    num.append(int(input()))
nice = filter(lambda x:x>=85, num)
good = filter(lambda x:x>=60, num)
good_num = round(len(list(good))/n, 2)*100
nice_num = round(len(list(nice))/n, 2)*100
print(str(good_num).split('.')[0] + '%')
print(str(nice_num).split('.')[0] + '%')

单词分析

【问题描述】
小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组成，有些单词很长，远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词，他准备不再完全记忆这些单词，而是根据单词中哪个字母出现得最多来分辨单词。现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这个字母出现的次数。
【输入格式】
输入一行包含一个单词，单词只由小写英文字母组成。
【输出格式】
输出两行，第一行包含一个英文字母，表示单词中出现得最多的字母是哪个。如果有多个字母出现的次数相等，输出字典序最小的那个。
第二行包含一个整数，表示出现得最多的那个字母在单词中出现的次数。
【样例输入】
lanqiao
【样例输出】
a
2
【样例输入】
longlonglongistoolong
【样例输出】
o
6

characters = list(input())
new_strs = [] # 记录唯一字符
maxtime = 1 # 记录最多次数
r = []
# for i in characters:
#     if i not in new_strs:
#         new_strs.append(i)
new_strs = list(set(characters)) # 使用set立刻去重
for i in new_strs:
    c = characters.count(i)
    if c > maxtime:
        maxtime = c
for i in new_strs:
    if characters.count(i) == maxtime:
        r.append(i)
r.sort() # 按字典序排序
print(r[0])
print(maxtime)

小数第n位

原先错误的想法：

x = input().split()
a, b, n = [int(x[i]) for i in range(3)]
t = str(a/b)
point = t.find(".")
x = t[point+n:point+n+3]
if(len(x)==3):
    print(x)
elif(len(x)==2):
    print(x+'0')
elif(len(x)==1):
    print(x+'00')
elif(len(x)==0):
    print('000')

未考虑到 n 过大时的情况，正确的题解为：

def quickPow(a, n): # 快速幂
    res = 1
    while(n):
        if n%2 != 0:
            res *= a
        a *= a          # 翻倍
        n >>= 1         # 二进制右移一位
    return res
a, b, n = map(int, input().split())
mod = b * 1000
print(a * quick(10, n + 2) % (mod) // b)

成绩分析

重点是计算平均分的四舍五入。使用Decimal

from decimal import Decimal
n = int(input())
x = []
for i in range(n):
    x.append(int(input()))
print(max(x))
print(min(x))
avg = Decimal(sum(x)/n).quantize(Decimal("0.01"), rounding="ROUND_HALF_UP")
print(avg)