藍橋杯集錦05（python3）

試題 演算法提高 新建Microsoft Word檔案

問題描述
　　L正在出題，新建了一個word檔案，想不好取什么名字，身旁一人驚問：“你出的題目叫《新建Microsoft Word檔案》嗎？”，L大喜，一拍桌子，說：“好，就叫這個名字了，”
　　仔細觀察，當你新建一個word檔案時，會得到一個名為“新建 Microsoft Word 檔案.doc”的檔案，再新建一個，則名為“新建 Microsoft Word 檔案(2).doc”，再新建，便是“新建 Microsoft Word 檔案(3).doc”，不斷新建，編號不斷遞增，倘若你現在新建了三個檔案，然后洗掉了“新建 Microsoft Word 檔案(2).doc”，再新建就又會得到一個“新建 Microsoft Word 檔案(2).doc”，

嚴格說，Windows在每次新建檔案時，都會選取一個與已有檔案編號不重復的最小正整數作為新檔案的編號，

請編程模擬以上程序，支持以下兩種操作
　　New：新建一個word檔案，反饋新建的檔案的編號
　　Delete id：洗掉一個編號為id的word檔案，反饋洗掉是否成功
　　初始時一個檔案都沒有，“新建 Microsoft Word 檔案.doc”的編號算作1，
輸入格式
　　第一行一個正整數n表示操作次數，接下來n行，每行表示一個操作，若該行為”New”，則表示新建，為”Delete id”則表示要洗掉編號為id的檔案，其中id為一個正整數，操作按輸入順序依次進行，
輸出格式
　　對于輸入的每一行，輸出其反饋結果，對于新建操作，輸出新建的檔案的編號；對于洗掉操作，反饋洗掉是否成功：如果洗掉的檔案存在，則洗掉成功，輸出”Successful”，否則輸出”Failed”，
樣例輸入
12
New
New
New
Delete 2
New
Delete 4
Delete 3
Delete 1
New
New
New
Delete 4
樣例輸出
1
2
3
Successful
2
Failed
Successful
Successful
1
3
4
Successful

count = int(input())
lst = [False for i in range(count)]
for i in range(count):
    str1 = input()
    if str1 == 'New':
        for j in range(count):
            if lst[j] == False:
                lst[j] =True
                print(j+1)
                break
    elif str1[0:6] == 'Delete':
        for j in range(count):
            if int(str1[6::])-1 == j and lst[j] == False:
                print('Failed')
                break
            elif int(str1[6::])-1 == j and lst[j] == True:
                lst[j] = False
                print('Successful')
                break

試題 演算法訓練 二進制數數

問題描述
　　給定L,R，統計[L,R]區間內的所有數在二進制下包含的“1”的個數之和，
　　如5的二進制為101，包含2個“1”，
輸入格式
　　第一行包含2個數L,R
輸出格式
　　一個數S，表示[L,R]區間內的所有數在二進制下包含的“1”的個數之和，
樣例輸入
2 3
樣例輸出
3

left,right = map(int,input().split())
sum = 0
for i in range(left,right+1):
    str1 = bin(i)[2::]
    for j in str1:
        if j == '1':
            sum+=1
print(sum)

思路2：巧用.count()

left,right = map(int,input().split())
sum = 0
for i in range(left,right+1):
    str1 = bin(i)[2::]
    sum += str1.count('1')
print(sum)

節約不少時間

試題 演算法訓練 大小寫轉換

問題描述
　　撰寫一個程式，輸入一個字串（長度不超過20），然后把這個字串內的每一個字符進行大小寫變換，即將大寫字母變成小寫，小寫字母變成大寫，然后把這個新的字串輸出，
　　輸入格式：輸入一個字串，而且這個字串當中只包含英文字母，不包含其他型別的字符，也沒有空格，
　　輸出格式：輸出經過轉換后的字串，
輸入輸出樣例
樣例輸入
AeDb
樣例輸出
aEdB
思路1：

str1 = input()
new_str = []
for i in range(len(str1)):
    if ord('A')<=ord(str1[i])<=ord('Z'):
        new_str.append(chr(ord(str1[i]) + ord('a')-ord('A')))
    else:
        new_str.append( chr(ord(str1[i]) + ord('A')-ord('a')))

print(''.join(new_str))

改進：

str1 = input()
new_str = []
for s in str1:
    if 65<=ord(s)<=90:
        new_str.append(chr(ord(s) + 32))
    else:
        new_str.append( chr(ord(s) - 32))

print(''.join(new_str))

一行：

print(input().swapcase())

試題 演算法訓練 K好數

借鑒：https://blog.csdn.net/bianxia123456/article/details/104162203

問題描述
如果一個自然數N的K進制表示中任意的相鄰的兩位都不是相鄰的數字，那么我們就說這個數是K好數，求L位K進制數中K好數的數目，例如K = 4，L = 2的時候，所有K好數為11、13、20、22、30、31、33 共7個，由于這個數目很大，請你輸出它對1000000007取模后的值，

輸入格式
輸入包含兩個正整數，K和L，

輸出格式
輸出一個整數，表示答案對1000000007取模后的值，
樣例輸入
4 2
樣例輸出
7

思路：
剛開始看不懂題，其實是動態規劃問題；

k,l = map(int,input().split())
mod = 1000000007
count = 0
dp = [[0 for i in range(l+1)] for j in range(k)]
for w in range(k):
    dp[w][1] = 1
for y in range(2, l + 1):
    for x in range(k):
        for z in range(k):
            if z != x+1 and z != x-1:
                dp[x][y] = (dp[x][y]%mod + dp[z][y-1]%mod)%mod
for i in range(1,k):
    count = count%mod + dp[i][l]%mod
print(count % mod)

符合K好數條件的用紅色標出：

求4進制3位數的時候就會發現：

當百位是0的時候
得出：
dp[0][2] = dp[0][1] + dp[2][1] + dp[3][1] = 3
dp[2][2] = dp[0][1] + dp[2][1] = 2
dp[3][3] = dp[0][2] + dp[1][2] + dp[3][2] = 8
…
下面給出通式：dp[x][y] = dp[x][y] + dp[z][y-1]
其中0<=z<k