第十三届蓝桥杯省赛 python B组复盘（三道代码题全AC居然省一了）

获奖感言

芜湖，努力是有结果的，这一个多月慢慢刷题，把数据结构和算法设计一步一步捡起来，也好好学习python的知识

终于一分耕耘一分收获咯，嘻嘻，开心，我居然拿了省一

其实考完以后，我个人感觉有点凉，因为感觉稍微的有点没什么信心，最后一道题没写几乎，倒数第二道题也胡乱写了一通，导致考完我就觉得随缘了，努努力就好了，没有抱太大希望，并且这之后，一点都不敢看这些试题了，给自己好好放松了

结果！！！我居然也有省一哈哈哈，我听到我朋友告诉我，我好开心哈哈，连忙分享给朋友们，也收到了恭喜，不错不错，嘻嘻，运气不错嘻嘻，而且排名也还是可以的，在前3%左右，看起来国奖还是有点希望的。

也有小伙伴跟我说，看了我讲解的视频，也拿了省一，都很不错，希望继续努力，在国赛也能拿个国奖回来。

好咯，开始复盘一下这次的蓝桥杯之路，顺便补补自己的短板，之后，也会出一期讲解视频嘻嘻

接下来所有的题目实际上都可以在C语言网进行提交，这里给出网址[2022年第十三届蓝桥杯大赛软件类省赛Python大学B组真题](2022年第十三届蓝桥杯大赛软件类省赛Python大学B组真题

试题 A：排列字母

思路

这道题其实简单来说，就是一个排序问题，所以我几乎没怎么思考，直接调用sort函数，我后面还仔细看了看，害怕第一道题怎么那么简单哈哈，不过第一道题简单确实正常。

代码

s = "WHERETHEREISAWILLTHEREISAWAY"print(''.join(sorted(s))) # AAAEEEEEEHHHIIILLRRRSSTTWWWY

试题 B：寻找整数

思路

这道题我现在想起来，依旧是心有余悸

当时我觉得最简单就是穷举嘛，反正硬生生穷举，并且考虑到python速度比较慢，我还用了C++来穷举，我想着四个小时起码出来吧，但是我大意了，即使后面我疯狂穷举，一天都还没出来，我无了，麻了。

听说正解是中国剩余定理，我在查资料的时候也看到一些有趣的解法，大家都还是蛮聪明的

有个朋友用暴力也搞了出来，真的人才，只能说这种枚举很聪明，但是感觉可遇不可求，他枚举到了一个等差数列，就是在满足一定条件下的数据是一个等差数列，接着就利用等差数列这个数据进行暴力穷举，30s得出最后答案，大家有兴趣也可以看一看2022第十三届蓝桥杯PythonB组

暴力三步走：

1.枚举数据找规律：取表后面5个大数判断更容易找到大数据，得到关键数据。

2.找出规律求公式：这些数字是按判断求得的，所以一定存在公式。

3.遍历公式找答案：通过公式进行快速遍历，30s轻松找到十六位数的答案。

代码

#1.枚举数据找规律i=1while True:    flag=True    if i%49!=46:        flag=False    if i%48!=41:        flag=False    if i%47!=5:        flag=False    if i%46!=15:        flag=False    if i%45!=29:        flag=False    if flag:        print(i)    i+=1'''47720094290968981047369119185049157322729···'''

#2.找出规律求公式a=[4772009, 42909689, 81047369, 119185049,157322729]#发现存在等差数列print(a[1]-a[0])#38137680print(a[2]-a[1])#38137680print(a[3]-a[2])#38137680k=38137680b=4772009#求出公式y=k

#遍历公式x=0k=38137680b=4772009while True:    flag=True    y=k*x+b    for i,j in mod:        if y%i !=j:            flag=False            break    if flag==True:        print(y)#2022040920220409        break    x+=1

试题 C：纸张尺寸

题目描述

在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm × 841mm，将 A0 纸沿长边对折后为 A1 纸，大小为 841mm × 594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。将 A1 纸沿长边对折后为 A2 纸，依此类推。

输入纸张的名称，请输出纸张的大小。

输入

输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、A3、A4、A5、A6、A7、A8、A9 之一。

输出

输出两行，每行包含一个整数，依次表示长边和短边的长度。

样例输入

A0

样例输出复制

1189841

思路

这道题我觉得，相对于来说，还是比较简单的，因为其实题目已经固定了A0的纸张的大小，之后就是对A0的纸张不断的折叠。然后A后面的数字就是折叠的次数，比如A1是折叠一次，A2是折叠2次。。。

这之中注意两个点，第一，我们是对较长的边进行折叠

第二，就是我们首先输出长边，然后输出短边

代码

s = input() t = int(s[-1]) # 最后一个数字也就是迭代的次数w,h = 1189,841for i in range(t):    if w > h:        w = w//2    else:        h = h//2if w > h:    print(w)    print(h)else:    print(h)    print(w)

大家的代码也可以去这里提交 纸张尺寸

试题 D：数位排序

题目描述

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。

例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。

又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。

给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？

输入

输入第一行包含一个正整数 n。

第二行包含一个正整数 m。

输出

输出一行包含一个整数，表示答案。

样例输入

135

样例输出

3

提示

1 到 13 的排序为：1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9。第 5 个数为 3。

对于 30% 的评测用例，1 ≤ m ≤ n ≤ 300。

对于 50% 的评测用例，1 ≤ m ≤ n ≤ 1000。

对于所有评测用例，1 ≤ m ≤ n ≤ 1 0 6 10^6 106。

思路

我觉得这其实就是一个排序问题，对于python来说，那我值需要设置一个排序规则即可，实际对于C++也有sort函数

所以思路就出来，首先创建我们需要的数组，然后定义一个排序规则，这个排序规则就是依照数位之和排序，所以定义了一个cmp函数计算数位之和，最后输出第m个数字就可以得到答案了

代码

n = int(input())l = [i for i in range(1,n+1)]# 设置一个排序规则，计算数位之和def cmp(x):    ans = 0    while x:        ans += x%10        x = x//10    return ans l.sort(key = cmp)m = int(input())print(l[m-1])

大家的代码也可以去这里提交 数位排序

试题 E：蜂巢

题目描述

蜂巢由大量的六边形拼接而成，定义蜂巢中的方向为：0 表示正西方向，1 表示西偏北 60◦，2 表示东偏北 60◦，3 表示正东，4 表示东偏南 60◦，5 表示西偏南 60◦。

对于给定的一点 O，我们以 O 为原点定义坐标系，如果一个点 A 由 O 点先向 d 方向走 p 步再向 (d + 2) mod 6 方向（d 的顺时针 120◦ 方向）走 q 步到达，则这个点的坐标定义为 (d, p, q)。在蜂窝中，一个点的坐标可能有多种。

下图给出了点 B(0, 5, 3) 和点 C(2, 3, 2) 的示意。

给定点 (d1, p1, q1) 和点 (d2, p2, q2)，请问他们之间最少走多少步可以到达？

输入

输入一行包含 6 个整数 d1, p1, q1, d2, p2, q2 表示两个点的坐标，相邻两个整数之间使用一个空格分隔。

输出

输出一行包含一个整数表示两点之间最少走多少步可以到达。

样例输入

0 5 3 2 3 2

样例输出

7

提示

对于 25% 的评测用例，p1, p2 ≤ 1 0 3 10^3 103 ；
对于 50% 的评测用例，p1, p2 ≤ 1 0 5 10^5 105 ；
对于 75% 的评测用例，p1, p2 ≤ 1 0 7 10^7 107 ；
对于所有评测用例，0 ≤ d1, d2 ≤ 5，0 ≤ q1 < p1 ≤ 1 0 9 10^9 109，0 ≤ q2 < p2 ≤ $10^9 $。

思路

这道题也真是搞脑子呀，当时看到这道题，想了好一会，想了很多种坐标系，结果几乎一个都没有对

在考完试和朋友讨论的时候，他跟我说，这道题可以用向量的想法，真是妙啊，那我们来看看

这样我们就可以将得到的坐标转化成0方向和1方向的向量，之后两个点的距离，就可以用我们的向量相减表示

不过之后，求最近距离的时候又分为两种情况，一种是符号相同的情况，符号相同的时候，也就是a+b或者-a-b这时候我们的距离就是|a+b|，也就是a+b的绝对值

但是对于符号不同的情况，我们就要取max(|a|,|b|)了，这里大概画图理解一下

代码

d1,p1,q1,d2,p2,q2=map(int,input().split())# 全部转化为0 方向 和 1方向的向量def change(d,p,q):    if d==0:return (p-q,q)    if d==1:return (-q,p)    if d==2:return (-p,p-q)    if d==3:return (q-p,-q)    if d==4:return (q,-p)    if d==5:return (p,q-p)s1=change(d1,p1,q1)s2=change(d2,p2,q2)# 向量的剑法s=[s1[0]-s2[0],s1[1]-s2[1]]a,b=s[0],s[1]if a*b > 0: # ab同号    print(abs(a+b))else: # ab异号  print(max(abs(a),abs(b)))

大家的代码也可以去这里提交 蜂巢

试题 F：消除游戏

题目描述

在一个字符串 $S$ 中，如果 S i = S i − 1 S_i = S_{i−1} Si​=Si−1​ 且 S i ≠ S i + 1 S_i \ne S_{i+1} Si​​=Si+1​，则称 S i S_i Si​ 和 S i + 1 S_{i+1} Si+1​ 为边缘字符。如果且 S i ≠ S i − 1 S_i \ne S_{i-1} Si​​=Si−1​ ， S i = S i + 1 S_i = S_{i+1} Si​=Si+1​，则 S i − 1 S_{i−1} Si−1​ 和 S i S_i Si​ 也称为边缘字符。其它的字符都不是边缘字符。

对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符（操作后可能产生新的边缘字符）。

请问经过 2 64 2^{64} 264 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则输出 EMPTY。

输入

输入一行包含一个字符串 S 。

输出

输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。

样例输入

edda

样例输出

EMPTY

样例输入

sdfhhhhcvhhxcxnnnnshh

样例输出

s

提示

对于 25% 的评测用例，|S | ≤ 1 0 3 10^3 103 ，其中 |S | 表示 S 的长度；

对于 50% 的评测用例，|S | ≤ 1 0 4 10^4 104；

对于 75% 的评测用例，|S | ≤ 1 0 5 10^5 105 ；

对于所有评测用例，|S | ≤ 1 0 6 10^6 106，S 中仅含小写字母。

思路

其实这道题，我当时的想法很简单，就是暴力枚举嘛，简单暴力法

不断地进行判断，所以首先就定义一个函数，这个函数就是一个操作，然后再循环迭代2的64次方次，不过这里会涉及一个判断，如果发现，进行操作后，得到的字符串和上一次的字符串一样的时候，就说明不需要再次进行操作了，这时候就直接退出，得到我们的结果。

不过提交以后发现应该只能过75%的数据，不过能拿 3/4 的分也很不错了，这时候可以想想有什么好一点的算法

代码

能过75%的数据

s = input()def f(x):    s = set()    for i in range(1,len(x)-1):        if (x[i] == x[i-1] and x[i] != x[i+1]):            s.add(i)            s.add(i+1)        elif (x[i] != x[i-1] and x[i] == x[i+1]):            s.add(i-1)            s.add(i)     sr = ''    for i in range(len(x)):        if i not in s:            sr += x[i]    return srimport copy# 2的64次方操作for i in range(1<<64):    pre = copy.copy(s)    s = f(s)    if s == '':        print('EMPTY')        break    elif pre == s:        print(s)        break

大家的代码也可以去这里提交 消除游戏

试题 G：全排列的价值

题目描述

对于一个排列 A = (a1, a2, · · · , an)，定义价值 ci 为 a_1 至 a i − 1 a_{i−1} ai−1​ 中小于 a i a_i ai​ 的数的个数，即 bi = |{ a j a_j aj​ | j < i, a j a_j aj​ < a i a_i ai​}|。定义 A 的价值为_ ∑ i = 1 n c i \sum _{i=1}^nc_i ∑i=1n​ci​。

给定 n，求 1 至 n 的全排列中所有排列的价值之和。

输入

输入一行包含一个整数 n 。

输出

输出一行包含一个整数表示答案，由于所有排列的价值之和可能很大，请输出这个数除以 998244353 的余数。

样例输入

3

样例输出

9

提示

1 至 3 构成的所有排列的价值如下:

(1, 2, 3) : 0 + 1 + 2 = 3 ；

(1, 3, 2) : 0 + 1 + 1 = 2 ；

(2, 1, 3) : 0 + 0 + 2 = 2 ；

(2, 3, 1) : 0 + 1 + 0 = 1 ；

(3, 1, 2) : 0 + 0 + 1 = 1 ；

(3, 2, 1) : 0 + 0 + 0 = 0 ；

故总和为 3 + 2 + 2 + 1 + 1 = 9。

对于 40% 的评测用例，n ≤ 20 ；

对于 70% 的评测用例，n ≤ 5000 ；

对于所有评测用例，2 ≤ n ≤ $10^6 $。

思路

其实这道题，我是从蜂巢那里调过来的，先做了消除游戏和这道题

这道题我的历程还蛮奇怪的，我本来应该很快写对的，但是由于我最后结果没有MOD 998244353，所以一直以为自己是错的，然后进行一个验证，思路的整理，从二维慢慢的压缩成一维，一直害怕时间超限等问题，就不断优化，最后发现结果没有MOD，惨兮兮，不过最好还好，最后用了一个O（n）的代码，是完全AC的

这道题呢，实际上就是一个DP的问题，还是一道比较简单的DP问题，n+1的状态是可以从n的状态推导过来的，这里我简单的写了一下我的思路和推导的过程。

以我的思路来看，可以得到这样的动态转移方程
$$dp[n]=dp[n-1]\ast n+(0+1+..+n-1)\ast (n-1的全排列数)$$
再简化一下，就可以变成
$$dp[n]=dp[n-1]\ast n+n\ast (n-1)/2\ast (n-1)!$$
所以我们只需要每次记录一下全排列的个数就可以了，由于n-1的全排列数为n-1！，所以我们计算的时候，随着循环递增即可。

最后一定要记得，把我们的MOD取上，我一开始就是因为这个，以为自己错了。

代码

MOD = 998244353n = int(input())ans = 2 #初始化为2的阶乘dp = [0]*(n+3)dp[1] = 0dp[2] = 1for i in range(3,n+1):    dp[i] = (dp[i-1]*i + ans*i*(i-1)//2) % MOD #动态转移方程    ans = (ans*i)%MOD # 计算全排列数print(dp[n]%MOD) # 输出结果，结果一定要取模

大家的代码也可以去这里提交 全排列的价值

之后的，我感觉我需要好好思考，写出一个较为正确的答案再跟大家分享

试题 H：技能升级

题目描述

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数都会减少 Bi。 ∣ A i B i ∣ |\frac{A_i}{B_i}| ∣Bi​Ai​​∣(上取整) 次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力？

输入

输入第一行包含两个整数 N 和 M。

以下 N 行每行包含两个整数 Ai 和 Bi。

输出

输出一行包含一个整数表示答案。

样例输入

3 610 59 28 1

样例输出

47

提示

对于 40% 的评测用例，1 ≤ N, M ≤ 1000；

对于 60% 的评测用例，1 ≤ N ≤ 104 , 1 ≤ M ≤ 107；

对于所有评测用例，1 ≤ N ≤ 105，1 ≤ M ≤ 2 × 109，1 ≤ Ai , Bi ≤ 106。

思路

首先来说，我先自己做了一下，然后想到一个根据优先队列的做法，我只需要每次取得最优的，那我从某种意义来说，我们最后的结果就是最优的。

所以构建一个最大堆，然后每次取到最大的数，然后再push一个数进去，就是我们会更新我们的数，不过我们这个堆，一直都只有n个数据，我们把最大的pop出来以后，我们就可以进行更新，比如说减去b，或者变成0后不再进行技能升级。

所以依靠这样的想法，我就写了一下，而且我们在想，这样子，我们的读入数据是O（n），处理数据加上一个堆的排序，可能是nlogn，这样子应该是可以的。

这里提一下，我觉得最小堆和最大堆他是可以互换的，由于我好想发现heapq的最大堆没有push操作，那我就把数变成负的，这样我就利用最小堆构建了一个最大堆，因为加了一个负号后，最大的就变成最小的了

代码

import heapqn,m = map(int,input().split())a,b = [],[]heap = []for i in range(n):    x,y = map(int,input().split())    a.append(x)    b.append(y)    heapq.heappush(heap,(-x,i,0))cnt = 0import mathfor i in range(m):    x,y,z = heapq.heappop(heap)    if x == 0:        break    x=-x    cnt += x    # x,y = nlargest(1,heap)    if z > math.ceil(a[y]/b[y]):          x = 0        continue    else:        x = x - b[y]    heapq.heappush(heap,(-x,y,z+1))    print(cnt)

试题 I：最长不下降子序列

题目描述

给定一个长度为 N 的整数序列：A1, A2, · · · , AN。现在你有一次机会，将其中连续的 K 个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。

最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。

输入

输入第一行包含两个整数 N 和 K。

第二行包含 N 个整数 A1, A2, · · · , AN。

输出

输出一行包含一个整数表示答案。

样例输入

5 11 4 2 8 5

样例输出

4

提示

对于 20% 的评测用例，1 ≤ K ≤ N ≤ 100；

对于 30% 的评测用例，1 ≤ K ≤ N ≤ 1000；

对于 50% 的评测用例，1 ≤ K ≤ N ≤ 10000；

对于所有评测用例，1 ≤ K ≤ N ≤ 105，1 ≤ Ai ≤ 106。

试题 J：最优清零方案

题目描述

给定一个长度为 N 的数列 A1, A2, · · · , AN。现在小蓝想通过若干次操作将这个数列中每个数字清零。

每次操作小蓝可以选择以下两种之一：

1. 选择一个大于 0 的整数，将它减去 1；

2. 选择连续 K 个大于 0 的整数，将它们各减去 1。

小蓝最少经过几次操作可以将整个数列清零？

输入

输入第一行包含两个整数 N 和 K。

第二行包含 N 个整数 A1, A2, · · · , AN。

输出

输出一个整数表示答案。

样例输入复制

4 21 2 3 4

样例输出复制

6

提示

对于 20% 的评测用例，1 ≤ K ≤ N ≤ 10。

对于 40% 的评测用例，1 ≤ K ≤ N ≤ 100。

对于 50% 的评测用例，1 ≤ K ≤ N ≤ 1000。

对于 60% 的评测用例，1 ≤ K ≤ N ≤ 10000。

对于 70% 的评测用例，1 ≤ K ≤ N ≤ 100000。

对于所有评测用例，1 ≤ K ≤ N ≤ 1000000, 0 ≤ Ai ≤ 1000000。