2024年第十五屆藍橋杯省賽B組Python題解
一、整體情況說明
2024年第十五屆藍橋杯省賽B組Python組考試共包含8道題目，分為結果填空題和程序設計題兩類。
- 考試時間：4小時
- 編程環境：Python 3.x，禁止使用第三方庫，僅可使用標準庫
- 題型分布：2道結果填空題，6道程序設計題
考試題目涵蓋了進制轉換、動態規劃、模擬、圖論、搜索等多個知識點，旨在考察選手的綜合編程能力和算法思維。
二、題型分布與分值概覽
| 題號 | 題目名稱 | 類型 | 分值 | 涉及知識點 | |
|---|---|---|---|---|---|
| A | 穿越時空之門 | 結果填空題 | 5 | 進制轉換 | |
| B | 數字串個數 | 結果填空題 | 5 | 動態規劃 | |
| C | 連連看 | 程序設計題 | 10 | 模擬、哈希 | |
| D | 神奇鬧鐘 | 程序設計題 | 10 | 模擬、時間處理 | |
| E | 藍橋村的真相 | 程序設計題 | 15 | 模擬、邏輯推理 | |
| F | 魔法巡游 | 程序設計題 | 15 | 圖論、廣度優先搜索 | |
| G | 繳納過路費 | 程序設計題 | 20 | 圖論、最短路徑算法 | |
| H | 純職業小組 | 程序設計題 | 20 | 圖論、拓撲排序 | ([AcWing][1], [博客園][2], [知乎專欄][3], [Dotcpp][4], [力扣 LeetCode][5], [北京語言大學信息科學與技術系][6]) |
三、各題題解與代碼實現
題目A：穿越時空之門
題目描述：從1到2024中，找出那些數字，其二進制表示的數位和等于其四進制表示的數位和的數字個數。
解題思路：遍歷1到2024的每個數字，分別計算其二進制和四進制表示的數位和，若兩者相等，則計數加一。
Python代碼實現：
def digit_sum(n, base):"""計算數字n在指定進制下的數位和"""total = 0while n > 0:total += n % basen //= basereturn totaldef count_equal_sums(limit):"""統計在1到limit中，二進制和四進制數位和相等的數字個數"""count = 0for i in range(1, limit + 1):if digit_sum(i, 2) == digit_sum(i, 4):count += 1return countif __name__ == "__main__":result = count_equal_sums(2024)print(result) # 輸出結果
結果：63
題目B：數字串個數
題目描述：構造一個長度為10000的數字字符串，要求不含數字0，且必須包含數字3和7，求滿足條件的字符串數量，對10^9+7取模。
解題思路：使用動態規劃，定義狀態dp[i][j][k]表示長度為i的字符串中是否包含數字3（j）和數字7（k）的方案數。
Python代碼實現：
def count_strings(length):"""統計滿足條件的數字字符串數量"""MOD = 10**9 + 7dp = [[[0]*2 for _ in range(2)] for _ in range(length+1)]dp[0][0][0] = 1 # 初始狀態for i in range(1, length + 1):for has3 in range(2):for has7 in range(2):for digit in range(1, 10): # 數字1到9new_has3 = has3 or (digit == 3)new_has7 = has7 or (digit == 7)dp[i][new_has3][new_has7] = (dp[i][new_has3][new_has7] + dp[i-1][has3][has7]) % MODreturn dp[length][1][1]if __name__ == "__main__":result = count_strings(10000)print(result) # 輸出結果
結果：157509472
題目C：連連看
題目描述：在一個n×m的矩陣中，統計滿足條件的格子對數目。條件是：兩個格子中的數字相等，且它們的位置滿足|a?c|=|b?d|>0。
解題思路：利用哈希表記錄對角線上的數字出現次數，分別處理主對角線和副對角線。對于每條對角線，統計相同數字出現的次數，使用組合數公式計算滿足條件的格子對數目。
Python代碼實現：
from collections import defaultdictdef count_pairs(matrix):"""統計滿足條件的格子對數目"""n = len(matrix)m = len(matrix[0])diag1 = defaultdict(lambda: defaultdict(int))diag2 = defaultdict(lambda: defaultdict(int))for i in range(n):for j in range(m):val = matrix[i][j]diag1[i - j][val] += 1diag2[i + j][val] += 1def count(diag):total = 0for line in diag.values():for count in line.values():if count > 1:total += count * (count - 1) // 2return totalreturn count(diag1) + count(diag2)if __name__ == "__main__":n, m = map(int, input().split())matrix = [list(map(int, input().split())) for _ in range(n)]result = count_pairs(matrix)print(result) # 輸出結果
題目D：神奇鬧鐘
題目描述：給定一個時間字符串，要求將其調整為一個回文時間，且調整后的時間不小于原時間，求最小的調整次數。
解題思路：從原時間開始，每次增加一分鐘，直到時間字符串變為回文。
Python代碼實現：
def is_palindrome(time_str):"""判斷時間字符串是否為回文"""return time_str == time_str[::-1]def next_minute(h, m):"""獲取下一分鐘的時間"""m += 1if m == 60:m = 0h += 1if h == 24:h = 0return h, mdef format_time(h, m):"""格式化時間為字符串"""return f"{h:02d}{m:02d}"def min_adjustments(h, m):"""計算最小的調整次數"""count = 0while True:time_str = format_time(h, m)if is_palindrome(time_str):return counth, m = next_minute(h, m)count += 1if __name__ == "__main__":time_input = input().strip()h, m = map(int, time_input.split(":"))result = min_adjustments(h, m)print(result) # 輸出結果
題目E：藍橋村的真相
題目描述：在藍橋村中，n名村民圍坐在圓桌旁，每人發表一個聲明，稱他身后的兩人中有一個說真話，一個說假話。求所有可能的真假組合中，說謊者的總數。([CSDN 博客][7])
解題思路：枚舉所有可能的真假組合，驗證每個組合是否滿足所有人的聲明，統計說謊者的數量。
Python代碼實現：
def total_liars(n):"""計算所有可能的真假組合中，說謊者的總數"""from itertools import producttotal = 0for combo in product([0, 1], repeat=n): # 0表示真話，1表示假話valid = Trueliars = 0for i in range(n):next1 = (i + 1) % nnext2 = (i + 2) % nif combo[i] == 0:# 說真話，后兩人中一個真一個假if combo[next1] == combo[next2]:valid = Falsebreakelse:# 說假話，后兩人中不是一個真
::contentReference[oaicite:103]{index=103}
