第十六屆藍橋杯大賽軟件賽省賽第二場

大家好。最近參加了第十六屆藍橋杯大賽軟件賽省賽第二場 Python 大學 B 組的比賽，現在來和大家分享一下我的解題思路和代碼實現。以下內容是我自己寫的，可能對也可能錯，歡迎大家交流討論。

試題 A：密密擺放

問題描述：小藍有一個大箱子，內部的長寬高分別是 200、250、240（單位：毫米），他要用這個大箱子來放一些同樣大小的小盒子，小盒子的外部長寬高分別是 30、40、50（單位：毫米）。小盒子允許從各個方向旋轉（包括可以平放和倒放）。請問小藍最多可以在一個大箱子里面放多少個小盒子。

解題思路：這道題可以看作是一個空間利用問題。我們需要找到大箱子和小盒子的最優擺放方式，使得小盒子的數量最多。由于小盒子可以旋轉，我們可以通過枚舉小盒子的擺放方向，計算每種方向下大箱子最多能容納的小盒子數量，然后取最大值即可。

代碼實現：

# 大箱子的長寬高
box = [200, 250, 240]
# 小盒子的長寬高
small_box = [30, 40, 50]# 枚舉小盒子的擺放方向
max_count = 0
for i in range(3):for j in range(3):for k in range(3):# 計算每種方向下大箱子最多能容納的小盒子數量count = (box[0] // small_box[i]) * (box[1] // small_box[j]) * (box[2] // small_box[k])max_count = max(max_count, count)print(max_count)

答案：384

我的答案：5，簡直離譜我

試題 B：脈沖強度之和

問題描述：在藍橋電子工坊，工程師小藍正在設計一款智能脈沖生成器，用于驅動一種新型設備。該設備的運行依賴于特定的脈沖強度，用正整數 p 表示，其必須滿足以下三個條件：

1. 可由連續 10 個正整數之和組成：即存在一個正整數 k，使得脈沖強度 p = k + (k + 1) + (k + 2) + · · · + (k + 9)。
2. 各個數位上的數字都相同：例如 1111、22222、333333 等。
3. 數值不超過 20255202：即 1 ≤ p ≤ 20255202。
   通過計算所有符合條件的脈沖強度之和，小藍能夠優化設備運行模式。對此，請幫助他計算這一總和。

解題思路：這道題需要找到所有符合條件的脈沖強度，并將它們相加。我們可以先根據第一個條件，將脈沖強度表示為連續 10 個正整數之和的形式，即 p = 10k + 45。然后，根據第二個條件，枚舉各個數位上的數字都相同的數，判斷它們是否滿足 p = 10k + 45 的形式，且數值不超過 20255202。

代碼實現：

# 初始化脈沖強度之和
total_sum = 0# 枚舉各個數位上的數字都相同的數
for digit in range(1, 10):  # 數字范圍為 1 到 9for length in range(1, 8):  # 數字長度范圍為 1 到 7（因為 20255202 是 8 位數）# 構造各個數位上的數字都相同的數num = int(str(digit) * length)# 判斷是否滿足 p = 10k + 45 的形式if (num - 45) % 10 == 0 and num <= 20255202:total_sum += numprint(total_sum)

答案：6172835 無語了

試題 C：25 之和

問題描述：小藍最近對求和很著迷，給定一個正整數 n，他想求從 n 開始的連續 25 個整數的和，即 n + (n + 1) + (n + 2) + · · · + (n + 24)，請幫幫他吧。

解題思路：這道題可以直接使用等差數列的求和公式來解決。等差數列的求和公式為：S = (首項 + 末項) × 項數 / 2。在這個問題中，首項為 n，末項為 n + 24，項數為 25。

代碼實現：

n = int(input())
print(int(((n + n + 24) * 25) / 2))

試題 D：旗幟

問題描述：小藍要畫一個 LANQIAO 圖形，并把這個圖形做成一個旗幟。圖形的形狀為一個 h×w 的矩形，其中 h 表示圖形的高，w 表示圖形的寬。當 h = 5, w = 10 時，圖形如下所示：
LANQIAOLAN
ANQIAOLANQ
NQIAOLANQI
QIAOLANQIA
IAOLANQIAO
圖形的規律是：第一行用 LANQIAO 重復填入，第二行開始，每行向左移動一個字符，用 LANQIAO 重復填入。小藍需要把圖形中的每個字母都剪出來，以粘貼到旗幟上，他想知道，給定圖形的高和寬，圖形中有多少個 A。

解題思路：這道題可以通過模擬圖形的生成過程來解決。首先，根據圖形的規律，生成每一行的字符串，然后統計每一行中 A 的個數，最后將所有行中 A 的個數相加即可。

代碼實現：

h, w = map(int, input().split())
s = "LANQIAO"
res = []
for i in range(h):tmp = ""tmp += s[i % 7:]while len(tmp) < w:tmp += sres.append(tmp[:w])
ans = 0
for i in res:ans += (i.count('A'))
print(ans)

試題 E：消消樂

問題描述：小藍正在玩一個叫 “一維消消樂” 的游戲。游戲初始時給出一個長度為 n 的字符串 S = S0S1 · · · Sn?1，字符串只包含字符 A 和 B。小藍可以對這個字符串進行若干次操作，每次操作可以選擇兩個下標 i, j ∈ [0, n ? 1]，如果 i < j 且 Si = A 且 Sj = B，小藍就可以把它們同時消掉。小藍想知道在經過若干次操作后，直到無法對字符串繼續進行操作時，字符串最多剩下多少個字符。

