第十四届蓝桥杯 Python B组 题目简析 - 知乎

　　没有在这篇里的题目就是我没有做/来不及时间做的题。

　　请求出在 12345678 至 98765432 中，有多少个数中完全不包含 2023 。

　　完全不包含 2023 是指无论将这个数的哪些数位移除都不能得到 2023 。

　　例如 20322175，33220022 都完全不包含 2023，而 20230415，20193213 则

　　含有 2023 (后者取第 1, 2, 6, 8 个数位) 。

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

　　个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

　　用字符串的find方法。可以指定搜索的范围，那么搜完第一个，我们将范围缩小来继续搜。

　　只要有一个找不到就返回False。

　　小蓝手中有 2023 种不同面值的硬币，这些硬币全部是新版硬币，其中第

　　i(1 ≤ i ≤ 2023) 种硬币的面值为 i ，数量也为 i 个。硬币兑换机可以进行硬币兑

　　换，兑换规则为：交给硬币兑换机两个新版硬币 coin1 和 coin2 ，硬币兑换机会

　　兑换成一个面值为 coin1 + coin2 的旧版硬币。

　　小蓝可以用自己已有的硬币进行任意次数兑换，假设最终小蓝手中有 K 种

　　不同面值的硬币（只看面值，不看新旧）并且第 i(1 ≤ i ≤ K) 种硬币的个数为

　　sumi。小蓝想要使得 max{sum1, sum2, · · · , sumK} 的值达到最大，请你帮他计算

　　这个值最大是多少。

　　注意硬币兑换机只接受新版硬币进行兑换，并且兑换出的硬币全部是旧版

　　硬币。

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

　　个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

　　（不一定对，只是我的做法）

　　要求最后某一种的硬币数量最多。范围为1~2023。你如果加的和超过了2023这个阈值，那么在总数上，实际上是减少了的（2->1）。那么单在范围内考虑的话，不妨考虑最大的数，2023=1+2022，只能加1次2023；2023=2+2021，能加2次2023。...2023=1011+1012，能加1011次2023。

　　那么2023此时的次数就是1+2+3+...+1011+2023，用编程求解即可

　　时间限制: 10.0s

　　内存限制: 512.0MB

　　本题总分：10 分

　　给定一个仅含小写字母的字符串 s ，假设 s 的一个子序列 t 的第 i 个字符

　　对应了原字符串中的第 pi 个字符。我们定义 s 的一个松散子序列为：对于 i > 1

　　总是有 pi − pi−1 ≥ 2 。设一个子序列的价值为其包含的每个字符的价值之和 (

　　a ∼ z 分别为 1 ∼ 26 ) 。

　　求 s 的松散子序列中的最大价值。

　　输入一行包含一个字符串 s 。

　　输出一行包含一个整数表示答案。

　　azaazaz

　　78

　　题目说的很绕，但其实就是dp问题。

　　用闫式dp分析法。

　　状态表示：f[i][0]，不选字符串s的第i个字符时的价值；f[i][1]，选字符串s的第i个字符时的价值。

　　属性：max，因为要求价值最大

　　状态计算：因为有pi-pi-1>=2的限制，所以f[i][1]=max(f[i-2][1], f[i-2][0])，只能从隔了1个的开始选。

　　f[i][0]=max(f[i-1][1], f[i-1][0])，因为第i个字符没有选，那么我们就用前一个来更新。

　　代码如下

　　时间限制: 10.0s

　　内存限制: 512.0MB

　　本题总分：15 分

　　小蓝有一个保险箱，保险箱上共有 n 位数字。

　　小蓝可以任意调整保险箱上的每个数字，每一次操作可以将其中一位增加

　　1 或减少 1 。

　　当某位原本为 9 或 0 时可能会向前（左边）进位/退位，当最高位（左边第

　　一位）上的数字变化时向前的进位或退位忽略。

　　例如：

　　00000 的第 5 位减 1 变为 99999 ；

　　99999 的第 5 位减 1 变为 99998 ；

　　00000 的第 4 位减 1 变为 99990 ；

　　97993 的第 4 位加 1 变为 98003 ；

　　99909 的第 3 位加 1 变为 00009 。

　　保险箱上一开始有一个数字 x，小蓝希望把它变成 y，这样才能打开它，问

　　小蓝最少需要操作的次数。

　　输入的第一行包含一个整数 n 。

　　第二行包含一个 n 位整数 x 。

　　第三行包含一个 n 位整数 y 。

　　输出一行包含一个整数表示答案。

　　5

　　12349

　　54321

　　11

　　求最少操作次数，用bfs。（刚开始用了dfs来做，浪费了些时间）

　　这个问题主要是要注意加减时的进位、借位。这里编写了op_minus，op_plus两个函数来进行处理。

　　然后因为加减时的进位借位都是右数（低位）向左数（高位）进位/借位，也就意味着会影响到下一位，所以我们需要先把低位先处理成目标字符，把它固定住。

　　然后bfs队列中的元素是源字符串src_old，目标字符串dst_old，当前操作次数cnt，当前要操作的位数idx。

　　然后只要发现源字符串和目标字符串相等了，就break掉循环。此时队内都是源字符串和目标字符串相等的元素，只有操作次数不相等，因此遍历一遍，取最小操作次数即可。

　　时间限制: 10.0s

　　内存限制: 512.0MB

　　本题总分：15 分

　　给定一棵树，树根为 1，每个点的点权为 Vi 。

　　你需要找出若干个点 Pi，使得：

　　1. 每两个点 Px Py 互不相邻；

　　2. 每两个点 Px Py 与树根的距离互不相同；

　　3. 找出的点的点权之和尽可能大。

　　请输出找到的这些点的点权和的最大值。

　　输入的第一行包含一个整数 n 。

　　第二行包含 n − 1 个整数 Fi ，相邻整数之间使用一个空格分隔，分别表示

　　第 2 至 n 个结点的父结点编号。

　　第三行包含 n 个整数 Vi，相邻整数之间使用一个空格分隔，分别表示每个

　　结点的点权。

　　输出一行包含一个整数表示答案。

　　5

　　1 2 3 2

　　2 1 9 3 5

　　11

　　这道题是树形dp。前天才在acwing上做了这道板子题《没有上司的舞会》。不过dfs函数内部顺序写错了，所以这道题寄掉了，很可惜。