算法基础——蓝桥杯（python实现，实际上大多数用c++更明白易懂）（第一部分，共12个小题）_蓝桥杯python

1.成绩统计
问题描述:
编写一个程序，建立一个字典，每个字典包含姓名、学号、英语成绩、数学成绩和C++成绩，并通过字典操作平均分最高的学生和平均分最低的学生并且输出。
输入格式：
输入n+1行，第一行输入一个正整数n，表示学生数量；接下来的n行每行输入5个数据，分别表示姓名、学号、英语成绩、数学成绩和C++成绩。注意成绩有可能会有小数。
输出格式：
输出两行，第一行输出平均成绩最高的学生姓名。第二行输出平均成绩最低的学生姓名。
样例输入
2
yx1 1 45 67 87
yx2 2 88 90 99
样例输出：
yx2
yx1
 

list_dict = [{} for i in range(100)]
maxx, minn = 0, 301
maxs, mins = "", ""
summ = 0
num = int(input())
for i in range(0, num):
    list_dict[i]["xm"], list_dict[i]["xh"], list_dict[i]["yy"], list_dict[i]["sx"], list_dict[i]["cpp"] = input().split()
for j in range(0, num):
    summ = float(list_dict[j]["yy"]) + float(list_dict[j]["sx"]) + float(list_dict[j]["cpp"])
    if summ >= maxx:
        maxx = summ
        maxs = list_dict[j]["xm"]
    if summ < minn:
        minn = summ
        mins = list_dict[j]["xm"]
print(maxs)
print(mins)

总结：如果这道题用cpp来写，可以用结构体，在python中，可以利用列表＋字典达到相同的效果。

---

2. 大衍数列
中国古代文献中，曾记载过“大衍数列”, 主要用于解释中国传统文化中的太极衍生原理。
它的前几项是：0、2、4、8、12、18、24、32、40、50 …
其规律是：对偶数项，是序号平方再除2，奇数项，是序号平方减1再除2。
以下的代码打印出了大衍数列的前 100 项。

for i in range(1, 101):
    if i % 2 == 0:
        print("%d " % int((i**2) / 2))
    else:
        print("%d " % int((i**2 - 1) / 2))

输出结果：

0 
2 
4 
8 
12 
18 
24 
32 
40 
50 
60 
72 
84 
98 
112 
128 
....
.....
......

总结：照着公式写就行了。

---

3. 合并检测
新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情，A 国准 备给大量民众进病毒核酸检测。
然而，用于检测的试剂盒紧缺。为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（k 个）采集的标本放到同一个试剂盒中进行检测。
如果结果为阴性，则说明这 k 个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明 至少有一个人为阳性，
需要将这 k 个人的样本全部重新独立检测（从理论上看， 如果检测前 k−1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中 不会利用此推断，而是将 k 个人独立检测），
加上最开始的合并检测，一共使用 了 k + 1 个试剂盒完成了 k 个人的检测。
A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能最节省试剂盒？

m = 4537
minn = 9999999
k, summ, ans = 1, 0, 0
for k in range(1, 101):
    summ = (m - k) / k + 0.01 * m * k + 1
    if summ < minn:
        minn = summ
        ans = k
print(ans)

输出结果：10

总结：这是一个很有实际意义的例子。

---

4.矩阵转置
给定一个n×m矩阵相乘，求它的转置。其中1≤n≤20，1≤m≤20，矩阵中的每个元素都在整数类型（4字节）的表示范围内。
输入格式
第一行两个整数n和m；
第二行起，每行m个整数，共n行，表示n×m的矩阵。数据之间都用一个空格分隔。
输出格式
共m行，每行n个整数，数据间用一个空格分隔，表示转置后的矩阵。
样例输入
2 4
34 76 -54 7
-4 5 23 9
样例输出
34 -4
76 5
-54 23
7 9

list_old = []
list_new = []
list_in = [[] for i in range(20)]
m, n = map(int, input().split())
"""
构造矩阵列表
"""
for i in range(0, m):
    list_old.append(list(map(int, input().split())))
for j in range(0, n):
    list_new.append(list_in[j])
print(list_old)
print(list_new)
"""
转置
"""
for a in range(0, n):
    for b in range(0, m):
        list_new[a].append(list_old[b][a])
print(list_new)
"""
打印
"""
for c in range(0, n):
    for l in range(0, m):
        print(list_new[c][l], end=" ")
    print("")

输出结果：

2 4
34 76 -54 7
-4 5 23 9
[[34, 76, -54, 7], [-4, 5, 23, 9]]
[[], [], [], []]
[[34, -4], [76, 5], [-54, 23], [7, 9]]
34 -4 
76 5 
-54 23 
7 9 

总结：这道转置题要是用cpp里的数组，更加鲜明，用python实现同样也能用numpy库轻松实现，但我还是倔强的用最朴素的方法写出来了，花了不少心思。

---

5. 切面条

一根高筋拉面，中间切一刀，可以得到2根面条。
如果先对折1次，中间切一刀，可以得到3根面条。
如果连续对折2次，中间切一刀，可以得到5根面条。 那么，连续对折10次，中间切一刀，会得到多少面条呢？
提示：找到问题规律进行求解
 

n = int(input())
print(2**n + 1)

结果：

10
1025

总结：看提示↑↑↑

---

6.日志统计
题目描述
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。
其中每一行的格式是：
ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式
第一行包含三个整数 N,D,K。
以下 N 行每行一条日志，包含两个整数 ts 和 id。
输出格式
按从小到大的顺序输出热帖 id。
每个 id 占一行。
输入样例：
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
输出样例：
1
3

from operator import itemgetter
list_log = []
st = [None for i in range(20)]
cnt = [0 for i in range(20)]
n, d, k = map(int, input().split())
for i in range(0, n):
    list_log.append(list(map(int, input().split())))
