2022年蓝桥杯Python程序设计B组思路和代码分享

2022年蓝桥杯Python程序设计B组比赛结束了，分享一下题目以及思路。

---

A:排列字母

题目：

本题总分：5 分

【问题描述】
小蓝要把一个字符串中的字母按其在字母表中的顺序排列。
例如，LANQIAO 排列后为AAILNOQ。
又如，GOODGOODSTUDYDAYDAYUP 排列后为AADDDDDGGOOOOPSTUUYYY。
请问对于以下字符串，排列之后字符串是什么？
WHERETHEREISAWILLTHEREISAWAY
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

思路：

排序。

代码：

s = list("WHERETHEREISAWILLTHEREISAWAY")
s.sort()
print("".join(s))
1
2
3

B: 寻找整数

题目：

本题总分：5 分

【问题描述】
有一个不超过 10¹⁷ 的正整数 n，知道这个数除以 2 至 49 后的余数如下表所示，求这个正整数最小是多少。

【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

思路：

正解应该是中国剩余定理，由于过于复杂，我这里提供一种搜索算法，每次增加前n个数的最小公倍数，1s内可以算完。答案是2022040920220409

代码：

import time
import sys
import math
def solution(d):
    a, b = 2,d[2]
    ans = b
    lcm = a
    for i in range(3,50):
        a, b = i, d[i]
        while ans%a != b:
            ans += lcm
        lcm = lcm//math.gcd(lcm,a)*a
        print(ans)
    return

def main():
    d={2:1,3:2,4:1,5:4,6:5,7:4,8:1,9:2,10:9,11:0,12:5,13:10,14:11,15:14,16:9,17:0,18:11,19:18,20:9,21:11,22:11,23:15,24:17,25:9,26:23,27:20,28:25,29:16,30:29,31:27,32:25,33:11,34:17,35:4,36:29,37:22,38:37,39:23,40:9,41:1,42:11,43:11,44:33,45:29,46:15,47:5,48:41,49:46}
    t1 = time.time()
    solution(d)
    t2 = time.time()
    sys.stderr.write(f"Running time: {(t2-t1)*1000}")
    return

if __name__ == "__main__":
    main()

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

C: 纸张尺寸

题目：

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分

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

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

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

【样例输入 1】
A0

【样例输出 1】
1189
841

【样例输入 2】
A1

【样例输出 2】
841
594

思路：

打表即可。

代码：

def solution():
    d = {}
    x = 1189
    y = 841
    for i in range(10):
        if x>y:
            d["A"+str(i)] = [x, y]
            x = x//2
        else:
            d["A"+str(i)] = [y, x]
            y = y//2
    return d
    
def main():
    s = input()
    d = solution()
    print(d[s][0])
    print(d[s][1])
if __name__ == "__main__":
    main()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

D: 数位排序

题目：

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分

【问题描述】
小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。
例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。
又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。
给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？

【输入格式】
输入第一行包含一个正整数 n。第二行包含一个正整数 m。
【输出格式】
输出一行包含一个整数，表示答案。

【样例输入】
13
5

【样例输出】
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 ≤ 10⁶。

思路：

用内置的sort函数，调整key参数。

代码：

def main():
    n = int(input())
    m = int(input())
    s = list(range(1,n+1))
    s.sort(key = lambda x: sum(map(int, list(str(x)))))
    print(s[m-1])
if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9

E: 蜂巢

题目：

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】
蜂巢由大量的六边形拼接而成，定义蜂巢中的方向为：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) 的示意。

给定点 (d₁, p₁, q₁) 和点 (d₂, p₂, q₂)，请问他们之间最少走多少步可以到达？

【输入格式】
输入一行包含 6 个整数 d₁, p₁, q₁, d₂, p₂, q₂ 表示两个点的坐标，相邻两个整数之间使用一个空格分隔。

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

【样例输入】
0 5 3 2 3 2
【样例输出】
7

【评测用例规模与约定】
对于 25% 的评测用例，p₁, p₂ ≤ 10³ ；
对于 50% 的评测用例，p₁, p₂ ≤ 10⁵ ；
对于 75% 的评测用例，p₁, p₂ ≤ 10⁷ ；
对于所有评测用例，0 ≤ d₁, d₂ ≤ 5，0 ≤ q₁ < p₁ ≤ 10⁹，0 ≤ q₂ < p₂ ≤ 10⁹ 。

思路：

把网格转换成直角坐标系，半个六边形作为一个直角坐标系单位长度。

代码：

