2021年第十二届蓝桥杯软件类省赛python组试题及其解析。_n = int(input())2 sum = [[0 for i in range(32)] fo

---

一、卡片

本题总分：5分
【问题描述】
小蓝有很多数字卡片，每张卡片上都是数字0到9

小蓝准备用这些卡片来拼一些数，他想从1开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。

小蓝想知道自己能从1拼到多少。

例如，当小蓝有30张卡片，其中0到9各3张，则小蓝可以拼出1到10,但是拼11时卡片1已经只有一张了，不够拼出11

现在小蓝手里有0到9的卡片各2021张，共20210张，请问小蓝可以从1拼到多少？

提示：建议使用计算机编程解决问题。

因为首先到达2021张的一定是数字‘1’，所以只需要统计1的个数就可以。

# -*- coding:UTF-8 -*-
"""
@Project :2021年第十二届蓝桥杯软件类省赛python组试题
@File    :一、卡片.py
@IDE     :PyCharm
@Author  :Kinght_123
@Date    :2021/11/13 11:36
"""

num = 0
for i in range(1, 5000):
    num += str(i).count('1')
    if num >= 2021:
        print(i)
        break




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

---

二、直线

本题总分：5分
【问题描述】
在平面直角坐标系中，两点可以确定一条直线。如果有多点在一条直线上，那么这些点中任意两点确定的直线是同一条。

给定平面上2×3个整点{ ( x , y ) | 0 ≤ x < 2 , 0 ≤ y < 3 , x ∈ Z , y ∈ Z } , 即横坐标是0到1(包含0和1)之间的整数、纵坐标是0到2(包含0和2)之间的整数的点。这些点一共确定了11条不同的直线。

给定平面上20×21个整点{ ( x , y ) | 0 ≤ x < 20 , 0 ≤ y < 21 , x ∈ Z , y ∈ Z},即横坐标是0到19(包含0和19)之间的整数、纵坐标是0到20(包含0和20)之间的整数的点。请问这些点一共确定了多少条不同的直线。

可以求每条的斜率k和截距b，然后进行去重。

# -*- coding:UTF-8 -*-
"""
@Project :2021年第十二届蓝桥杯软件类省赛python组试题
@File    :二、直线.py
@IDE     :PyCharm
@Author  :Kinght_123
@Date    :2021/11/13 11:40
"""
# 斜率： k = (y2 - y1) / (x2 - x1)
# 截距：b = - k * x1 + y1 = (x2 * y1 - x1 * y2) / (x2 - x1)


points = [[i, j] for i in range(20) for j in range(21)]  # 每个点的坐标
res = set()  # 储存结果，并且进行去重
for i in range(len(points)):
    x1, y1 = points[i][0], points[i][1]
    for j in range(i, len(points)):
        x2, y2 = points[j][0], points[j][1]
        if x1 == x2:  # 斜率为无穷时不进行计算
            continue
        k = (y2 - y1) / (x2 - x1)
        b = (x2 * y1 - x1 * y2) / (x2 - x1)
        if (k, b) not in res:
            res.add((k, b))
print(len(res) + 20)





40257
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

---

三、货物摆放

本题总分：10分
【问题描述】
小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有n箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。

小蓝希望所有的货物最终摆成一个大的立方体。即在长、宽、高的方向上分别堆L、W、H的货物，满足n=L×W×H

给定n,请问有多少种堆放货物的方案满足要求。

例如，当n=4时，有以下6种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1

请问，当n=2021041820210418(注意有16位数字)时，总共有多少种方案？

通过分解质数来进行计算，把所有的质数对存储起来，然后进行筛选。

# -*- coding:UTF-8 -*-
"""
@Project :2021年第十二届蓝桥杯软件类省赛python组试题
@File    :三、货物摆放.py
@IDE     :PyCharm
@Author  :Kinght_123
@Date    :2021/11/13 11:54
"""
import time
start = time.perf_counter()
n = int(input())
docker = set()
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        docker.add(i)
        docker.add(n // i)
ans = 0
for i in docker:
    for j in docker:
        for k in docker:
            if i * j * k == n:
                ans += 1
print(ans)
end = time.perf_counter()
print(f"Running time: {end - start} Seconds")






2021041820210418
2430
Running time: 772.9354631 Seconds
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

---

四、路径

本题总分：10分
【问题描述】

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由2021个结点组成，依次编号1至2021

对于两个不同的结点a,b,如果a和b的差的绝对值大于21,则两个结点之间没有边相连；如果a和b的差的绝对值小于等于21,则两个点之间有一条长度为a和b的最小公倍数的无向边相连。

例如：结点1和结点23之间没有边相连；结点3和结点24之间有一条无向边，长度为24;结点15和结点25之间有一条无向边，长度为75.

请计算，结点1和结点2021之间的最短路径长度是多少。

主要思想就是求解最小公倍数，然后再加上一个判断就可以。

# -*- coding:UTF-8 -*-
"""
@Project :2021年第十二届蓝桥杯软件类省赛python组试题
@File    :四、路径.py
@IDE     :PyCharm
@Author  :Kinght_123
@Date    :2021/11/13 12:14
"""

import math


def func(x, y):
    x1, y1 = x, y
    while y1:
        x1, y1 = y1, x1 % y1  # x1为最大公约数
    return x * y // x1


n = int(input())
dp = [float('inf')] * (n + 1)
dp[1] = 0
for i in range(1, n + 1):
    for j in range(i + 1, i + 22):
        if j > n:   # 跳出循环
            break
        dp[j] = min(dp[j], dp[i] + func(i, j))
print(dp[n])








2021
10266837
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

---

五、回路计算

本题总分：15分
【问题描述】

蓝桥学院由21栋教学楼组成，教学楼编号1到21。对于两栋教学楼a和b,当a和b互质时，a和b之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路），请问他有多少种不同的访问方案？两个访问方案不同是指存在某个i,小蓝在两个访问方法中访问完教学楼i后访问了不同的教学楼。

# -*- coding:UTF-8 -*-
"""
@Project :2021年第十二届蓝桥杯软件类省赛python组试题
@File    :五、回路计算.py
@IDE     :PyCharm
@Author  :Kinght_123
@Date    :2021/11/13 12:34
"""
from math import gcd
n = int(input())
m = 1 << n
dp = [[0 for j in range(n)] for i in range(m)]  # dp[i][j]对于状态i，i的二进制表示中为1的位置 表示走过了教学楼j
load = [[False for j in range(n)] for i in range(n)]  # 存储i, j之间是否有路
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if gcd(i, j) == 1:
            load[i - 1][j - 1] = True
dp[1][0] = 1
for i in range(1, m):  # 枚举每一种状态
    for j in range(n):
        if i >> j & 1:  # 判断状态i是否包含第j栋教学楼
            for k in range(n):  # 枚举所有可能从教学楼k走到教学楼j的情况
                if i - (1 << j) >> k & 1 and load[k][j]:  # 判断状态i除去j后是否包含k
                    dp[i][j] += dp[i - (1 << j)][k]
print(sum(dp[m - 1]) - dp[m - 1][0])






21
881012367360
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

---

六、时间显示

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

【问题描述】

小蓝要和朋友合作开发一个时间显示的网站。在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从1970年1月1日00:00:00到当前时刻经过的毫秒数。

现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。

给定一个用整数表示的时间，请将这个时间对应的时分秒输出。

【输入格式】

输入一行包含一个整数，表示时间。

【输出格式】

输出时分秒表示的当前时间，格式形如HH:MM:SS,其中H表示时，值为0到23,MM表示分，值为0到59,SS表示秒，值为0到59时、分、秒不足两位时补前导0

[样例输入1]

46800999

[样例输出1]

13:00:00

[样例输入2]

1618708103123

[样例输出2]

01:08:23

通过计算可以很简单的做出来。

# -*- coding:UTF-8 -*-
"""
@Project :2021年第十二届蓝桥杯软件类省赛python组试题
@File    :六、时间显示.py
@IDE     :PyCharm
@Author  :Kinght_123
@Date    :2021/11/13 12:37
"""

n = int(input())
n //= 1000   # 消除毫秒的影响
day_second = 24 * 60 * 60  # 一天的秒数
n_sencond = n % day_second      # 此时的n为一天之内的秒数
second = n % 60    # 输出秒数

n_minute = n_sencond // 60  # 计算剩下的分钟
minute = n_minute % 60   # 输出分钟

n_time = n_minute // 60  # 计算小时
times = n_time
print('%.2d:%.2d:%.2d' % (times, minute, second))






46800999
13:00:00


1618708103123
01:08:23
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

---

七、杨辉三角

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

【问题描述】

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,

给定一个正整数N,请你输出数列中第一次出现N是在第几个数？

【输入格式】

输入一个整数N.

【输出格式】

输出一个整数代表答案。

【样例输入】

6

【样例输出】

13

# -*- coding:UTF-8 -*-
"""
@Project :2021年第十二届蓝桥杯软件类省赛python组试题
@File    :七、杨辉三角.py
@IDE     :PyCharm
@Author  :Kinght_123
@Date    :2021/11/13 13:02
"""


def find_n(n):
    if n == 1:
        return 1
    res = 3  # 已计算过的个数
    li, l = [1, 2], 3  # 将要进行比对的行的元素及其行数
    while n not in li:
        res += len(li) * 2 - l % 2
        li, l = [1] + [li[i] + li[i + 1] for i in range(len(li) - 1)] + ([li[-1] * 2] if l % 2 == 0 else []), l + 1
    return res + li.index(n) + 1


if __name__ == '__main__':
    n = int(input())
    print(find_n(n))




6
13
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

---

八、左孩子右兄弟

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

【问题描述】

对于一棵多叉树，我们可以通过“左孩子右兄弟”表示法，将其转化成一棵二叉树。

如果我们认为每个结点的子结点是无序的，那么得到的二叉树可能不唯一。换句话说，每个结点可以选任意子结点作为左孩子，并按任意顺序连接右兄弟。

给定一棵包含N个结点的多叉树，结点从1至N编号，其中1号结点是根，每个结点的父结点的编号比自己的编号小。请你计算其通过“左孩子右兄弟”表示法转化成的二叉树，高度最高是多少。注：只有根结点这一个结点的树高度为0。

可能有以下3种(这里只列出3种，并不是全部)不同的“左孩子右兄弟”表示：

其中最后一种高度最高，为4

【输入格式】

输入的第一行包含一个整数N。

以下N-1行，每行包含一个整数，依次表示2至N号结点的父结点编号。

【输出格式】

输出一个整数表示答案。

【样例输入】

5
1
1
1
2

【样例输出】

4

# -*- coding:UTF-8 -*-
"""
@Project :2021年第十二届蓝桥杯软件类省赛python组试题
@File    :七、左孩子右兄弟.py
@IDE     :PyCharm
@Author  :Kinght_123
@Date    :2021/11/13 13:06
"""


class node:
    def __init__(self, val):
        self.val = val
        self.child = []


n = int(input())
tree = [None, node(val=0)]
for i in range(2, n + 1):
    m = int(input())
    tree.append(node(val=m))
    tree[m].child.append(i)


def maxlen(n: node) -> int:
    if len(n.child):
        return len(n.child) + max(maxlen(tree[tmp]) for tmp in n.child)
    return 0  # 在计算上一节点的子节点个数时已计算过，故不在计算节点本身，返回0


print(f'答案为：{maxlen(tree[1])}')





5
1
1
1
2
答案为：4
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

---

九、异或数列

不会做。。。。。。。。
1

---

十、括号序列

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

【问题描述】

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。

例如，对于括号序列(（（）,只需要添加两个括号就能让其合法，有以下几种不同的添加结果：（）（）（）、（）(（）)、(（）)（）、(（）（）)和(（（）））。

【输入格式】

输入一行包含一个字符串s,表示给定的括号序列，序列中只有左括号和右括号。

【输出格式】

输出一个整数表示答案，答案可能很大，请输出答案除以1000000007(即1 0 9 10^910
9
+7)的余数。

【样例输入】

（（（）

【样例输出】

5

【评测用例规模与约定】

对于40%的评测用例，|s|≤200

对于所有评测用例，1≤|s|≤5000

不会做。。。。。。。。。。
1