歡迎交流學(xué)習(xí)~~

---

專欄： 藍(lán)橋杯Python組刷題日寄

---

藍(lán)橋杯進(jìn)階系列：

🏆 Python | 藍(lán)橋杯進(jìn)階第一卷——字符串
🔎 Python | 藍(lán)橋杯進(jìn)階第二卷——遞歸（待續(xù)）
💝 Python | 藍(lán)橋杯進(jìn)階第三卷——?jiǎng)討B(tài)規(guī)劃（待續(xù)）
?? Python | 藍(lán)橋杯進(jìn)階第四卷——圖論（待續(xù)）
🌞 Python | 藍(lán)橋杯進(jìn)階第五卷——數(shù)論（待續(xù)）
🌠 Python | 藍(lán)橋杯進(jìn)階第六卷——貪心（待續(xù)）
💎 Python | 藍(lán)橋杯進(jìn)階第七卷——搜索（待續(xù)）

---

---

🎁 字符串的修改

時(shí)間限制：
1s

內(nèi)存限制：
128MB

題目描述：
設(shè)A和B是兩個(gè)字符串。我們要用最少的字符操作次數(shù)，將字符串A轉(zhuǎn)換為字符串B。這里所說的字符操作共有三種：

1. 刪除一個(gè)字符；
2. 插入一個(gè)字符；
3. 將一個(gè)字符改為另一個(gè)字符。

對(duì)任給的兩個(gè)字符串 A 和 B，計(jì)算出將字符串 A 變換為字符串 B 所用的最少字符操作次數(shù)。

輸入描述：
第一行為字符串 A；第二行為字符串 B；字符串 A 和 B 的長度均小于 200。

輸出描述：
只有一個(gè)正整數(shù)，為最少字符操作次數(shù)。

樣例輸入：

sfdxbqw
gfdgw

樣例輸出：
4

---

解題思路

本題思路如下：

1. 求解兩字符串的最長公共子序列，得到其長度 L；
2. 計(jì)算最少字符操作次數(shù)

本題思路的核心在于 求解兩個(gè)字符串的最長公共子序列。
可以選擇用循環(huán)暴力求解，但是時(shí)間復(fù)雜度過高，容易超時(shí)。因此我們這里可以選用時(shí)間復(fù)雜度更低的動(dòng)態(tài)規(guī)劃方法：

• dp[i][j] 表示 a[:i-1] 和 b[:j-1] 的最長公共子序列的長度 i>0, j>0，對(duì)應(yīng) dp 數(shù)組的大小為 dp[l1+1][l2+1]，l1 和 l2 為兩個(gè)字符串的長度；
• i=0 或 j=0 表示空字符串，此時(shí)公共子序列長度都為 0，因此我們將 dp 數(shù)組都初始化為 0；
• 狀態(tài)轉(zhuǎn)移具體見代碼。

而對(duì)于計(jì)算最終結(jié)果，其計(jì)算方式為：max(l1, l2) - L。
因?yàn)?#xff0c;如果想將較長的字符串變?yōu)檩^短的字符串，除了最長公共子序列，其余字符都需要變化。

參考代碼

a = input()
b = input()
l1 = len(a)
l2 = len(b)
# dp數(shù)組,
# dp[i][j]表示a[:i-1]和b[:j-1]中最長公共子序列的長度(i>0, j>0)
# i=0 和 j=0 表示空字符串，初始化dp數(shù)組為全0
dp = [[0 for j in range(l2 + 1)] for i in range(l1 + 1)]
for i in range(1, l1+1):for j in range(1, l2+1):if a[i-1] == b[j-1]:# a的第i-1個(gè)字符和b的第j-1個(gè)字符相同dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])res = max(l1, l2) - dp[-1][-1]
print(res)

---

🌲 ISBN碼

題目：
時(shí)間限制：
1s

內(nèi)存限制：
128MB

題目描述：
每一本正式出版的圖書都有一個(gè)ISBN號(hào)碼與之對(duì)應(yīng)，ISBN碼包括 9 位數(shù)字、1 位識(shí)別碼和 3 位分隔符，其規(guī)定格式如 x-xxx-xxxxx-x，其中符號(hào) - 就是分隔符（鍵盤上的減號(hào)），最后一位是識(shí)別碼，例如 0-670-82162-4 就是一個(gè)標(biāo)準(zhǔn)的ISBN碼。ISBN碼的首位數(shù)字表示書籍的出版語言，例如 0 代表英語；第一個(gè)分隔符 - 之后的三位數(shù)字代表出版社，例如 670 代表維京出版社；第二個(gè)分隔符后的五位數(shù)字代表該書在該出版社的編號(hào)；最后一位為識(shí)別碼。