解題思路：這道題可以通過貪心算法來解決。從左到右遍歷字符串，找到第一個 A 和最后一個 B，將它們消掉，然后繼續尋找下一個 A 和 B，直到無法繼續消掉為止。最后剩下的字符數量就是答案。

代碼實現：

S = input()
n = len(S)
ans = n
i, j = 0, n - 1
while i < j:while S[i] != 'A' and i < n:i += 1while S[j] != 'B' and j >= 0:j -= 1if i < j and S[i] == 'A' and S[j] == 'B':ans -= 2i += 1j -= 1
print(ans)

試題 F：數列差分

問題描述：小藍有兩個長度均為 n 的數列 A = {a1, a2, · · ·, an} 和 B = {b1, b2, · · ·, bn}，將兩個數列作差定義為 C = A ? B = {c1 = a1 ? b1, c2 = a2 ? b2, · · ·, cn = an ? bn}。小藍將對數列 B 進行若干次操作，每次操作可以將數列 B 中的任意一個數更改為任意一個整數。在進行完所有操作后，小藍可以按任意順序將數列 B 重排，之后再計算數列 C。小藍想知道，最少操作多少次可以使得數列 C 中的所有數都為正整數。

解題思路：這道題可以通過排序和貪心算法來解決。首先，將數列 A 和 B 按照從小到大的順序排序。然后，從左到右遍歷數列 A 和 B，對于每個位置 i，如果 A[i] - B[i] <= 0，則需要對 B[i] 進行操作，將其更改為一個更小的數，使得 A[i] - B[i] > 0。最后，統計需要操作的次數即可。

代碼實現：

n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B.sort(reverse=True)
res = 0
flag = [False] * n
for j in range(n):is_ok = Falsefor i in range(n):if A[j] - B[i] > 0 and not flag[i]:flag[i] = Trueis_ok = Truebreakif not is_ok:res += 1
print(res)

試題 G：樹上尋寶

問題描述：小藍正在一棵含有 n 個結點的樹的根結點 1 上，他準備在這棵樹上尋寶。結點 i 上有一個物品，價值為 wi。然而，小藍每次尋寶只能從根節點出發走不超過 k 步，每步只能選擇走 1 條邊或者 2 條邊，之后會自動拾取最終停留的結點上的物品并被傳送回根結點。請求出小藍最終能獲得的物品的總價值。

解題思路：這道題可以通過深度優先搜索（DFS）來解決。從根結點出發，使用 DFS 遍歷樹，記錄每個結點的深度。在遍歷過程中，如果當前結點的深度不超過 k，則將該結點的物品價值加入總價值中。最后，返回總價值即可。

代碼實現：

from collections import defaultdictn,k=map(int,input().split())
# print(n,k)
value=list(map(int,input().split()))
# print(value)
tree=defaultdict(list)
# tree=dict(list)
for i in range(n-1):a,b=map(int,input().split())# print(a,b)tree[a].append(b)# print(tree[a])
# print()
# print(tree)
path=defaultdict(list)#當前的節點索引 i 當前已經走過多少邊 j
# now=1
def dfs(i,j):if j>k*2:return path[j].append(i)for w in (tree[i]):dfs(w,j+1)dfs(1,0)
S=set()
for i in range(0,k*2+1):# print(path[i])for x in path[i]:S.add(x)
# print(S)
res=0
# print(value)
for i in S:res+=value[i-1]
print(res)# print(path)'''
7 1
1 1 1 1 1 1 1
1 2
1 3
2 4
2 5
3 6
3 7''''''
8 2
6 3 3 1 5 4 3 4
1 2
2 3
2 4
4 5
5 6
6 7
7 8
'''

試題 H：破解信息

問題描述：在遙遠的未來，星際旅行已經成為常態。宇航員小藍在一次探險任務中，意外發現了一個古老的太空遺跡。遺跡中存放著一個數據存儲器，里面記錄著一段加密的信息。經過初步分析，小藍發現這段信息可以被表示為一個字符串 S，而解密的關鍵，在于找出 S 中字典序最大的回文子序列。

解題思路：這道題可以通過動態規劃來解決。首先，定義一個二維數組 dp，其中 dp[i][j] 表示字符串 S 從第 i 個字符到第 j 個字符的最長回文子序列。然后，根據動態規劃的狀態轉移方程，計算 dp 數組的值。最后，從 dp 數組中找到字典序最大的回文子序列即可。

代碼實現：

S=input()n=len(S)
i,j=0,n-1
left=[]
right=[]
pre=n-1
path=[]for i in range(n):while i<=j:if i==j:left.append(S[i])right=right[::-1]huiwen=left+rightpath.append(huiwen)breakleft.append(S[i])while S[j]!=left[-1] and i<j:j-=1if S[j]==left[-1] and i<j:right.append(S[j])pre=jj-=1else:left.pop(-1)i=i+1j=prei+=1right=right[::-1]huiwen=left+rightpath.append(huiwen)left=[]right=[]j=n-1ans=[]
for i in path:ch=""for j in i:ch+=jans.append(ch)
ans.append(max(list(S)))print(max(ans))