CSDN 编程竞赛·第八期总结

CSDN 编程竞赛·第八期为笔者参加的第三次 CSDN 编程竞赛，本来报名了第七期的，因为时间和二十大撞了，就错过了，第八期成绩似乎不错，排名第6（刚好没奖555，还挺想要签名书的），写博客一篇做总结。

11.02补充：
第3名被判定违规了，这下能有签名书了，好耶！

本次编程竞赛一共4题，笔者完美通过3题，现对比赛的4道题目进行总结。

代写匿名信

题目描述：
小Q想要匿名举报XX领导不务正业！ 小Q害怕别人认出他的字迹。 他选择从报纸上剪裁下来英文字母组成自己的举报信。
现在小Q找来了报纸，和自己的举报信的Txt， 你能帮他确定一下是否能够完成匿名信吗？

简单题，暴力过：

class Solution:def __init__(self) -> None:passdef solution(self, words, msg):result = Nonewords = set(list(words))result = all([i in words for i in msg])result = 'Yes' if result else 'No'return resultif __name__ == "__main__":words = input().strip()msg = input().strip()sol = Solution()result = sol.solution(words, msg)print(result)

小艺改编字符串

题目描述：
已知字符串str. 添加至少多少字符可以使得str变成回文串。

一道动态规划题，dp[i][j]代表字符串s第i+1到第j+1个字符形成的子串变为回文串所需要添加的最少字符数：

class Solution:def __init__(self) -> None:passdef 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+kif 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])+1return dp[0][n-1]if __name__ == "__main__":s = input().strip()sol = Solution()result = sol.solution(s)print(result)

开学趣闻之美食诱惑

题目描述：
小艺酱又开学了，可是在上学的路上总会有各种意想不到的美食诱惑让小艺酱迟到。 假设小艺酱家到学校是一个n*n的矩
阵。 每个格子包含一个诱惑值p，诱惑着小艺，让她迟到。 小艺位于矩阵的左上角，学校在矩阵的右下角落。 小艺想知道
自己到达学校所要经历的最小诱惑值是？

纯纯的动态规划，dp[i][j]代表走到[i][j]经历的最小诱惑值，比第2题简单：

class Solution:def __init__(self) -> None:passdef solution(self, n, vector):result = Nonedp = [[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)

争抢糖豆

题目描述：
抓糖豆，小Q与小K都喜欢吃糖豆。 但是糖豆分两种，超甜糖豆和普通糖豆。 现在有w个超甜糖豆和b个普通糖豆。 小Q和
小K开始吃糖豆，他们决定谁先吃到超甜糖豆谁就获胜。 小K每次吃的时候会捏碎一颗糖豆。 小Q先吃，小Q想知道自己获
胜的概率。 如果两个人都吃不到超甜糖豆小K获胜。

还是动态规划，比赛的时候有个情况写错了，dp[i][j]代表有i个超甜糖豆和j个普通糖豆时小Q的胜率，状态转移方程如下：

$$d{p}_{i,j}=\frac{i}{i+j}+\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{i}{i+j-2}\times d{p}_{i-1,j-2}+\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{j-2}{i+j-2}\times d{p}_{i,j-3}$$

class Solution:def __init__(self) -> None:passdef solution(self, w, b):dp = [[0]*(b+1) for i in range(w+1)]for i in range(1,w+1):dp[i][0] = 1for i in range(b+1):dp[0][b] = 0for 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 编程竞赛的全部内容了，如有错误，请读者指正。