識(shí)別碼的計(jì)算方法如下：

首位數(shù)字乘以 1 加上次位數(shù)字乘以 2……以此類推，用所得的結(jié)果 mod 11，所得的余數(shù)即為識(shí)別碼，如果余數(shù)為 10，則識(shí)別碼為大寫字母 X。例如ISBN號(hào)碼 0-670-82162-4 中的識(shí)別碼 4 是這樣得到的：對(duì) 067082162 這 9 個(gè)數(shù)字，從左至右，分別乘以1，2，...,9 ,再求和，即 0×1+6×2+……+2×9=158，然后取158 mod 11的結(jié)果 4 作為識(shí)別碼。

你的任務(wù)是編寫程序判斷輸入的ISBN號(hào)碼中識(shí)別碼是否正確，如果正確，則僅輸出 Right；如果錯(cuò)誤，則輸出你認(rèn)為是正確的ISBN號(hào)碼。

輸入描述：
輸入只有一行，是一個(gè)字符序列，表示一本書的ISBN號(hào)碼（保證輸入符合ISBN號(hào)碼的格式要求）。

輸出描述：
輸出共一行，假如輸入的ISBN號(hào)碼的識(shí)別碼正確，那么輸出 Right ，否則，按照規(guī)定的格式，輸出正確的ISBN號(hào)碼（包括分隔符 -）。

樣例輸入：

0-670-82162-4
0-670-82162-0

樣例輸出：

Right
0-670-82162-4

---

解題思路

本題思路比較簡單，注意細(xì)節(jié)的處理：

• 字符串以 - 分割；
• 當(dāng)計(jì)算出的識(shí)別碼為 10 時(shí)，將其轉(zhuǎn)換為 X；

參考代碼

while True:try:raw = input()s = ''.join(raw.split('-'))id = 0for i in range(len(s)-1):id += int(s[i]) * (i + 1)id %= 11id = str(id)if id == '10':id = 'X'if id == s[-1]:print('Right')else:print(raw[:-1] + id)except:break

---

🚀 完美的代價(jià)

時(shí)間限制：
1s

內(nèi)存限制：
128MB

題目描述：
回文串，是一種特殊的字符串，它從左往右讀和從右往左讀是一樣的。小龍龍認(rèn)為回文串才是完美的?，F(xiàn)在給你一個(gè)串，它不一定是回文的，請(qǐng)你計(jì)算最少的交換次數(shù)使得該串變成一個(gè)完美的回文串。
交換的定義是：交換兩個(gè)相鄰的字符
例如：對(duì)于 mamad：
第一次交換 ad : mamda
第二次交換 md : madma
第三次交換 ma : madam (回文！完美！)

輸入描述：
第一行是一個(gè)整數(shù) N，表示接下來的字符串的長度(N < = 8000)
第二行是一個(gè)字符串，長度為 N，只包含小寫字母

輸出描述：
如果可能，輸出最少的交換次數(shù)。
否則輸出 Impossible

樣例輸入：

5
mamad

樣例輸出：
3

---

解題思路

本題利用雙指針，其中頭指針 head 從前向后遍歷，尾指針 tail 從后向前遍歷。

退出循環(huán)的條件：

• 字符串長度為偶數(shù)，但是有頻數(shù)為奇數(shù)的字母
• 字符串長度為奇數(shù)，但是有多于 1 個(gè)的頻數(shù)為奇數(shù)的字母

具體思路見參考代碼。

參考代碼

n = int(input())
s = list(input())
count = 0   # 記錄交換次數(shù)
flag = 0    # 標(biāo)記是否有字母頻數(shù)為奇數(shù)
res = True	# 標(biāo)記是否為Impossible(是Impossible置為False)# 雙指針
L = n - 1   # 頭指針?biāo)阉鞣秶?#xff0c;到倒數(shù)第2個(gè)
for head in range(L):# 對(duì)于每一個(gè)s[head]，用尾指針去搜索是否有相同的字母s[tail]for tail in range(L, head - 1, -1):# 指針tail搜索完畢，沒有發(fā)現(xiàn)s[head] == s[tail]# 說明該字母頻數(shù)為奇數(shù) 1，且該字母在回文序列中一定在中間if head == tail:# 如果字符串長度為偶數(shù)# 字符串長度為奇數(shù)，但是已經(jīng)有 flag == 1if n%2 == 0 or flag == 1:res = Falsebreakflag = 1# (n//2 - head) 為將該字母移動(dòng)到中間位置的交換次數(shù)count += n//2 - head# 發(fā)現(xiàn)了 s[head] == s[tail]elif s[head] == s[tail]:# 交換位置for i in range(tail, L):s[i], s[i+1] = s[i+1], s[i]count += 1L -= 1break# 如果是impossible，退出外層循環(huán)if res == False:breakif res == False:print('Impossible')
else:print(count)

