2021年第十二届蓝桥杯国赛/决赛，因为疫情原因没有像往年一样前往北京参赛，而是在自己学校的机房进行考试，形式上类似蓝桥杯省赛，但由于参加国赛的都是在省赛上获得省一的同学，所以人数相对较少，换到了一个较小的机房统一考试，而这间机房正好就在我实验室隔壁，早上不用站在考场外干等了。

这届蓝桥杯也是本人第一次参加编程竞赛，之前无任何经验，这段时间通过把蓝桥杯省赛、国赛作为一个阶段性目标，让自己的代码水平比平时划水时提高了不少，这里不敢说自己算法水平有多大的提高，因为蓝桥杯和一些专业的编程赛事相比，还是有一些差距的。

由于我写这篇博客的时候，网上还找不到Python组的真题，所以就从其他组别的真题中找相同的题目先作题解了。

签到题，但我不会，往年省赛是考过这样的单位转换题的，考试时想着 b 和 B 之间好像是差一个 8倍的关系，结果答了个 200 * 8 = 1600。

正确答案应该是 200 // 8 = 25.

本题也算签到题，我在考场上的想法就是直接对每个数分别判断： 1）是否为质数。 2）是否为纯质数。

判断是否为质数我觉得参加国赛的同学应该都能写对，但之后判断是否为纯质数就要注意不要漏数字了。

根据题意，一个数的某个数位上一旦出现质数，则该数就不是纯质数，那么数位上可能出现的质数应该是 0， 1， 4， 6， 8， 9，我自己在做的时候就漏掉了 0 。

代码如下：

其中判断质数的函数写法，我在之前写过的几篇省赛题解博客中有过详细介绍，感兴趣或者这里看不太明白的同学可以查看以前写的博客，主要思路围绕着“6的倍数”。

我们将关注点放在 6的倍数 上。任何一个数字对 6 取余，得到的余数都是在 0 ~ 5 之间，于是我们可以将任何一个数字表示为下列形式：

0）对6取余为0：6n 6的倍数，能被6整除，显然不是质数。

1）对6取余为1：6n + 1

2）对6取余为2：6n + 2 6n + 2 = 2 * (3n + 1)，能被2整除，显然不是质数

3）对6取余为3：6n + 3 6n + 3 = 3 * (2n + 1)，能被3整除，显然不是质数

4）对6取余为4：6n + 4 6n + 4 = 2 * (3n + 2)，能被2整除，显然不是质数

5）对6取余为5：6n + 5

由此可见，只要一个数字对6取余的结果不为 1 或者 5 ，那么可以确定它一定不是质数。由此我们可以“剪枝”掉大量无用的计算。

那么对于那些余数为 1 或 5的数呢？它们就一定是质数吗？ 答案是否定的，一个简单的反例是 24，24作为6的倍数，它的前后分别是 23 和 25，25作为余数为 1 的数字，却是质数，说明对于余数为 1 和 5 的数字，我们并不能确定它一定是质数，我们还需要对这些数单独进行判断。

代码中优化部分说的就是这部分，即对余数为 1 或 5 的数字单独判断是否为质数，那么我优化了什么呢？

正常判断一个数字是否为质数，我们需要从 2 开始遍历到该数的平方根，看是否能被整除，如果能被其中任意一个数除尽，则该数不是质数，若其中没有任意一个数能除尽，则该数为质数。

但仔细观察我们前面“剪枝”掉的数字，其中一部分是 2 * (3n + 1)，即所有能被 2 整除的数字，也就是全部的偶数，全部的偶数都被我们“剪枝”掉了；同时 3 * （2n + 1) 说明我们同时也“剪枝”掉了全部能被 3 整除的数字。综上所述，我们可以跳过 2、3、4，从5开始尝试，并且跳过那些偶数进行判断，在Python中可以设置遍历步长为2来跳过那些偶数。这就是优化部分的思路。

最后这部分优化的思路，是在另一位Python组国赛选手ZBR同学的帮助下得出的，ZBR同学数学方面的思维在编程上带来了巨大的优势。

正确答案是 1903 顺带一提，如果忘记了 0 ，那么错误答案应该是5599或者5601之类的。

