CSDN 编程竞赛·第八期总结
CSDN 编程竞赛·第八期总结
CSDN 编程竞赛·第八期为笔者参加的第三次 CSDN 编程竞赛，本来报名了第七期的，因为时间和二十大撞了，就错过了，第八期成绩似乎不错，排名第6（刚好没奖555，还挺想要签名书的），写博客一篇做总结。
11.02补充： 第3名被判定违规了，这下能有签名书了，好耶！
本次编程竞赛一共4题，笔者完美通过3题，现对比赛的4道题目进行总结。
1.代写匿名信
题目描述： 小Q想要匿名举报XX领导不务正业！ 小Q害怕别人认出他的字迹。 他选择从报纸上剪裁下来英文字母组成自己的举报信。 现在小Q找来了报纸，和自己的举报信的Txt， 你能帮他确定一下是否能够完成匿名信吗？
简单题，暴力过：
class Solution:
def __init__(self) -> None:
pass
def solution(self, words, msg):
result = None
words = set(list(words))
result = all([i in words for i in msg])
result = 'Yes' if result else 'No'
return result
if __name__ == "__main__":
words = input().strip()
msg = input().strip()
sol = Solution()
result = sol.solution(words, msg)
print(result)2.小艺改编字符串
题目描述： 已知字符串str. 添加至少多少字符可以使得str变成回文串。
一道动态规划题，
dp[i][j]代表字符串s第i+1到第j+1个字符形成的子串变为回文串所需要添加的最少字符数：
class Solution:
def __init__(self) -> None:
pass
def solution(self, s):
n = len(s)
dp = [[0 for i in range(n)] for j in range(n)]
for k in range(1, n):
for i in range(n-k):
j = i+k
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]
else:
dp[i][j] = min(dp[i+1][j], dp[i][j-1])+1
return dp[0][n-1]
if __name__ == "__main__":
s = input().strip()
sol = Solution()
result = sol.solution(s)
print(result)3.开学趣闻之美食诱惑
题目描述： 小艺酱又开学了，可是在上学的路上总会有各种意想不到的美食诱惑让小艺酱迟到。 假设小艺酱家到学校是一个n*n的矩 阵。 每个格子包含一个诱惑值p，诱惑着小艺，让她迟到。 小艺位于矩阵的左上角，学校在矩阵的右下角落。 小艺想知道 自己到达学校所要经历的最小诱惑值是？
纯纯的动态规划，
dp[i][j]代表走到[i][j]经历的最小诱惑值，比第2题简单：
class Solution:
def __init__(self) -> None:
pass
def solution(self, n, vector):
result = None
dp = [[0 for i in range(n)] for j in range(n)]
dp[0][0]=vector[0][0]
for i in range(1,n):
dp[0][i] = dp[0][i-1]+vector[0][i]
dp[i][0] = dp[i-1][0]+vector[i][0]
for i in range(1,n):
for j in range(1,n):
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + vector[i][j]
return dp[-1][-1]
if __name__ == "__main__":
n = int(input().strip())
vector = []
for i in range(n):
vector.append([int(item) for item in input().strip().split()])
sol = Solution()
result = sol.solution(n, vector)
print(result)4.争抢糖豆
题目描述： 抓糖豆，小Q与小K都喜欢吃糖豆。 但是糖豆分两种，超甜糖豆和普通糖豆。 现在有w个超甜糖豆和b个普通糖豆。 小Q和 小K开始吃糖豆，他们决定谁先吃到超甜糖豆谁就获胜。 小K每次吃的时候会捏碎一颗糖豆。 小Q先吃，小Q想知道自己获 胜的概率。 如果两个人都吃不到超甜糖豆小K获胜。
还是动态规划，比赛的时候有个情况写错了，
dp[i][j]代表有i个超甜糖豆和j个普通糖豆时小Q的胜率，状态转移方程如下：
class Solution:
def __init__(self) -> None:
pass
def solution(self, w, b):
dp = [[0]*(b+1) for i in range(w+1)]
for i in range(1,w+1):
dp[i][0] = 1
for i in range(b+1):
dp[0][b] = 0
for i in range(1,w+1):
for j in range(b+1):
dp[i][j] = i/(i+j)
if j >= 2:
dp[i][j] += j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2]
if j >= 3:
dp[i][j] += j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3]
return dp[w][b]
if __name__ == "__main__":
w, b = [int(item) for item in input().strip().split()]
sol = Solution()
result = sol.solution(w)
print(f'{result:.9f}')以上就是这次 CSDN 编程竞赛的全部内容了，如有错误，请读者指正。