---

💡 字符串的展開

時(shí)間限制：
1s

內(nèi)存限制：
128MB

題目描述：
在初賽普及組的“閱讀程序?qū)懡Y(jié)果”的問題中，我們曾給出一個(gè)字符串展開的例子：如果在輸入的字符串中，含有類似于 d-h 或者 4-8 的字串，我們就把它當(dāng)作一種簡寫，輸出時(shí)，用連續(xù)遞增的字母獲數(shù)字串替代其中的減號(hào)，即，將上面兩個(gè)子串分別輸出為 defgh 和 45678。在本題中，我們通過增加一些參數(shù)的設(shè)置，使字符串的展開更為靈活。具體約定如下：

• 遇到下面的情況需要做字符串的展開：在輸入的字符串中，出現(xiàn)了減號(hào) -，減號(hào)兩側(cè)同為小寫字母或同為數(shù)字，且按照ASCII碼的順序，減號(hào)右邊的字符嚴(yán)格大于左邊的字符。
• 參數(shù)p1：展開方式。p1=1 時(shí)，對(duì)于字母子串，填充小寫字母；p1=2 時(shí)，對(duì)于字母子串，填充大寫字母。這兩種情況下數(shù)字子串的填充方式相同。p1=3 時(shí)，不論是字母子串還是數(shù)字字串，都用與要填充的字母個(gè)數(shù)相同的星號(hào) * 來填充。
• 參數(shù)p2：填充字符的重復(fù)個(gè)數(shù)。p2=k表示同一個(gè)字符要連續(xù)填充 k 個(gè)。例如，當(dāng) p2=3 時(shí)，子串d-h 應(yīng)擴(kuò)展為 deeefffgggh。減號(hào)兩邊的字符不變。
• 參數(shù)p3：是否改為逆序：p3=1 表示維持原來順序，p3=2 表示采用逆序輸出，注意這時(shí)候仍然不包括減號(hào)兩端的字符。例如當(dāng)p1=1、p2=2、p3=2時(shí)，子串 d-h 應(yīng)擴(kuò)展為 dggffeeh。
• 如果減號(hào)右邊的字符恰好是左邊字符的后繼，只刪除中間的減號(hào)，例如：d-e 應(yīng)輸出為 de，3-4 應(yīng)輸出為 34。如果減號(hào)右邊的字符按照 ASCII碼的順序小于或等于左邊字符，輸出時(shí)，要保留中間的減號(hào)，例如：d-d 應(yīng)輸出為 d-d，3-1 應(yīng)輸出為 3-1。

輸入描述：
輸入包括兩行：
第 1 行為用空格隔開的 3 個(gè)正整數(shù)，一次表示參數(shù) p1，p2，p3。
第 2 行為一行字符串，僅由數(shù)字、小寫字母和減號(hào) - 組成。行首和行末均無空格。

數(shù)據(jù)規(guī)模和約定
100%的數(shù)據(jù)滿足：1<=p1<=3，1<=p2<=8，1<=p3<=2。字符串長度不超過 100

輸出描述：
輸出只有一行，為展開后的字符串.

樣例輸入：

1 2 1
abcs-w1234-9s-4zz

樣例輸出：
abcsttuuvvw1234556677889s-4zz

---

解題思路

• 符號(hào) - 只會(huì)在 s[1:len(s)-1] 之間（s 為輸入字符串），因此要在這個(gè)范圍內(nèi)遍歷，找到符號(hào) - 并將其展開；
• 滿足展開的條件，即要判斷左右兩邊的字符的ASCII碼關(guān)系；
• 之后根據(jù) p3->p1->p2 的判斷順序?qū)φ归_字符進(jìn)行修改。

具體見代碼。

參考代碼

p1, p2, p3 = map(int, input().split())
s = input()
res = s[0]
# '-' 只會(huì)在s[1:len(s)-1]中間，因此s的首尾不需要變化
for i in range(1, len(s)-1):left, mid, right = s[i-1], s[i], s[i+1]# 遇到 '-' 并且左右字符滿足如下條件：# 條件1：left<right# 條件2：(left>='0' and right<='9') or (left>='a' and right<='z') if mid == '-' and left < right and ((left >= '0' and right <= '9') or (left >= 'a' and right <= 'z')):## 判斷順序：p3 -> p1 -> p2## p3if p3 == 1:# 順序index_j = [j for j in range(ord(left)+1, ord(right))]else:# 逆序index_j = [j for j in range(ord(right)-1, ord(left), -1)]## p1for j in index_j:# chr()轉(zhuǎn)為字符tmp = chr(j)if p1 == 2:# 變?yōu)榇髮?/span>tmp = tmp.upper()elif p1 == 3:# 變?yōu)?'*'tmp = '*'## p2# 重復(fù) p2 次res += tmp * p2else:res += mid# 尾巴
res += s[-1]
print(res)