本题我觉得也算签到题，至少因为我个人参加的是Python组，而Python处理日期有专门的datetime模块，非常的方便。

关键是要掌握两个点吧： 1）如何正确地遍历目标日期范围。 2）如何正确地判断一个日期是否为完全日期。

对于第一点，可以使用datetime模块中的datetime类和timedelta类完成。

对于第二点，可以解析出datetime类中的年月日信息进行求和处理。

说白了，本题只要你掌握了合适的API函数，基本就没啥坑点。

正确答案是977

本题作为填空题的压轴，有一定的难度。考场上我先是观察了这个计算权重的式子，看能不能观察出一些端倪，然后我观察到，如果左子树或者右子树的节点数为0，那么该权重计算式就可以简化成这样： 此时考场上的我喜出望外，对于这样两种情况，显然选择前面系数为2的第二种情况，即右子树节点为0，将全部节点集中在左子树，同时递归地进行相同的处理，这样就可以得到一棵这样的树： 对于这样一棵树，我们转化后的权重计算式可以通过函数递归的形式进行计算，也就是这样： 接着就是用代码来实现了：

结果一运行，发现栈溢出。没错，这就是Python不擅长递归的体现，Python递归的栈有限，一旦超出默认栈深度，就会抛出异常。

于是我在考场上是这样想的，我们递归个100次，然后把前100次递归的结果记录一下，接着跑 101次 - 200次递归，依次记录结果，直到 2021次都完成。虽然方法笨了点，但好歹不是无法解决的问题！

就在我兴高采烈地跑 f(100)的时候，却给出了这样的答案：

没错，这个数字好像有点大啊，而且这才递归了100次，我们要递归2021次才行啊。我本能地反应过来，哦，我应该是忘记设置mod，结果应该是要对mod取余的吧，结果一看题目，本题根本没有要求对某个数取余。

这个时候警觉的我意识到，答案应该不可能这么大，代码逻辑非常简单，不可能写错，所以问题出在我的思路上，也就是我把全部结点集中在左子树上这个想法很可能是错的！一切都要推翻重新思考！

之后思考了一段时候无果，我就先去做后面的题目了，等回过头来再看本题时，一个念头油然而生，今年这一套题做下来，怎么一道动态规划的题目都没有啊，没错，动态规划是蓝桥杯非常爱出的一种题型，考前本人花了大功夫准备动态规划的，可是大题里全连一道DP题都没有。这一点让我萌生了，是否可以试着用DP的思路来解本题呢？

首先DP的第一步，定义状态，dp[i] 表示节点数为 i 的树的最小权重。

第二步，设计状态转移方程。对于 dp[i]，树本身的根节点需要占用一个节点，因此剩余的 i - 1个节点要被左树和右树分配，左树分配 left 个节点，left 的取值范围是 0 ~ i - 1，那么右树可以被分配 right 个节点，right = i - 1 - left。 再结合题目给出的权重计算公式，那么得到状态转移方程为 第三步，设置DP数组的初值，显然根据题意有 dp[0] = 0,dp[1] = 1

代码如下：

答案是 2653631372 本题不保证答案的正确性，因为我也只是尝试着用DP去解题，无后效性和最优子结构之类的并没有通过证明去验证。

本题是编程题中的签到题。对于Python，有现成的API函数可以使用，upper()函数可以将字符串中所有小写字母转化成大写字母，我觉得参加Python组国赛的同学应该能会用这个函数吧

生性多疑的我，在考场上不断阅读本题题干，试图找出该题隐藏的坑点，可惜无果，我记得给出的数据范围，保证了输入字符串长度是在100以内的。

考虑输入字符串的长度是因为，有些题因为输入字符串过长，会采用换行输入的方式，而一旦换行，对于Python input()函数就不那么友好了，我们就需要提前获取目标字符串长度，然后不断重复接受直到长度符合要求为止。这一点是我在洛谷等OJ上做题经常遇到的情况，但是对于本题应该不会发生，因为数据范围非常小。

本题我自己写得实在不太好。直接上ZBR同学的代码，应该是可以AC本题拿满分的代码