CSDN竞赛第49期题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了CSDN竞赛第49期题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第49期比赛页面：第49期编程竞赛

一、

小海豚喜欢打游戏，现在它在操纵游戏人物小C逃脱废弃的隧道，逃生装置在小C的前方 X 米远的位置。但是游戏机只有两个按钮：前进和后退，按前进，小C会前进 m 米，按后退，小C会后退 n 米。小海豚必须设法把小C送到逃生装置上，方能逃离隧道，请你帮帮小海豚，告诉它至少要操作多少次，才能通关。

数据范围不大，直接暴力。

X, m, n = map(int, input().strip().split())
a = 0
while True:
    b = 0
    d = m * a
    while True:
        t = d - X - n * b
        if t > 0:
            b += 1
        else:
            break
    if t == 0: break
    a += 1
print(a + b)

二、输出给定字符串str中最长回文串的长度。

马拉车算法模板。

三、以字符串的形式给你一个长度为 M 的整数 N，请你计算出对这个数进行一次操作后模 9 的值为 1 的所有可能的不同操作方式。在一次操作中，我们可以选择 N 的一个数位 N[i]，并把它替换成另一个不同的 0 到 9 范围之内的数 B，两种操作方式不同当且仅当它们选择的 i 或 B 不同。

线性 DP 求解。定义 $(i\in [0, n], k \in [0, 9])$ 表示前缀中使得余数为 k 的操作方案数量。

四、小明电脑空间满了，决定清理一下磁盘空间。为了简化问题，小明列了他个人文件夹（/data）中所有末级文件路径和大小，挑选出总大小为m的删除方案。求所有删除方案中，删除操作次数最小是多少。一次删除操作：删除文件或者删除文件夹。如果删除文件夹，那么该文件夹包含的文件都将被删除。文件夹的大小：文件夹中所有末级文件大小之和。

典型的属性背包题目。

10. 有依赖的背包问题文章来源地址https://www.toymoban.com/news/detail-435046.html

到了这里，关于CSDN竞赛第49期题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！