刷题记录（240619）
meituan0427
第一题
小美拿到了一个字符串，她准备把其中所有的"mei"子串替换为"tuan"子串，你能帮帮她吗？
输入描述
一个仅由小写字母组成的字符串。长度不超100000
输出描述
修改后的字符串。
示例
输入
meituan
输出
tuantuan
思路
直接模拟即可
s = input().replace("mei","tuan")
print(s)
第二题
小美拿到了一个字符矩阵，她定义一个矩形区域是“特殊的”，当且仅当这个矩形区域中没有两个相同的字符。 现在小美想知道，有多少个2行2列的矩阵区域是特殊的？
输入描述
第一行输入两个正整数n,m，代表矩阵的行数和列数。
接下来的n行，每行输入一个长度为m的、仅由小写字母组成的字符串，代表小美拿到的字符矩阵。
1<=n,m<=200
输出描述
一个整数，代表"特殊的"矩形区域的数量。
示例
输入
2 3
abb
aac
输出
0
思路
直接枚举即可，利用set的性质，如果len(set)==4，那么证明这个矩阵里面没有重复字符
代码
n,m = list(map(int,input().split()))
matrix = [list(input()) for _ in range(n)]
res = 0
for i in range(n-1):for j in range(m-1):s = set()for x in range(2):for y in range(2):s.add(matrix[i+x][j+y])if len(s) == 4:res += 1
print(res)
第三题
小美拿到了一个数组，她每次操作可以将两个相邻元素ai合并为一个元素，合并后的元素为原来两个元素之和。小美希望最终数组的最小值不小于k。她想知道有多少种不同的合并结果？
输入描述
第一行输入两个正整数n,k，代表数组大小和数组的最大值。
第二行输入个正整数ai，代表小美拿到的数组。
1<=n,k,ai<=200
输出描述
输出一个整数，代表小美可以得到多少种不同的结果。由于结果可能很大，输出对10^9+7取模的结果。
示例 1
输入
4 4
2 3 4 5
输出
4
说明
可能得到的数组有：[5,4,5]、[9,5]、[5,9]、[14]这四种。
思路
动态规划
对于每一个数字来说，如果当前和是小于k的，那么只能选择合并；否则的话，合并和不合并都可以。
f[i,j] 考虑i往后的数字，当前和是p，组成满足条件的方案数有多少。
推导如下：
if j>=k: f[i,j] += f[i+1,j+a[i]] + f[i+1,a[i]]
else: f[i,j] = f[i+1,j+a[i]]
代码
n,k = list(map(int,input().split()))
arr = list(map(int,input().split()))
MOD = 10**9+7
dp = [[-1]*(sum(arr)+1) for _ in range(n+1)]
def dfs(i,p):if i == n:return 1 if p >= k else 0if dp[i][p] != -1:return dp[i][p]cnt = 0if p >= k:cnt += dfs(i+1,arr[i]) + dfs(i+1,p+arr[i])else:cnt += dfs(i+1,p+arr[i])cnt %= MODdp[i][p] = cntreturn dp[i][p]print(dfs(0,0))