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：路徑
決議
主要思想就是求解最小公倍數，然后再加上一個判斷就可以
- 建圖：共2021個結點組成的圖，列舉任意兩點組合，通過計算最大公約數，記錄這兩個點之間的距離，即增加一條邊，
- 最短路求解：可以使用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：異或數列
決議
- 涉及知識點：動態規劃，取模
- 動態規劃設計：
- 狀態設計： 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
- 注意事項：要增加 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)屬性：數量
狀態計算：
#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)
獲取更多題解，演算法講解歡迎關注公眾號：演算法夢工廠
藍橋杯備賽群：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/400567.html
標籤：python