咸阳市网站建设公司,塘沽网站制作,中山环保骏域网站建设专家,网站盈利的10种方式欢迎交流学习~~ 专栏#xff1a; 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列#xff1a; #x1f3c6; Python | 蓝桥杯进阶第一卷——字符串 #x1f50e; Python | 蓝桥杯进阶第二卷——递归#xff08;待续#xff09; #x1f49d; Python | 蓝桥杯进阶第三卷——动态… 欢迎交流学习~~ 专栏 蓝桥杯Python组刷题日寄 蓝桥杯进阶系列 Python | 蓝桥杯进阶第一卷——字符串 Python | 蓝桥杯进阶第二卷——递归待续 Python | 蓝桥杯进阶第三卷——动态规划待续 ✈️ Python | 蓝桥杯进阶第四卷——图论待续 Python | 蓝桥杯进阶第五卷——数论待续 Python | 蓝桥杯进阶第六卷——贪心待续 Python | 蓝桥杯进阶第七卷——搜索待续 Python | 蓝桥杯进阶第一卷——字符串 字符串的修改 ISBN码 完美的代价 字符串的展开 正则问题字符串的修改
时间限制 1s
内存限制 128MB
题目描述 设A和B是两个字符串。我们要用最少的字符操作次数将字符串A转换为字符串B。这里所说的字符操作共有三种
删除一个字符插入一个字符将一个字符改为另一个字符。
对任给的两个字符串 A 和 B计算出将字符串 A 变换为字符串 B 所用的最少字符操作次数。
输入描述 第一行为字符串 A第二行为字符串 B字符串 A 和 B 的长度均小于 200。
输出描述 只有一个正整数为最少字符操作次数。
样例输入
sfdxbqw
gfdgw样例输出 4 解题思路 本题思路如下
求解两字符串的最长公共子序列得到其长度 L计算最少字符操作次数
本题思路的核心在于 求解两个字符串的最长公共子序列。 可以选择用循环暴力求解但是时间复杂度过高容易超时。因此我们这里可以选用时间复杂度更低的动态规划方法
dp[i][j] 表示 a[:i-1] 和 b[:j-1] 的最长公共子序列的长度 i0, j0对应 dp 数组的大小为 dp[l11][l21]l1 和 l2 为两个字符串的长度i0 或 j0 表示空字符串此时公共子序列长度都为 0因此我们将 dp 数组都初始化为 0状态转移具体见代码。
而对于计算最终结果其计算方式为max(l1, l2) - L。 因为如果想将较长的字符串变为较短的字符串除了最长公共子序列其余字符都需要变化。 参考代码
a input()
b input()
l1 len(a)
l2 len(b)
# dp数组,
# dp[i][j]表示a[:i-1]和b[:j-1]中最长公共子序列的长度(i0, j0)
# i0 和 j0 表示空字符串初始化dp数组为全0
dp [[0 for j in range(l2 1)] for i in range(l1 1)]
for i in range(1, l11):for j in range(1, l21):if a[i-1] b[j-1]:# a的第i-1个字符和b的第j-1个字符相同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码
题目 时间限制 1s
内存限制 128MB
题目描述 每一本正式出版的图书都有一个ISBN号码与之对应ISBN码包括 9 位数字、1 位识别码和 3 位分隔符其规定格式如 x-xxx-xxxxx-x其中符号 - 就是分隔符键盘上的减号最后一位是识别码例如 0-670-82162-4 就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言例如 0 代表英语第一个分隔符 - 之后的三位数字代表出版社例如 670 代表维京出版社第二个分隔符后的五位数字代表该书在该出版社的编号最后一位为识别码。
识别码的计算方法如下
首位数字乘以 1 加上次位数字乘以 2……以此类推用所得的结果 mod 11所得的余数即为识别码如果余数为 10则识别码为大写字母 X。例如ISBN号码 0-670-82162-4 中的识别码 4 是这样得到的对 067082162 这 9 个数字从左至右分别乘以12...,9 ,再求和即 0×16×2……2×9158然后取158 mod 11的结果 4 作为识别码。
你的任务是编写程序判断输入的ISBN号码中识别码是否正确如果正确则仅输出 Right如果错误则输出你认为是正确的ISBN号码。
输入描述 输入只有一行是一个字符序列表示一本书的ISBN号码保证输入符合ISBN号码的格式要求。
输出描述 输出共一行假如输入的ISBN号码的识别码正确那么输出 Right 否则按照规定的格式输出正确的ISBN号码包括分隔符 -。
样例输入
0-670-82162-4
0-670-82162-0样例输出
Right
0-670-82162-4解题思路 本题思路比较简单注意细节的处理
字符串以 - 分割当计算出的识别码为 10 时将其转换为 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 Xif id s[-1]:print(Right)else:print(raw[:-1] id)except:break完美的代价
时间限制 1s
内存限制 128MB
题目描述 回文串是一种特殊的字符串它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串它不一定是回文的请你计算最少的交换次数使得该串变成一个完美的回文串。 交换的定义是交换两个相邻的字符 例如对于 mamad 第一次交换 ad : mamda 第二次交换 md : madma 第三次交换 ma : madam (回文完美)
输入描述 第一行是一个整数 N表示接下来的字符串的长度(N 8000) 第二行是一个字符串长度为 N只包含小写字母
输出描述 如果可能输出最少的交换次数。 否则输出 Impossible
样例输入
5
mamad样例输出 3 解题思路 本题利用双指针其中头指针 head 从前向后遍历尾指针 tail 从后向前遍历。
退出循环的条件
字符串长度为偶数但是有频数为奇数的字母字符串长度为奇数但是有多于 1 个的频数为奇数的字母
具体思路见参考代码。 参考代码
n int(input())
s list(input())
count 0 # 记录交换次数
flag 0 # 标记是否有字母频数为奇数
res True # 标记是否为Impossible(是Impossible置为False)# 双指针
L n - 1 # 头指针搜索范围到倒数第2个
for head in range(L):# 对于每一个s[head]用尾指针去搜索是否有相同的字母s[tail]for tail in range(L, head - 1, -1):# 指针tail搜索完毕没有发现s[head] s[tail]# 说明该字母频数为奇数 1且该字母在回文序列中一定在中间if head tail:# 如果字符串长度为偶数# 字符串长度为奇数但是已经有 flag 1if n%2 0 or flag 1:res Falsebreakflag 1# (n//2 - head) 为将该字母移动到中间位置的交换次数count n//2 - head# 发现了 s[head] s[tail]elif s[head] s[tail]:# 交换位置for i in range(tail, L):s[i], s[i1] s[i1], s[i]count 1L - 1break# 如果是impossible退出外层循环if res False:breakif res False:print(Impossible)
else:print(count)字符串的展开
时间限制 1s
内存限制 128MB
题目描述 在初赛普及组的“阅读程序写结果”的问题中我们曾给出一个字符串展开的例子如果在输入的字符串中含有类似于 d-h 或者 4-8 的字串我们就把它当作一种简写输出时用连续递增的字母获数字串替代其中的减号即将上面两个子串分别输出为 defgh 和 45678。在本题中我们通过增加一些参数的设置使字符串的展开更为灵活。具体约定如下
遇到下面的情况需要做字符串的展开在输入的字符串中出现了减号 -减号两侧同为小写字母或同为数字且按照ASCII码的顺序减号右边的字符严格大于左边的字符。参数p1展开方式。p11 时对于字母子串填充小写字母p12 时对于字母子串填充大写字母。这两种情况下数字子串的填充方式相同。p13 时不论是字母子串还是数字字串都用与要填充的字母个数相同的星号 * 来填充。参数p2填充字符的重复个数。p2k表示同一个字符要连续填充 k 个。例如当 p23 时子串d-h 应扩展为 deeefffgggh。减号两边的字符不变。参数p3是否改为逆序p31 表示维持原来顺序p32 表示采用逆序输出注意这时候仍然不包括减号两端的字符。例如当p11、p22、p32时子串 d-h 应扩展为 dggffeeh。如果减号右边的字符恰好是左边字符的后继只删除中间的减号例如d-e 应输出为 de3-4 应输出为 34。如果减号右边的字符按照 ASCII码的顺序小于或等于左边字符输出时要保留中间的减号例如d-d 应输出为 d-d3-1 应输出为 3-1。
输入描述 输入包括两行 第 1 行为用空格隔开的 3 个正整数一次表示参数 p1p2p3。 第 2 行为一行字符串仅由数字、小写字母和减号 - 组成。行首和行末均无空格。
数据规模和约定 100%的数据满足1p131p281p32。字符串长度不超过 100
输出描述 输出只有一行为展开后的字符串.
样例输入
1 2 1
abcs-w1234-9s-4zz样例输出 abcsttuuvvw1234556677889s-4zz 解题思路
符号 - 只会在 s[1:len(s)-1] 之间s 为输入字符串因此要在这个范围内遍历找到符号 - 并将其展开满足展开的条件即要判断左右两边的字符的ASCII码关系之后根据 p3-p1-p2 的判断顺序对展开字符进行修改。
具体见代码。 参考代码
p1, p2, p3 map(int, input().split())
s input()
res s[0]
# - 只会在s[1:len(s)-1]中间因此s的首尾不需要变化
for i in range(1, len(s)-1):left, mid, right s[i-1], s[i], s[i1]# 遇到 - 并且左右字符满足如下条件# 条件1leftright# 条件2(left0 and right9) or (lefta and rightz) 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()转为字符tmp chr(j)if p1 2:# 变为大写tmp tmp.upper()elif p1 3:# 变为 *tmp *## p2# 重复 p2 次res tmp * p2else:res mid# 尾巴
res s[-1]
print(res)正则问题
时间限制 1s
内存限制 128MB
题目描述 考虑一种简单的正则表达式 只由 x ( ) | 组成的正则表达式。 小明想求出这个正则表达式能接受的最长字符串的长度。
例如((xx|xxx)x|(x|xx))xx 能接受的最长字符串是 xxxxxx长度是 6。
输入描述 一个由 x()| 组成的正则表达式。输入长度不超过 100保证合法。
输出描述 这个正则表达式能接受的最长字符串的长度。
样例输入 ((xx|xxx)x|(x|xx))xx
样例输出 6 解题思路 该问题是利用 深度优先遍历 的思想具体实现见下面的参考代码。
这里我们以样例逐步说明算法原理将参考代码进行简单修改可以帮助我们理解在哪一层搜索
# 测试代码
s ((xx|xxx)x|(x|xx))xx
i 0
floor 0
def dfs():global i, floorprint(f此时: i {i})floor 1print(f进入一层此时的层数为 {floor})res 0while i len(s):# 遇到 (递归调用函数对接下的 x 计数if s[i] (:i 1res dfs()i 1print(f此时: i {i})# 遇到 )返回计数结果elif s[i] ):floor - 1print(f退出一层此时的层数为 {floor})return res# 遇到 x计数1索引后移elif s[i] x:i 1print(f此时: i {i})res 1# 遇到 |返回左右两边的较大值elif s[i] |:i 1res max(res, dfs())return resdfs()输出结果
此时: i 0
进入一层此时的层数为 1
此时: i 1
进入一层此时的层数为 2
此时: i 2
进入一层此时的层数为 3
此时: i 3
此时: i 4
此时: i 5
进入一层此时的层数为 4
此时: i 6
此时: i 7
此时: i 8
退出一层此时的层数为 3
退出一层此时的层数为 2
此时: i 9
此时: i 10
此时: i 11
进入一层此时的层数为 3
此时: i 12
进入一层此时的层数为 4
此时: i 13
此时: i 14
进入一层此时的层数为 5
此时: i 15
此时: i 16
退出一层此时的层数为 4
退出一层此时的层数为 3
此时: i 17
退出一层此时的层数为 2
退出一层此时的层数为 1
此时: i 18
此时: i 19
此时: i 20参考代码
s list(input().strip())
i 0def dfs():global ires 0while i len(s):# 遇到 (递归调用函数对接下的 x 计数if s[i] (:i 1res dfs()i 1# 遇到 )返回计数结果elif s[i] ):return res# 遇到 x计数1索引后移elif s[i] x:i 1res 1# 遇到 |返回左右两边的较大值elif s[i] |:i 1res max(res, dfs())return resprint(dfs())
