2021年蓝桥杯省赛A组题解（python组）

来自微信公众号：算法梦工厂，二维码见文末，
欢迎加入蓝桥杯备赛群：768245918，获取往届试题，测验资料，算法课程等相关资源，

A：卡片

答案：3181

决议

• 涉及知识点：列举
• 做法：因为首先到达2021张的一定是数字‘1’，所以只需要统计1的个数就可以，

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

B：直线

答案：40257

决议

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

# -*- coding:UTF-8 -*-
# 斜率： 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

C：货物摆放

决议

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

# -*- coding:UTF-8 -*-
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

D：路径

决议

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

1. 建图：共2021个结点组成的图，列举任意两点组合，通过计算最大公约数，记录这两个点之间的距离，即增加一条边，
2. 最短路求解：可以使用Floyd算法或DijkStra算法计算最短路，（这里因为是填空题，建议使用Floyd算法更加好写，可以考虑两个算法都实作用来相互验证）

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

E：回路计数

决议

详见https://mp.weixin.qq.com/s/IsJKGLMkFMKOAlu5YE2mrw试题E

# -*- coding:UTF-8 -*-
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

F：时间显示

决议

简单模拟计算即可

# -*- coding:UTF-8 -*-
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

G：杨辉三角形

决议

资料范围其实比较小，直接计算即可

# -*- coding:UTF-8 -*-
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

H：左孩子右兄弟

决议

可以发现左孩子右兄弟的存盘方法，对于树上的一个节点，它的所有儿子都会按照某种顺序依次成为它的右儿子，右儿子的右儿子，右儿子的右儿子的右儿子…依次类推深度不断增加，所以这里就有一个递回的结论：对于一个节点，只有把它的所有儿子形成的子树中，转化为二叉树深度最深的儿子放到最下边，才会最优，所以对于每个结点的所有儿子顺序选择，只需要选择它的儿子形成的子树中转化成二叉树高度最高的放到最后边就能得到最优答案，

树形DP：

f[u]：以点 u 为根节点，通过 “左孩子右兄弟” 表示法转化成二叉树后的最大高度；

• f[u] = 子节点数量 + 子树转化为二叉树后的最大高度；

def dfs(x):
  ret = 1;
  for i in range(len(u)):
    temp = 1 + dfs(u[x][i]) + len(u[x]) - 1
    ret = max(temp, ret)
  return ret;

n = int(input())
fa = list(map(int, input.split()))
for i in range(n - 1):
    u[fa[i]].append(i + 2);
print(dfs(1) - 1);

I：异或数列

决议

1. 涉及知识点：动态规划，取模
2. 动态规划设计：
   • 状态设计： d p ( i , j ) dp(i,j) dp(i,j) 表示前 i i i 个括号插入若干个括号之后，左括号比右括号多 j j j 个的插入方法数，
   • 状态转移方程： d p ( i , j ) = d p ( i ? 1 , j ? 1 ) dp(i,j) = dp(i-1,j-1) dp(i,j)=dp(i?1,j?1)（ s t r i str_i stri? 是左括号）， d p ( i , j ) = ∑ k = 0 j + 1 d p ( i ? 1 , k ) dp(i,j) = \sum_{k=0}^{j+1}dp(i-1,k) dp(i,j)=∑k=0j+1?dp(i?1,k) （ s t r i str_i stri? 是右括号）
   • 状态转移优化：当 s t r i str_i stri? 是右括号时，因为： d p ( i , j ? 1 ) = ∑ k = 0 j d p ( i ? 1 , k ) dp(i,j-1) = \sum_{k=0}^{j}{dp(i-1,k)} dp(i,j?1)=∑k=0j?dp(i?1,k) ，所以 d p ( i , j ) = d p ( i ? 1 , j + 1 ) + d p ( i , j ? 1 ) dp(i,j) = dp(i-1,j+1) + dp(i,j-1) dp(i,j)=dp(i?1,j+1)+dp(i,j?1) ，相当于是利用一个前缀和来把 O ( n ) O(n)