蓝桥杯系列1——python组真题_python蓝桥杯真题

零

考完复盘，自认为练习真题进步最快。这个可能每个人不一样，仅供参考。
但前期可以先练习一下，做做小题把基础打好。我最开始直接写杨辉三角形，写了差不多一整天，后来练小题有手感后，一个下午能做两题|ू･ω･` )

一

这个博主整理了几乎所有Python组蓝桥杯题目及代码U•ェ•*U，解锁专栏只要10r，物超所值。如果时间充裕，或者想冲击省一前几名，可以支持一下 ᕦ(･ㅂ･)ᕤ
https://bigsmart.blog.csdn.net/article/details/103641497

二

我看代码时看不进去o(╥﹏╥)o，所以看上面博客时主要是看思路，然后自己再手敲一遍。他的思路真的是秒，叹为观止。但其中还有部分没满分的，我请学院老师帮忙拿到了答案，好像蓝桥杯系统老师端口有标答，其他题目没有的可以问问负责老师。

三

练习真题这部分是我耗时最久的部分，因为python语言性质决定了，暴力算法很难拿满分，所以不断优化版本花了较长的时间，但这部分收获也是最大的。

各版块内容

蓝桥杯系列1——python组真题
https://blog.csdn.net/wtyuong/article/details/124547334
蓝桥杯系列2——python基本语法
https://blog.csdn.net/wtyuong/article/details/124553971
蓝桥杯系列3——基础算法
https://blog.csdn.net/wtyuong/article/details/124560369
蓝桥杯系列4——python基础练习
https://blog.csdn.net/wtyuong/article/details/124560407
蓝桥杯系列5——填空题练习
https://blog.csdn.net/wtyuong/article/details/124560438
蓝桥杯系列6——python技巧
https://blog.csdn.net/wtyuong/article/details/124560522

全部

我准备蓝桥杯python组时全部的代码及结果，供时间不太够的同学冲击省一。

https://download.csdn.net/download/WTYuong/85274463

其实博客内容基本都覆盖了，主要是里面是.ipynb文件版本，可以直接跑，并且更方便做笔记。也欢迎在博客下面留言邮箱，如果看到也会发过去滴(╹▽╹)

真题题型

字符串算法、排序算法、递归、最小生成树之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)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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
1
2
3

版本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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3 2
4 3
5 6
6 10
7 20
8 35
9 70
10 126
11 252
1
2
3
4
5
6
7
8
9

版本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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

6
13
1
2

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))
1
2
3
4
5
6
7
8

1111111
00:18:31
1
2

测试

print(3//2)
print(int(3/2))
print('%.2d:%.2d:%.2d'%(13,0,1)) #%.2d格式化输出两位整数
1
2
3

1
1
13:00:01
1
2
3

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=' ')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3 3
0 3
[3, 2, 1]
1 2
[3, 1, 2]
0 2
[3, 1, 2]
3 1 2 
1
2
3
4
5
6
7
8

易错点

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)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

3 3
0 3
1 2
0 2
3 1 2
1
2
3
4
5

PREV-271 括号序列【第十二届】【省赛】【B组】

题目

策略

不会，之后遇到可以直接放弃

1

PREV-263 砝码称重【第十二届】【省赛】【B组】

题目

测试

a = [[0 for _ in range(3)]for _ in range(2)]
print(a)
1
2

[[0, 0, 0], [0, 0, 0]]
1

版本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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3
1 4 6
10
1
2
3

版本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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3
1 4 6
10
1
2
3

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

20200202
20211202
21211212
1
2
3

print(str(i)[::-1][:2]
1

对称迷宫

题目

描述

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

3
ABA
BBB
ABA
2
1
2
3
4
5