---

🍞 正則問題

時(shí)間限制：
1s

內(nèi)存限制：
128MB

題目描述：
考慮一種簡單的正則表達(dá)式：
只由 x ( ) | 組成的正則表達(dá)式。
小明想求出這個(gè)正則表達(dá)式能接受的最長字符串的長度。

例如：((xx|xxx)x|(x|xx))xx 能接受的最長字符串是： xxxxxx，長度是 6。

輸入描述：
一個(gè)由 x()| 組成的正則表達(dá)式。輸入長度不超過 100，保證合法。

輸出描述：
這個(gè)正則表達(dá)式能接受的最長字符串的長度。

樣例輸入：
((xx|xxx)x|(x|xx))xx

樣例輸出：
6

---

解題思路

該問題是利用 深度優(yōu)先遍歷 的思想，具體實(shí)現(xiàn)見下面的參考代碼。

這里我們以樣例逐步說明算法原理，將參考代碼進(jìn)行簡單修改，可以幫助我們理解在哪一層搜索：

# 測試代碼
s = '((xx|xxx)x|(x|xx))xx'
i = 0
floor = 0
def dfs():global i, floorprint(f'此時(shí): i = {i}')floor += 1print(f'進(jìn)入一層，此時(shí)的層數(shù)為 {floor}')res = 0while i < len(s):# 遇到 '('，遞歸調(diào)用函數(shù)，對(duì)接下的 'x' 計(jì)數(shù)if s[i] == '(':i += 1res += dfs()i += 1print(f'此時(shí): i = {i}')# 遇到 ')'，返回計(jì)數(shù)結(jié)果elif s[i] == ')':floor -= 1print(f'退出一層，此時(shí)的層數(shù)為 {floor}')return res# 遇到 'x'，計(jì)數(shù)+1，索引后移elif s[i] == 'x':i += 1print(f'此時(shí): i = {i}')res += 1# 遇到 '|'，返回左右兩邊的較大值elif s[i] == '|':i += 1res = max(res, dfs())return resdfs()

輸出結(jié)果：

此時(shí): i = 0
進(jìn)入一層，此時(shí)的層數(shù)為 1
此時(shí): i = 1
進(jìn)入一層，此時(shí)的層數(shù)為 2
此時(shí): i = 2
進(jìn)入一層，此時(shí)的層數(shù)為 3
此時(shí): i = 3
此時(shí): i = 4
此時(shí): i = 5
進(jìn)入一層，此時(shí)的層數(shù)為 4
此時(shí): i = 6
此時(shí): i = 7
此時(shí): i = 8
退出一層，此時(shí)的層數(shù)為 3
退出一層，此時(shí)的層數(shù)為 2
此時(shí): i = 9
此時(shí): i = 10
此時(shí): i = 11
進(jìn)入一層，此時(shí)的層數(shù)為 3
此時(shí): i = 12
進(jìn)入一層，此時(shí)的層數(shù)為 4
此時(shí): i = 13
此時(shí): i = 14
進(jìn)入一層，此時(shí)的層數(shù)為 5
此時(shí): i = 15
此時(shí): i = 16
退出一層，此時(shí)的層數(shù)為 4
退出一層，此時(shí)的層數(shù)為 3
此時(shí): i = 17
退出一層，此時(shí)的層數(shù)為 2
退出一層，此時(shí)的層數(shù)為 1
此時(shí): i = 18
此時(shí): i = 19
此時(shí): i = 20

參考代碼

s = list(input().strip())
i = 0def dfs():global ires = 0while i < len(s):# 遇到 '('，遞歸調(diào)用函數(shù)，對(duì)接下的 'x' 計(jì)數(shù)if s[i] == '(':i += 1res += dfs()i += 1# 遇到 ')'，返回計(jì)數(shù)結(jié)果elif s[i] == ')':return res# 遇到 'x'，計(jì)數(shù)+1，索引后移elif s[i] == 'x':i += 1res += 1# 遇到 '|'，返回左右兩邊的較大值elif s[i] == '|':i += 1res = max(res, dfs())return resprint(dfs())

---