蓝桥杯集锦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