list_log.sort(key=itemgetter(1,0))
j = 0
for i in range(0, n):
    cnt[list_log[i][1]] += 1
    while list_log[i][0] - list_log[j][0] >= d:
        cnt[list_log[j][1]] -= 1
        j += 1
    if cnt[list_log[i][1]] >= k:
        st[list_log[i][1]] = True
for m in range(0, n):
    if st[m] is True:
        print(m)

结果：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
1
3

总结：这道题说实话，可以用cpp还是尽量别用其他语言，核心思想就是尺取法，一段一段来，要自己敲敲才能体会，算了，不说了，好累。

---

7.蛇形填数
矩阵第二行第二列中的数是5。请你计算矩阵中第20 行第20 列的数是多少？
提示：
当到达边界时，判断它应该向右走还是向下走，向右走完就直接向左下走，向下走完就直接向右上走

list_s = [[] for i in range(250)]
i, j = 0, 0
cnt = 2
list_s[0].append(1)
while cnt < 1000:
    j += 1
    while i != -1 and j != -1:
        list_s[i].append(cnt)
        cnt += 1
        if j == 0:
            break
        i += 1
        j -= 1
        
    i += 1
    while i != -1 and j != -1:
        list_s[i].append(cnt)
        cnt += 1
        if i == 0:
            break
        i -= 1
        j += 1
print(list_s[19][19])

 

 得到结果是：761

总结：其实还可以另辟蹊径，找到数学公式求解，聪明的人总会跟数学之神有缘，相信你也是其中之一，自己看图，我都画的这么形象了，还看不出来，苦海无涯，回头是岸。

---

8.特别数的和
题目描述
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示满足条件的数的和。
数据范围
1≤n≤10000
输入样例：
40
输出样例：
574

def check(n)->bool:
    if str(n).count("2") + str(n).count("0") + str(n).count("1") + str(n).count("9") > 0:
        return True
    return False
 
ans = 0
n = int(input())
for i in range(1, n+1):
    if (check(i)):
        ans += i
print(ans)
        

总结：这道题的一般思想是求出每一位上的数字，求余，但python可以用字符数统计实现，只能说各有千秋吧。
 

---

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

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

结果是：624

总结：跟上面一道题一毛一样，就算化成灰我也认得出来。

---

10.微生物增殖
假设有两种微生物 X 和 Y
X出生后每隔3分钟分裂一次（数目加倍），Y出生后每隔2分钟分裂一次（数目加倍）。
一个新出生的X，半分钟之后吃掉1个Y，并且，从此开始，每隔1分钟吃1个Y。
现在已知有新出生的 X=10, Y=89，求60分钟后Y的数目。
如果X=10，Y=90呢？
本题的要求就是写出这两种初始条件下，60分钟后Y的数目。
提示：
分析可知，Y分别会在0.5,1.5,2.5······时被吃，所以，把60分钟分成120份，则在除以2余数为1时，Y的数目减少X个

x, y = 10, 90
for i in range(1, 121):
    if y <= 0:
        y = 0
        break
    if i % 2 == 1:
        y -= x
    if i % 4 == 0:
        y *= 2
    if i % 6 == 0:
        x *= 2
print(y)

结果是：94371840

总结：仔细分析过程，找到规律，实在不行，只能看看人家的思路了，总之要理解。

---

11.星期一
整个20世纪（1901年1月1日至2000年12月31日之间），一共有多少个星期一？(不要告诉我你不知道今天是星期几)
提示：
判断1901年1月1日到2000年12月31的每一天是星期几，如果是星期一则统计的个数+1

"""
daysum, dayrun, dayping = 0, 0, 0
day = 2
count = 0
for year in range(1901, 2001):
    if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
        dayrun += 1
    else:
        dayping += 1
daysum = dayrun * 366 + dayping * 365
while day <= daysum - 7:
    count += 1
    day += 7
print(count)
"""
import datetime
a = datetime.date(1901, 1, 1)
b = datetime.timedelta(1)
count = 0
while 1:
    if a.isoweekday() == 1:
        count += 1
    a += b
    if a.year == 2001:
        break
print(count)

结果是：5217

总结：注释的那段代码是一般思路求解，而我则更倾向于python的datetime库，真的很酷，简单易懂，有兴趣大家可以去仔细了解。

我推荐一个python的官方链接，里面有很多模块的文档：

3.10.0 Documentation

---

12.星系炸弹
在X星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。
每个炸弹都可以设定多少天之后爆炸。
比如：阿尔法炸弹2015年1月1日放置，定时为15天，则它在2015年1月16日爆炸。
有一个贝塔炸弹，2014年11月9日放置，定时为1000天，请你计算它爆炸的准确日期。
提示： 
先判断是否为闰年，这会影响2月份是28还是29，如果是闰年，2月份是29，如果不是，就是28
 

list_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
year, month, day = 2014, 11, 9 
tid = 1000
for i in range(0, tid):
    day += 1
    if day > list_month[month - 1]:
        day = 1
        month += 1
        if month > 12:
            month = 1
            year += 1
            if (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0):
                list_month[1] = 29
            else:
                list_month[1] = 28
print("%s-%s-%s" % (year, month, day))
"""
import datetime
a = datetime.date(2014, 11, 9)
b = datetime.timedelta(1000)
a += b
print("%s-%s-%s" % (a.year, a.month, a.day))
"""

结果是：2017-8-5

总结：跟上道题差不多，都是时间题，这次也是一般思路和python特有的思路都给了出来，都是有意义的，尤其是一般思路，要好好看懂，这是本篇最后一题了。

---

今日心得：好久没在电脑前熬夜了，睡了睡了