def solution(d1,p1,q1,d2,p2,q2):
    bu = {0:(-2,0),
          1:(-1,1),
          2:(1,1),
          3:(2,0),
          4:(1,-1),
          5:(-1, -1)}
    x1 = bu[d1][0]*p1+bu[(d1+2)%6][0]*q1
    y1 = bu[d1][1]*p1+bu[(d1+2)%6][1]*q1
    x2 = bu[d2][0]*p2+bu[(d2+2)%6][0]*q2
    y2 = bu[d2][1]*p2+bu[(d2+2)%6][1]*q2
    return abs(x1-x2)//2+abs(y1-y2)//2

def main():
    d1,p1,q1,d2,p2,q2 = map(int, input().split())
    print(solution(d1,p1,q1,d2,p2,q2))
if __name__ == "__main__":
    main()

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

F: 消除游戏

题目：

时间限制: 3.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】
在一个字符串 S 中，如果 S i = S i−₁ 且 S i * S i₊₁ ，则称 S i 和 S i₊₁ 为边缘字符。如果 S i * S i−₁ 且 S i = S i₊₁，则 S
i−₁ 和 S i 也称为边缘字符。其它的字符都不是边缘字符。
对于一个给定的串 S ，一次操作可以一次性删除该串中的所有边缘字符
（操作后可能产生新的边缘字符）。
请问经过 2⁶⁴ 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则输出 EMPTY。

【输入格式】
输入一行包含一个字符串 S 。

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

【样例输入 1】
edda

【样例输出 1】
EMPTY

【样例输入 2】
sdfhhhhcvhhxcxnnnnshh

【样例输出 2】
s
【评测用例规模与约定】
对于 25% 的评测用例，|S | ≤ 10³ ，其中 |S | 表示 S 的长度；对于 50% 的评测用例，|S | ≤ 10⁴ ；
对于 75% 的评测用例，|S | ≤ 10⁵ ；
对于所有评测用例，|S | ≤ 10⁶，S 中仅含小写字母。

思路：

操作次数可以认为是无限大了，写了一个暴力模拟，字符串不变或为空时停止。

代码：

import copy
def solution(s):
    while 1:
        pan = [1]*len(s)
        for i in range(1,len(s)-1):
            if s[i-1]!=s[i] and s[i]==s[i+1]:
                pan[i-1] = 0
                pan[i] = 0
            if s[i-1]==s[i] and s[i]!=s[i+1]:
                pan[i] = 0
                pan[i+1] = 0
        temp = sum(pan)
        if temp == 0:
            return "EMPTY"
        if temp == len(s):
            break
        ns = []
        for i in range(len(s)):
            if pan[i]:
                ns.append(s[i])
        s = copy.deepcopy(ns)
    return "".join(s)
def main():
    s = list(input())
    print(solution(s))
if __name__ == "__main__":
    main()

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

G: 全排列的价值

题目：

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】
对于一个排列 A = (a₁, a₂, · · · , an)，定义价值 ci 为 a₁ 至 ai−₁ 中小于 ai 的数的个数，即 bi = |{a j| j < i, aj < ai}|。定义 A 的价值为${\sum }_{i=1}^n{c}_i$。

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

【输入格式】
输入一行包含一个整数 n 。

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

【样例输入 1】
3

【样例输出 1】
9

【样例输入 2】
2022

【样例输出 2】
593300958

【样例说明】
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⁶ 。

思路：

动态规划题，注意一下，过程中有乘方运算，最后结果非常大，每步都要取模。

代码：

