🏆全文目录
试题A:卡片⭐
1 真题
2 解析
3 代码
试题B:直线⭐
1 真题
2 解析
3 代码
试题C:货物摆放⭐
1 真题
2 解析
3 代码
试题D:路径⭐⭐
1 真题
2 解析
3 代码
试题E:回路计数⭐⭐
1 真题
2 解析
3 代码
试题F:时间显示⭐⭐
1 真题
2 解析
3 代码
试题G:杨辉三角形⭐⭐⭐
1 真题
2 解析
3 代码
试题H:左孩子右兄弟⭐⭐
1 真题
2 解析
3 代码
试题I:异或数列⭐⭐⭐
1 真题
2 解析
3 代码
试题 J: 括号序列⭐⭐⭐
1 真题
2 解析
3 代码
试题A:卡片 1 真题2 解析难度系数:⭐
考察题型:枚举
涉及知识点: 字符串:str() 计数方法:.count()
思路分析:
第一题就这么暴力,不愧是BF杯。循环就完事了!
经过一波分析,从材料中“拼11时卡片1已经只有一张了”推理出卡片1最先用光。
原因是:0~9这十张卡片是从1开始拼的,1最先被使用,也就意味着1最先用光。
小蓝得出思路:先循环遍历可以拼出的数字,再将整数格式转换成字符串格式,
接上count()方法统计"1"出现的次数,那么当"1"出现了2021次时,就搞定啦~
3 代码 #卡片cnt=0#计数器:统计1的个数i=1 #从1开始遍历while True: #循环次数未知,用while循环cnt+=str(i).count("1")#.count("1")方法:统计i中"1"出现的次数if cnt>2021: #如果"1"出现超过2021次,说明是卡片1用完了的下一次,找到了关键iprint(i-1)#输出结果3181breaki+=1试题B:直线 1 真题2 解析难度系数:⭐
考察题型:枚举 数论
涉及知识点: 集合docker=set() 斜率截距公式(k,b)
思路分析:
一条普普通通的直线,竟然能变出这么多花样?直线,接招!( •̀ ω •́ )✧
首先创建二维列表存放坐标系,然后二重循环遍历,给每个坐标点赋初值。
因为要统计不同的直线,所以用直线的性质:斜率和截距 来区分,并存放到集合容器里,
最后一点小细节,当斜率不存在时,k会报错,
所以单独计算,最后直接加上20条垂直x轴的直线。
3 代码 #直线M=[[x,y] for x in range(20) for y in range(21)] #创建二维列表:代表xy坐标系d=set()#创建集合属性的容器:因为集合里的元素不会重复for i in M:#二重循环遍历每个坐标x1,y1=i[0],i[1]#注意书写格式:a,b=c,dfor j in M: x2,y2=j[0],j[1] if x1==x2:#特殊情况:直线垂直时斜率不存在,先跳过最后计算 continue k=(y2-y1)/(x2-x1)#斜率公式 b=(x2*y1-x1*y2)/(x2-x1) #截距公式 if (k,b) not in d:#存入容器里没有的(斜率,截距)对 d.add((k,b))print(len(d)+20)#输出结果:容器的长度40237+斜率不存在的20种情况=40257 试题C:货物摆放 1 真题 2 解析难度系数:⭐⭐
考察题型:枚举 数论
涉及知识点: 约数 集合
思路分析:
长宽高,三重循环,枚举暴力,yyds!(´▽`ʃ♡ƪ)
两个知识点:一个是约数,另一个是集合。
1、判断约数算法: n%i==0
约数指的是被整除后没有余数的数。
举个栗子:3%1==0 3%3==0 1和3就是3的约数。
2、创建集合容器方法:docker=set()
选用集合作为容器存放数据,是因为集合的数据不会重复。相同的数据不会重复添加。
3 代码 n=2021041820210418#货物数量cnt=0#count统计值赋初始值0d=set() #容器docker赋予集合属性for i in range(1,int(n**0.5)+1): #循环遍历,筛选n的约数(对n开根号可加快速度)if n%i==0:#如果可被整除,判断为约数d.add(i) #添加约数d.add(n//i)for i in d: #三重循环遍历容器docker里的约数for j in d: for k in d:if i*j*k==n: #满足条件cnt+=1#方案数+1print(cnt)#print(2430) 试题D:路径 1 真题2 解析难度系数:⭐⭐
考察题型:数论 动态规划
涉及知识点:最小公倍数 最短路径
思路分析:
这道题可谓是究极嵌套!融合了最短路径,最小公倍数和动态规划。一个不会就全凉了~
最小公倍数我已经整理成精简模板放代码里了,考试时直接套模板就行。
动态规划经典的做题步骤有5步。
第一步:明白dp[i]的含义
dp[i]#i:结点编号1~2021#dp[i]:当前结点到结点1的最短路径长度 dp[j]#j:结点编号i+1~i+21 #dp[j]:当前结点到结点i的最短路径长度第二步:给dp数组初始化赋值
dp=[float('inf')]*(n+1) #创建列表赋值为无穷大dp[1]=0 #结点1的长度初始化为0第三步:弄清dp[i]遍历的顺序
for i in range(1,n+1): #先遍历结点a:遍历结点1~nfor j in range(i+1,i+22):#再遍历结点b:遍历结点i+1~i+21第四步:搞懂递推公式min()
别看递推公式短短一行,其中包含的信息量巨大!这是最为关键的一步。
(记得先回头去看第一步dp[i],dp[j]的定义,对理解下面的解析很有帮助)
此时dp[j]就在比较两个路径的长度,它只选择最短的那条路走:
第一条路:dp[j],代表之前存在dp列表里的最小路径(当前结点到结点1的最小路径)。
第二条路:dp[i]+lcm(i,j),代表假如现在的dp[i]加上新路lcm(i,j),这时候的路径长度。
比较dp[j]和dp[i]+lcm(i,j)哪条路更短,只走近路(min)的dp[j]就跟它走(╹ڡ╹ )
dp[j]=min(dp[j],dp[i]+lcm(i,j)) #递推公式第五步:打印数组dp[n]
print(dp[n])#输出结果:10266837参考资料:
python的动态规划我是看这个视频学的,学会里面的经典案例,动态规划一通百通~
清华计算机博士带你学习Python算法+数据结构_哔哩哔哩_bilibili
3 代码 #最小公倍数模板(least common multiple)def lcm(a,b):s=a*bwhile b:a,b=b,a%breturn s//a#最短路径(dp)n=2021 #结点数量dp=[float('inf')]*(n+1) #创建列表赋值为无穷大dp[1]=0 #结点1的长度初始化为0for i in range(1,n+1): #结点a:遍历结点1~nfor j in range(i+1,i+22):#结点b:遍历结点i+1~i+21if j>n: #j超出结点范围时break#结束循环dp[j]=min(dp[j],dp[i]+lcm(i,j))#递推公式print(dp[n])#输出结果:10266837试题E:回路计数 1 真题 2 解析难度系数:⭐⭐⭐
考察题型:动态规划 数论
涉及知识点:状态压缩DP 互质
思路分析:
>> 和 > 1 # >>1:相当于(l+r)//2if C(mid, k) >= n:r = midelse:l = mid + 1if C(r, k) != n:return Falseprint(r * (r + 1) // 2 + k + 1)#查找位置return Truen = int(input())if n == 1:print(1)else:for k in range(16,0,-1):#从16斜行枚举if check(k)==True:break 试题H:左孩子右兄弟 1 真题 2 解析难度系数:⭐⭐⭐⭐
考察题型:数据结构 动态规划
涉及知识点:二叉树 树型DP
思路分析:
没有思路肿么办?先暴力破解试试看吧!时间超了也有15分能拿。
先根据题目思路,定义一个树节点类,再初始化结点。
定义一个递归函数,求树的最大高度,最后遍历即可。
一步步转化,求二叉树最高高度->孩子结点个数
3 代码 #树形结构版#定义结点类class node():def __init__(self,val):self.val=val#父结点值self.child=[]#结点孩子tree=[None,node(val=0)] #初始化树#初始化树列表n=int(input())for i in range(2,n+1): m=int(input())tree.append(node(val=m))tree[m].child.append(i)#最大长度-递归函数def maxlen(n:node):if len(n.child)==0:#无孩子,高度为0return 0else:return len(n.child)+max(maxlen(tree[temp]) for temp in n.child)print(maxlen(tree[1])) #从根节点开始遍历 #二维列表法a = [[]for i in range(100001)] #测试数据最大为十万n = int(input())#测试数量:5for i in range(2, n + 1):#结点编号:2,3,4,5fu = int(input())#输入父节点:1,1,1,2a[fu].append(i) #测试结果:[[], [2, 3, 4], [5], [],[]]#树型DPdef dfs(t):ans = 0for i in range(len(a[t])): #t:1 len:3 i:0,1,2ans = max(ans, dfs(a[t][i])+len(a[t]))return ansprint(dfs(1)) 试题I:异或数列 1 真题
2 解析
难度系数:⭐⭐⭐⭐
考察题型:数论 搜索
涉及知识点:位运算 dfs
思路分析:
持续更新中······
参考思路:
蓝桥杯2021年第十二届省赛-异或数列_zy98zy998的博客-CSDN博客_蓝桥杯异或数列
3 代码 #持续更新中······ 试题 J: 括号序列 1 真题 2 解析难度系数:⭐⭐⭐⭐
考察题型:枚举
涉及知识点:模块
思路分析:
持续更新中·······
参考思路:
【蓝桥杯真题】2021年蓝桥杯省赛A组题目解析+代码(python组)_薛崇祥的博客-CSDN博客_2021蓝桥杯省赛python
3 代码 #括号序列MOD = (int)(1e9 + 7)def add(x, y): return (x + y) % MODdef brackets():f = [[0 for i in range(n + 10)] for i in range(n + 10)] f[0][0] = 1for i in range(1, n + 1):if str[i] == '(':for j in range(1, n + 1):f[i][j] = f[i - 1][j - 1]else:f[i][0] = add(f[i - 1][0], f[i - 1][1])for j in range(1, n + 1):f[i][j] = add(f[i - 1][j + 1], f[i][j - 1])for i in range(n + 1):if f[n][i]:return f[n][i]str = list(input())n = len(str)str.insert(0, 0) #使目标字符串下标从1开始ans_l = brackets()str.reverse()for i in range(n):if str[i] == '(':str[i] = ')'else:str[i] = '('str.insert(0, 0) #使目标字符串下标从 1 开始ans_r = brackets()print(ans_l * ans_r % MOD)旅途的最后,小蓝祝愿旅行者们好运连连🌟~