零
考完复盘，自认为练习真题进步最快。这个可能每个人不一样，仅供参考。
但前期可以先练习一下，做做小题把基础打好。我最开始直接写杨辉三角形，写了差不多一整天，后来练小题有手感后，一个下午能做两题|ू･ω･` )
一
这个博主整理了几乎所有Python组蓝桥杯题目及代码U•ェ•*U，解锁专栏只要10r，物超所值。如果时间充裕，或者想冲击省一前几名，可以支持一下 ᕦ(･ㅂ･)ᕤ
https://bigsmart.blog.csdn.net/article/details/103641497
二
我看代码时看不进去o(╥﹏╥)o，所以看上面博客时主要是看思路，然后自己再手敲一遍。他的思路真的是秒，叹为观止。但其中还有部分没满分的，我请学院老师帮忙拿到了答案，好像蓝桥杯系统老师端口有标答，其他题目没有的可以问问负责老师。
三
练习真题这部分是我耗时最久的部分，因为python语言性质决定了，暴力算法很难拿满分，所以不断优化版本花了较长的时间，但这部分收获也是最大的。
真题题型
字符串算法、排序算法、递归、最小生成树之prim算法、dfs算法、贪婪算法、动态规划
PREV-282 杨辉三角形【第十二届】【省赛】【B组】
题目
参考
https://blog.csdn.net/weixin_44091134/article/details/116748883
版本1 得分20
# 杨辉三角 超时了得分：20 def output(n): if n == 1: return 1 else: sanjiao=[] for i in range(n): sanjiao.append([1 for _ in range(i+1)]) if i >= 2: for j in range(1,i): sanjiao[i][j]=sanjiao[i-1][j-1]+sanjiao[i-1][j] if sanjiao[i][j] == n: result=(1+i)*i/2+j+1 print(sanjiao) return result N=int(input()) print(int(output(N)))
20 [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 1, 1, 1]] 25
版本2 得分40
# 杨辉三角 二项式定理 M=C(N,i)=n!/((n-i)!i!) 超时了 得分：40 # (sanjiao[i][j]=i!/((i-j)!j!) import math row = 3 max1 = 1 while True: if row%2 !=0: max1 = 2*max1 else: max1 = 2*max1*(row-1)//row print(row,max1) # if max1>515927503: # print(row) row = row+1 if row >11: break
3 2 4 3 5 6 6 10 7 20 8 35 9 70 10 126 11 252
版本3 标答 100分
def C(a,b): # 计算组合值 res=1 tmp=a for j in range(1,1+b): res=res*tmp//j #累除取余j if res > n: return res #大于n已无意义，且防止爆LL tmp = tmp -1 return res def check(k): # 二分该斜行,找到大于等于该值的第一个数 # 左边界2k，右边界为max(l, n)取二者最大，避免右边界小于左边界 l,r=k*2,max(1,n) while l<r : mid =l+r >>1 # print(mid,k) if C(mid ,k)>=n: r=mid else: l=mid+1 if C(r,k)!=n: return False print(r*(r+1)//2+k+1) return True n=int(input()) if n==1: print(1) else: k=16 # 从第16斜行枚举 while not check(k): k=k-1
6 13
PREV-279 时间显示【第十二届】【省赛】【B组】
题目
得分100
n=int(input()) n = n / 1000 H = n // (60*60) M = (n-H*3600)//60 S = n%60 if H > 24: H = H % 24 print('%.2d:%.2d:%.2d'%(H,M,S))
1111111 00:18:31
测试
print(3//2) print(int(3/2)) print('%.2d:%.2d:%.2d'%(13,0,1)) #%.2d格式化输出两位整数
1 1 13:00:01
PREV-276 双向排序【第十二届】【省赛】【B组】
题目
版本1 得分60
# 超时 得分60 def sheng(num,x): a = sorted(num[x-1:]) num[x-1:]=a # print(num) return num def jiang(num,x): b = sorted(num[:x],reverse=True) num[:x]=b return num n,m=map(int,input().split()) num=[i+1 for i in range(n)] for i in range(m): p,q=map(int,input().split()) if p == 0: num = jiang(num,q) else: num = sheng(num,q) for i in range(n): print(num[i],end=' ')
3 3 0 3 [3, 2, 1] 1 2 [3, 1, 2] 0 2 [3, 1, 2] 3 1 2
易错点
num[x-1:x]
左闭右开 (x-1,x-1)
版本2 标答
if __name__ == '__main__': n, m = map(int, input().split()) nums = [i + 1 for i in range(n)] seq = [] # 用于存储操作序列 for _ in range(m): p, q = map(int, input().split()) if p == 0: while seq and seq[-1][0] == 0: q = max(q, seq[-1][1]) seq.pop() while len(seq) > 1 and seq[-2][1] <= q: seq.pop() seq.pop() seq.append((0, q)) elif seq: while seq and seq[-1][0] == 1: q = min(q, seq[-1][1]) seq.pop() while len(seq) > 1 and seq[-2][1] >= q: seq.pop() seq.pop() seq.append((1, q)) k, left, right = n, 1, n for i in range(len(seq)): if seq[i][0] == 0: # 前缀降序 while right > seq[i][1] and left <= right: nums[right - 1] = k # 从后往前设置 right -= 1 k -= 1 else: # 后缀升序 while left < seq[i][1] and left <= right: nums[left - 1] = k # 从前往后设置 left += 1 k -= 1 if left > right: break if len(seq) % 2: # 最后一次操作为前缀降序 while left <= right: nums[left - 1] = k left += 1 k -= 1 else: # 最后一次操作为后缀升序 while left <= right: nums[right - 1] = k right -= 1 k -= 1 print(' '.join(map(str, nums)))
3 3 0 3 1 2 0 2 3 1 2
PREV-271 括号序列【第十二届】【省赛】【B组】
题目
策略
不会，之后遇到可以直接放弃
PREV-263 砝码称重【第十二届】【省赛】【B组】
题目
测试
a = [[0 for _ in range(3)]for _ in range(2)] print(a)
[[0, 0, 0], [0, 0, 0]]
版本1 得分80
# 超时 得分80 n = int(input()) array = list(map(int, input().split())) sum1 = sum(array) a_len = len(array) ans = 0 dp = [[0 for i in range(sum1+1)] for j in range(a_len)] dp[0][array[0]]=1 # no1 for i in range(1,a_len): for j in range(1,sum1+1): dp[i][j]=dp[i-1][j] # copy 对于当前的复制前一个的重量 dp[i][array[i]]=1 # 当前状态是可称的 for j in range(1, sum1+1): # 最大重量为所有砝码重量总和 if(dp[i-1][j]): #pre=1 上一个状态的重量 dp[i][j+array[i]] = 1 # 上一状态的重量在加上当前重量 dp[i][abs(j-array[i])]=1 # 上一个状态的重量减去当前状态的重量 for i in range(1,sum1+1): if(dp[n-1][i]): ans += 1 print(ans) # print(dp)
3 1 4 6 10
版本2 标答
n = eval(input()) weights = [eval(x) for x in input().split()] def solution(weights): counts = set() for weight in weights: to_add = [] to_add.append(weight) for count in counts: same = weight + count different = abs(weight - count) if same not in counts: to_add.append(same) if different not in counts: to_add.append(different) for new_count in to_add: counts.add(new_count) result = len(counts) if 0 in counts: return result -1 return result print(solution(weights))
3 1 4 6 10
PREV-226 回文日期【第十一届】【省赛】【B组】
题目
解题思路
需要给出输入日期的 下一个回文日期 和 下一个 ABABBABA 型的日期 。
所以从输入的数开始，每次循环+1。
用 date 表示输入的数。
输出的第一个数，需要判断 date 是否为合法日期和回文数。
输出的第二个数，除了需要上面的判断外，还需要判断是否为 ABABBABA 型的数。
我们可以使用3个函数判断以上三个条件
一、判断是否为合法日期
判断一个数是否为合法日期，只需要看月份和天数是否能够合法，比如：
1、3、5、7、8、10、12月，有31天；
4、6、9、11月，有30天；
2月 需要单独进行判断，如果年份为 闰年 ，2月有29天，否则2月只有28天。
二、判断是否为回文数
法1：将一个数直接逆序后判断是否相等
法2：
将数字转化为字符串，定义两个指针，分别在左端和右端。
判断左右两端的字符是否一样，如果一样则左右指针都向内移动一位，依次进行判断。
只要有一位不相同，就可以直接返回 false 。
两个指针相遇的时候，代表字符串内的全部字符已经比较完毕，没有需要不相同的，返回 true 。
三、判断 ABABBABA 型数
法1：
直接将这个数分解“强行”判断
法2：
只需判断字符串的第 0 , 2 , 5 , 7 位是否相同，和字符串的第 1 , 3 , 4 , 6 位是否相同
参考
https://blog.csdn.net/ZZZWWWFFF_/article/details/122867786
a=['01','02','03','04','05','06','07','08','09','10','11','12']#月份 b=['01', '02', '03', '04', '05', '06', '07', '08', '09', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '21', '22', '23', '24', '25', '26', '27', '28', '29', '30', '31']#日期 s=[] for i in range(1000,9000): # 月份+日期 if str(i)[::-1][:2] in a and str(i)[::-1][2:] in b: # a是月份，b是日期 # print(str(i),str(i)[::-1]) s.append(str(i)+str(i)[::-1]) # str(i)[::-1]为回文年份 for i in s:#去除不合法二月日期 if i[4:6]=='02': if int(i)%400!=0 and int(i[6:])>28: s.remove(i) if int(i)%400==0 and int(i[6:])>29: s.remove(i) big=['01','03','05','07','08','10','12'] small=['02','04','06','09','11'] for i in s:#去除不合法大小月 if i[4:6] in small and int(i[6:])>30: s.remove(i) if i[4:6] in big and int(i[6:])>31: s.remove(i) N=int(input()) for i in s: # 判断回文日期 if int(i)>N: print(i) break for j in s: # 判断 ABABBABA 型数 if int(j)>N and j[:2]==j[2:4] and j[0]!=j[1]: print(j) break
20200202 20211202 21211212
print(str(i)[::-1][:2]
对称迷宫
题目
描述
wlxsq有一个N*NN∗N的网格迷宫，每一个网格都有一个字母编号。
他要从左上角(1,1)(1,1)出发，走到右下角(n,n)(n,n)，由于wlxsq很懒，所以他每次只会往右或者往下走一格。
由于最后到终点的路径方案太多太多了，所以wlxsq想让你计算出所有不同的对称的路径个数。
例如:N = 3N=3
ABA
BBB
ABA
对称路径6条：有ABABA(2条)、ABBBA(4条)
不同的对称路径有: 有ABABA、ABBBA
输入
第一行输入一个数NN，表示迷宫的大小。
接下来输入N*NN∗N的字母迷宫
输出
输出对称路径的数量
样例
3
ABA
BBB
ABA
输出
2
提示
【评测用例规模与约定】
对于40%40%的数据，2<=N<=112<=N<=11
对于100%100%的数据，2<=N<=182<=N<=18
思路
在这一种题一般先整体深搜一便保存所有路径，然后再判断是不是对称路径，然后再进行判重，但是这是一种完全暴力的方法，这样不仅会超时，还会爆内存，逼近最大的图是18路劲大概有2^18次方条。
尽可能的优化它，于是有了第二种思路。
搜索两遍，第一遍从1,1位置搜索，第二遍从n,n位置搜索，分别保存路径和末尾点，然后再比对末尾点是否相同，路径是否相同，这里的路劲也是一个非常庞大的数据，而且加上判重，优化不好也会超时。
对于数字的判重可以用一个visit数组判断，对于路径呢，用map来判断。
参考
https://blog.csdn.net/weixin_45483201/article/details/104255693
代码
from collections import defaultdict dx=[1,0,-1,0] dy=[0,1,0,-1] dic=defaultdict(int) n=int(input()) def dfs1(x,y,step,path): if x+y==n-1: dic[path]=1 vis[x][path]=1 return for i in range(0,2): if x+dx[i]<n and x+dx[i]>=0 and y+dy[i]<n and y+dy[i]>=0 : dfs1(x+dx[i],y+dy[i],step+1,path+mp[x+dx[i]][y+dy[i]]) ans=int(0) def dfs2(x,y,step,path): global ans if x+y==n-1: if dic[path]==1 and vis[x][path]==1 : ans+=1 dic[path]=0 return for i in range(2,4): if x+dx[i]<n and x+dx[i]>=0 and y+dy[i]<n and y+dy[i]>=0 : dfs2(x+dx[i],y+dy[i],step+1,path+mp[x+dx[i]][y+dy[i]]) mp=[str("") for i in range(n)] vis=[defaultdict(int) for j in range(n)] for i in range(0,n): mp[i]=input() dfs1(0,0,1,""+mp[0][0]) dfs2(n-1,n-1,1,""+mp[n-1][n-1]) print(ans)
3 ABA BBB ABA 2