def solution(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    dp = [0, 1]
    jie = 1
    he = 1
    for i in range(2, n):
        jie *= i
        jie %= 998244353
        he += i
        he %= 998244353
        temp = (jie*he+(i+1)*dp[-1])%998244353
        dp.append(temp)
    return dp[-1]
    
def main():
    n = int(input())
    print(solution(n))
if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

H: 技能升级

题目：

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】
小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数都会减少 Bi。⌈ Ai ⌉ (上取整)
次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力？

【输入格式】
输入第一行包含两个整数 N 和 M。 以下 N 行每行包含两个整数 Ai 和 Bi。
【输出格式】
输出一行包含一个整数表示答案。

【样例输入】
3 6
10 5
9 2
8 1

【样例输出】
47

【评测用例规模与约定】
对于 40% 的评测用例，1 ≤ N, M ≤ 1000；
对于 60% 的评测用例，1 ≤ N ≤ 10⁴, 1 ≤ M ≤ 10⁷；
对于所有评测用例，1 ≤ N ≤ 10⁵，1 ≤ M ≤ 2 × 10⁹，1 ≤ Ai, Bi ≤ 10⁶。

思路：

Ai的范围很小，可以记录所有攻击力增加值的可取数，然后从大到小进行升级，感觉复杂度过得去。另一种思路是优先队列，但好像M过于大，复杂度过不去。

代码：

import collections
def solution(m, s):
    d = collections.defaultdict(int)
    for Ai, Bi in s:
        for i in range(Ai//Bi):
            d[Ai-i*Bi] += 1
        d[Ai%Bi] += 1
    keys = sorted(d.keys(), reverse = True)
    i = 0
    ans = 0
    while m>0:
        if m>=d[keys[i]]:
            ans += keys[i]*d[keys[i]]
            m -= d[keys[i]]
        else:
            ans += keys[i]*m
            break
        i += 1
    return ans

def main():
    n, m = map(int, input().split())
    s = []
    for _ in range(n):
        s.append(list(map(int, input().split())))
    print(solution(m, s))
if __name__ == "__main__":
    main()

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

I: 最长不下降子序列

题目：

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】
给定一个长度为 N 的整数序列：A₁, A₂, · · · , AN。现在你有一次机会，将其中连续的 K
个数修改成任意一个相同值。请你计算如何修改可以使修改后的数列的最长不下降子序列最长，请输出这个最长的长度。
最长不下降子序列是指序列中的一个子序列，子序列中的每个数不小于在它之前的数。

【输入格式】
输入第一行包含两个整数 N 和 K。 第二行包含 N 个整数 A₁, A₂, · · · , AN。
【输出格式】
输出一行包含一个整数表示答案。

【样例输入】
5 1
1 4 2 8 5

【样例输出】
4

【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ K ≤ N ≤ 100；对于 30% 的评测用例，1 ≤ K ≤ N ≤ 1000；
对于 50% 的评测用例，1 ≤ K ≤ N ≤ 10000；
对于所有评测用例，1 ≤ K ≤ N ≤ 10⁵，1 ≤ Ai ≤ 10⁶。

思路：

遍历整数序列，对于每一个最长不下降子序列，把序列后面k个数改成子序列中最后一个数，然后继续向后搜索，直到序列结束或者遇到下降的数。

代码：

def solution(n, k, s):
    start = 0
    result = 0
    for i in range(1, n):
        if s[i]<s[i-1]:
            if i+k>=n:
                result = max(result, n-start)
            else:
                for j in range(i+k, n):
                    if s[j]<s[j-1]:
                        break
                if j == n-1:
                    if s[j]<s[j-1]:
                        result = max(result, j-start)
                    else:
                        result = max(result, j-start+1)
                else:
                    result = max(result, j-start)
            start = i
    return result
def main():
    n, k = map(int, input().split())
    s = list(map(int, input().split()))
    print(solution(n, k, s))
    
if __name__ == "__main__":
    main()

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

J: 最优清零方案

题目：

时间限制: 5.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】
给定一个长度为 N 的数列 A₁, A₂, · · · , AN。现在小蓝想通过若干次操作将这个数列中每个数字清零。
每次操作小蓝可以选择以下两种之一：

1. 选择一个大于 0 的整数，将它减去 1；
2. 选择连续 K 个大于 0 的整数，将它们各减去 1。小蓝最少经过几次操作可以将整个数列清零？

【输入格式】
输入第一行包含两个整数 N 和 K。
第二行包含 N 个整数 A₁, A₂, · · · , AN。
【输出格式】
输出一个整数表示答案。

【样例输入】
4 2
1 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。

思路：

肯定是尽量使用操作2，但子序列的操作顺序无法确定，写了一个深度优先搜索，注意时间限制是5s。

代码：

import sys
sys.setrecursionlimit(100000000)
def solution(n, k, s):
    result = float("inf")
    if sum(s) == 0:
        return 0
    pan = 0
    for i in range(n-k+1):
        if all(map(lambda x: x>0, s[i:i+k])):
            pan = 1
            ns = s.copy()
            for j in range(i,i+k):
                ns[j] -= 1
            result = min(result, 1+solution(n,k,ns))
    if pan == 0:
        ns = s.copy()
        for j in range(n):
            if ns[j] > 0:
                ns[j] -= 1
                break
        result = min(result, 1+solution(n,k,ns))
    return result

def main():
    n, k = map(int, input().split())
    s = list(map(int, input().split()))
    result = solution(n, k, s)
    print(result)
    
if __name__ == "__main__":
    main()

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

---