【蓝桥杯真题】2021年蓝桥杯省赛A组题目解析+代码（python组）

admin • • Python

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)

      O(n) 的状态转移方程优化成

      O

      (

      1

      )

      O(1)

      O(1) 。

    • 初始状态：

      d

      p

      (

      0

      ,

      0

      )

      =

      1

      dp(0,0) = 1

      dp(0,0)=1

  3. 注意事项：要增加

    v

    i

    s

    vis

    vis 数组用于表示

    d

    p

    dp

    dp 数组每个位置取模前的实际值是否为

    0

    0

    0 ，如果只判断

    d

    p

    dp

    dp 值可能会出现

    d

    p

    dp

    dp 值实际不为

    0

    0

    0 但是因为取模恰好为

    0

    0

    0 的情况（虽然因为这个模数的特殊性，这个情况出现的概率几乎为

    0

    0

    0 ）

代码

num = [0] * 50
def add(x):
    cnt = 0
    while x > 0:
        if x & 1:
            num[cnt] += 1
        cnt += 1
        x >>= 1


T = int(input())

while(T):
    T -= 1
    xorSum = 0
    num = [0] * 50
    tmp = list(map(int, input().split()))
    n = tmp[0]
    for i in range(n):
        add(tmp[i + 1])
        xorSum ^= tmp[i + 1]

    if xorSum == 0:
        print(0)
        continue

    ans = 0
    pos = 0
    for i in range(30, -1, -1):
        if (num[i] & 1):
            pos = i
            break
    if ((n & 1) or (num[pos] == 1)):
        print(1)
    else:
        print(-1)

J：括号序列

在这里插入图片描述

解析

同c++A组括号序列

括号序列的性质：

(1) 左、右括号的数量相等

(2) 任意前缀的左括号数量必须大于等于右括号数量

最少需要添加括号的数量：

(1) 为了尽可能添加少的括号，所以添加的左、右括号不会出现如同“()”的形式。

(2) 从前往后遍历，当前前缀中，若左括号的数量小于右括号的数量，则需要添加对应数量的左括号，若遍历结束后左括号数量大于右括号，则需要添加对应数量的右括号。

添加括号的方案：

(1)左括号与右括号添加的位置方案是相互独立的，不会相互影响，即使左、右括号添加在同一个间隙，因为不能存在"()“的形式，此处只能为类似”))(("的一种形式，故总的方案数等于左括号的方案数 × 右括号的方案数。

(2)单独考虑添加左括号，若以右括号为分割点， 将整个序列进行分割，因为分割后的子串中均为左括号， 添加任意数目的左括号方案数均为一种，那么此时，我们仅需考虑添加不同数量的左括号的方案数即可。

(3)右括号同理

动态规划：

f[i][j]的状态表示：

(1)集合：只考虑前 i 部分，左括号比右括号多 j 个的所有方案的集合(即不同数量的左括号的方案数)

(2)属性：数量

状态计算：

image-20211227222122736 

#python3
MOD = (int)(1e9 + 7)

def add(x, y):  
    return (x + y) % MOD

def brackets():
    f = [[0 for i in range(n + 10)] for i in range(n + 10)]  
    f[0][0] = 1

    for i in range(1, n + 1):
        if str[i] == '(':
            for j in range(1, n + 1):
                f[i][j] = f[i - 1][j - 1]
        else:
            f[i][0] = add(f[i - 1][0], f[i - 1][1])
            for j in range(1, n + 1):
                f[i][j] = add(f[i - 1][j + 1], f[i][j - 1])

    for i in range(n + 1):
        if f[n][i]:
            return f[n][i]

str = list(input())
n = len(str)

str.insert(0, 0)  //使目标字符串下标从 1 开始
ans_l = brackets()

str.reverse()
for i in range(n):
    if str[i] == '(':
        str[i] = ')'
    else:
        str[i] = '('
str.insert(0, 0)  //使目标字符串下标从 1 开始
ans_r = brackets()

print(ans_l * ans_r % MOD)

获取更多题解，算法讲解欢迎关注公众号：算法梦工厂
在这里插入图片描述蓝桥杯备赛群：
在这里插入图片描述

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>