【第十六届蓝桥杯省赛】比赛心得与经验分享（PythonA 组）-海口c网

文章目录

一、我的成绩
二、我的备赛经历
三、如何备赛（个人观点）
- 1. 基础语法
- 2. 数据结构
- 3. 算法
- 4. 数学
四、做题技巧与注意事项
五、我的题解
- 试题A 偏蓝 🏆100%
- 试题B IPV6 🏆0%
- 试题C 2025图形 🏆100%
- 试题D 最大数字 🏆100%
- 试题E 倒水 🏆10%
- 试题F 拼好数 🏆40%
- 试题 G 登山 🏆15%
- 试题H 原料采购 🏆20%
五、结语

一、我的成绩

这是我第一次参加蓝桥杯，很高兴的是最后的成绩是省一等奖。在这里我想把我的经验分享给要参加蓝桥杯的其他同学们，也算是对我这段时间学习的一个总结。

（acmer 可以划走了，报名就送国一）

请添加图片描述

二、我的备赛经历

如果你还在因为实力不足而纠结到底报不报蓝桥杯的话，我的答案是：报就完事儿了。

我是一个大一的小菜鸡，进入大学之前没接触过编程，大一上学期也只学了一下 C 语言。当时听说有蓝桥杯比赛，想着大学里面至少也得拿个什么比赛的奖吧，就报名了。当时听学长说 Python 组比较好拿奖，因此就报名了 Python 组。

到了25年放寒假的时候，我在年前（大概 1 月中下旬左右）花了 5 天时间把 Python 的语法全部过了一遍，年后（2月份）开始学习基础的数据结构（顺序表、链表、栈、队列、二叉树等）。然后开始在力扣上刷算法题，不刷不知道，一刷吓一跳，最简单的基础题我甚至可以做到毫无思路，当评论区的大佬都在嘲讽“这也能算一个题”的时候，我正坐在电脑前苦思冥想。每天刷题的心路历程就是“刷题——>不会——>看题解——>if 看得懂：感叹大佬nb，else：崩溃——>下一道题”。当时挫败感非常强，不过我也只能每天不断练习和积累。

我刷 Python 题最大的感受就是：Python 库函数简直太多了…几乎我每刷一道题看题解的时候都能看到一个新的函数，比如 enumerate、reduce、map 等等。于是我专门建立了一个新的 markdown 文本写我的刷题笔记，不断积累。

到了 3 月份我开始系统地学习算法，从最简单的双指针、前缀和到 dfs、bfs 再到稍微复杂一点的动态规划、贪心等等。起初我还边学边写博客，后来发现这样好像时间不太够了，毕竟 4 月份就要比赛了（哀），所以我在后面的学习中主要以刷题为主。通过我逐步学习算法，我也能感受到自己的进步。从做开始力扣上简单题无从下手——>简单题也不过如此——>中等题我跟你拼了——>中等题你难不倒我——>困难题初探——>在别人的思路带领下完成困难题——>自己独立完成困难题。当你真正自己独立完成一道高难度的题的时候那种成就感与喜悦是任何东西都无法比拟的。我还记得我有一次花了一个半小时自己独立写出来了一道某年国赛真题，好像叫路径之谜。谁懂通过100% 弹出来那一刻的救赎感！

从备考到 4 月份比赛为止，我一共在力扣上刷了 200+ 道题，也在蓝桥杯官网上练了不少真题。其实我在刷真题之前已经学习了不少算法，也在力扣上刷了不少算法题，但是我做往年的题目的时候发现我还是不会做 (?)，这就很尴尬了。一部分原因我总结的是力扣的题题干都非常简洁直白，基本上思考一下就知道它考的是什么算法，但是像洛谷、蓝桥杯这样的题都是有一个特殊的情景，你需要透过现象看本质去挖掘出它到底要考什么，这一点是很重要的我觉得。再其次就是做不出来也完全没关系，不会的题思考了一定的时间之后就去看题解，把大佬们的经验技巧积累下来。做题都是一个不断历练的过程，欲问青云路，先叩荆棘门。并且蓝桥杯是一个很好拿奖的比赛，基本上只要你有十来分就有奖。

之后到了 4 月份就比赛了，我是线上参赛，要求双机位监考，只能使用指定的 IDE 编写代码（Python 是 IDLE，C++ 是 dev），草稿纸也是自己准备。从上午 9:00 比赛开始到下午的 13:00 一共 4 个小时。所以尽量前一天就把官方要求的配置都配好了然后第二天起床就开干。

考试之后大约两周多一点出的成绩。

三、如何备赛（个人观点）

1. 基础语法

首先我觉得无论是什么语言，都应该先把最基础的语法学好，毕竟有了语法基础才能更好地去写代码。这里我觉得我没有做的很好，因为我过 Python 基础语法过的比较快，学的不够扎实，导致我在开始做算法题的时候有一部分时间都在查语法…

2. 数据结构

其次是数据结构，都说 程序 = 数据结构 + 算法，数据结构是一个容器，我们想要解决一个问题通常要选择恰当的容器再选择一个合适的算法去解决。所以数据结构是必不可少的。下面我列举了一个我认为比较重要的数据结构。（这里只是我在做题的时候总结出来的可能用的比较多的，不一定准确）

T0 级别：

栈、队列、字符串、堆 (优先队列)、哈希表、并查集

T1 级别：

单调栈、单调队列、树、图、线段树

3. 算法

算法是解决一道题的核心，通过我刷题的经验以及看了其他大佬的总结然后我梳理了以下比较重要的算法。（如有任何遗漏或不妥，还请大佬指出）

T0 级别（基础）：

暴力，暴力，还是暴力！：其实严格来说它不是一个算法，但是蓝桥杯经常被调侃说是暴力杯就是因为它有很多题目都是可以通过暴力求解的方式来 AC 的。只要你会写循环，你就能拿奖！
模拟：这个本质上是在锻炼你的代码能力，就是题目要求你干啥你就干啥，并且这个算法也不需要系统地去学习，掌握语法和基本的数据结构之后就可以去刷，我建议这个可以多刷。
双指针、滑动窗口、前缀和、差分、位运算、二分、递归、分治。
DFS：基础的 DFS 需要掌握二叉树的前、中、后序遍历方式。
BFS：基础的 BFS 需要掌握二叉树的层序遍历。

T0 级别（进阶）：

（下面给出的经典习题没有特别说明均来自力扣）

动态规划：好像往年蓝桥杯被说是 dp 杯来着，dp 就是动态规划，也是蓝桥杯很喜欢的一个算法。我个人觉得学动态规划不要从背包问题开始学，这样容易崩溃。可以从简单的线性dp开始学起，这个比背包问题简单多了，只要你认真去学一定能学好。之后就是子数组、子序列、回文串、两个数组dp之类相关的问题。把动态规划基本了解了之后再去学背包问题就会轻松很多。背包问题优先学习 01背包和完全背包，然后是二维费用的背包。

经典习题：

简单一维dp：斐波那契数、爬楼梯…
简单二维dp：不同路径、不同路径Ⅱ、最小路径和…
子序列问题：最长递增子序列…
回文串问题：最长回文串、回文串分割…
两个数组dp：最长公共子序列…
01 背包、完全背包（这俩在牛客上有模板题）

回溯与剪枝（DFS）：我个人觉得这是我学起来比较抽象的算法，因为回溯是靠递归实现的，而递归本身就比较难理解，我最大的感受就是：不要总是去关心递归里面到底怎么深入的，要不然会把你绕晕。把递归想象成一个黑盒，你把任务交给这个黑盒，相信这个黑盒一定能完成任务的。

经典习题：全排列、八皇后、解数独…

BFS：稍微进阶一点的 BFS 包括边权为 1 的最短路问题、Floodfill 问题、多源 BFS 和拓扑排序。

**经典习题：**01矩阵、岛屿数量、课程表…

贪心：我个人感觉贪心是一个神奇的算法，有些贪心题你根据常识就能轻松想得到，有些贪心题就算你刷了 100 到贪心题你还是可能毫无思路。这个算法我觉得吧，还是多积累，积累贪心策略。

经典习题：最大数、最长递增子序列（贪心 + 二分）、优势洗牌（田忌赛马）、合并区间（区间问题）…

T1 级别：

图论：Dijkstra、Floyed、Kruskal、Prim、SPFA、最小生成树…
动态规划：学有余力可以再去学多重背包、混合背包等等。再然后有时间可以去学学区间dp，树形dp、状压dp…
排序：并不是说排序没那么重要，只是我觉得就参加比赛来说，能用库中的排序就足够了，不需要我们手写。但是从长远的角度来看，排序算法本身非常重要，需要掌握基本的 7 大排序。

T2 级别：

字符串相关算法：kmp、马拉车、字符串hash、字典树…
高精度
…

4. 数学

感觉蓝桥杯前几道题就很喜欢考数学和思维相关的东西。

T0 级别：

唯一分解定理、素数筛、快速幂、gcd、lcm、组合数学…

T1 级别：

裴蜀定理、欧拉函数、费马小定理、逆元、扩展欧几里得算法、中国剩余定理、扩展中国剩余定理、欧拉定理、扩展欧拉定理、高斯消元、矩阵快速幂…

别看上面这么多，其实它们很多都是互相关联的，比如费马小定理可以用于求解逆元，扩展欧几里得算法涉及到裴蜀定理和逆元，中国剩余定理又涉及到扩展欧几里得算法…

T2 级别：

计算几何、博弈…

四、做题技巧与注意事项

其实是~~骗分技巧~~

不要老想着一定要用某某算法去解题，用暴力不是什么可耻的事情，大胆去写循环就完事儿了，蓝桥杯是按通过的测试样例数量来给分的，只要你有样例过了，就有分。
遇到不会做的题没关系，如果这道题明确说明了无解的情况要输出 -1 的话，那么你可以直接打印一个-1（print(-1)），这样能骗不少分。
如果没有说要输出 -1，你可以打印一个随机值。比如 Python 的话就 import random 然后调用对应的函数打印一个随机值。你别看这样希望很渺茫，这个命中的概率真不小（我也不知道原理是什么）。
一些找规律的题不妨通过打表的方式来摸索答案。就是说把一定范围内的答案枚举出来，然后肉眼观察有什么规律。
正式比赛填空题直接交数字，不要 print 不要 printf 不要 cout。但是 OJ 上做题的时候要用输出语句。
C/C++ 组的同学记得在 main 函数中加上 return 0，我在有些评论区经常看到有些人忘记加了然后痛苦哀嚎。
（如果还有其他的还请大佬们补充）

五、我的题解

试题A 偏蓝 🏆100%

在这里插入图片描述

思路：枚举

这个题比较简单，就是通过循环把所有情况全部枚举出来然后用一个变量记录结果即可。

ans = 0
for k in range(1, 256):for i in range(0, k):for j in range(0, k):ans += 1
print(ans)

最终答案是 5559680，在正式比赛的时候只交这个数字即可。

试题B IPV6 🏆0%

在这里插入图片描述

恕我直言，我都没怎么读懂题意，当时做这道题的时候想了 5 分钟完全没思路就直接跳过了，到最后也没做出来，还好是个填空题。但好像可以用 dp (?)

试题C 2025图形 🏆100%

在这里插入图片描述

思路：

这道题也简单，由于数据范围比较小我就直接先打印了一串 2025 然后每行截取一段即可。

st = '2025' * 100  # 其实这里都用不着 100 个 2025, 最少是 50 个
h, w = map(int, input().split())
for i in range(h):print(st[i:i + w])

试题D 最大数字 🏆100%

在这里插入图片描述

思路：贪心 + 排序

题目意思就是把 1~n 之间的数转换成二进制然后拼接起来组成一个最大的二进制数然后返回它的十进制。比如 3，那么 1~3 这些数转换成二进制就是 1、10、11，把他们拼接在一起组成的最大二进制数就是 11110，对应十进制就是 30。

这个题和力扣上的 “最大数” 的思路几乎一样，由于这个题我记忆犹新，所以在做题的之后马上就反应出来了hhh，所以我说贪心要不断积累贪心策略。首先把 1~n 之间的所有数转换成 2 进制之后，然后开始贪心。这里的贪心策略就是如果 ab (b 拼接在 a 后面) 组成的数字比 ba (a 拼接在 b 后面) 组成的数字大的话，那么最终的二进制数中 a 一定要放在 b 的前面。比如说 100 和 11，11100 明显比 10011 大，所以在最终我们组成的最大二进制数中 11 就要排在 100 的前面。

这里就产生了一种新的排序规则，我们平时排序比如说升序，就是小的放前面大的放后面，现在就需要根据我们上面这样的新的规则进行排序。如何依照这样的规则进行排序就可以用到 cmp_to_key，你需要自己实现这个规则然后传给这个函数他就会根据你的规则进行排序。

import sys 
import functools
sys.set_int_max_str_digits(0) # 由于组成的数字很大，所以把int设置为无上限n = int(input())
a = [bin(x) for x in range(1, n + 1)]  # 把 1~n 所有数字转化成 2 进制然后存储在列表中
def cmp(a, b):  # 重写排序规则return -1 if a + b > b + a else 1  # 这里的规则就是我上面所说的
a = [x[2:] for x in a]  # 把二进制数前面两位无关的符号去掉，只保留数字
a.sort(key = functools.cmp_to_key(cmp))  # 排序
print(int(''.join(a), 2))

试题E 倒水 🏆10%

在这里插入图片描述

唉，做题做的太少了，都没想到二分，当时还在思考这到底要考啥，暴力也没暴出个名堂。罢了，打印个随机值溜了。

import random
n, k = map(int, input().split())
water = list(map(int, input().split()))
t = sum(water) // nprint(random.randint(1, t))

这样在洛谷的 10 个测试用例中还对了一个，不知道蓝桥杯那边的测试用例怎么样。

试题F 拼好数 🏆40%

在这里插入图片描述

~~疑似出题人吃完拼好饭吃多了出的题~~。这题还是做了挺久的，我当时个人的想法是贪心，先把每个数中 6 的次数统计出来放到列表中并排升序，然后如果 6 的出现次数大于等于 6 就单独成一组，统计一个次数。接着如果能两个一组就两个一组，不能再三个一组。赛后重新看到数据范围——原来是枚举…

在洛谷上测评只拿了 40% 的分。

n = int(input())
arr = input().split()
target = [x.count('6') for x in arr]
ret = 0
target.sort()
left_1, left_2, right = 0, 1, n - 1
while right >= 0 and target[right] >= 6:right -= 1ret += 1
while left_2 < right:if target[left_1] + target[right] >= 6:ret += 1left_1 += 1left_2 += 1right -= 1elif target[left_1] + target[left_2] + target[right] >= 6:ret += 1left_1 += 2left_2 += 2right -= 1else:left_1 += 1left_2 += 1
if left_1 < right:if target[left_1] + target[right] >= 6:ret += 1
print(ret)

枚举的思路如下：

对于 6：单独一组

对于 5：可以匹配 1， 2， 3， 4， 5

对于 4：可以匹配（1， 1）， 2， 3， 4， 5

对于 3：可以匹配（2， 1），3

对于 2：可以匹配（2， 2）

最后再加上（3， 2， 2）

优先级从上到下从左往右依次递减。

试题 G 登山 🏆15%

在这里插入图片描述

这题我只能想到暴力了，就纯模拟。遇到一个点我就往上下左右走去更新最大值。测试用例 AC 了 15%（我前段时间测还 30% 来着），小部分 WA，其他全是 TLE。

下面展示一下我那不堪入目代码。

n, m = map(int, input().split())
mount = [[]] * ndef get_max1(x, y):a, b = mount[x][y], mount[x][y]for i in range(x + 1):a = max(a, mount[i][y])for j in range(y + 1):b = max(b, mount[x][j])return max(a, b)def get_max2(x, y, n, m):max_num1, max_num2 = mount[x][y], mount[x][y]a, b = mount[x][y], mount[x][y]for i in range(x, n):if mount[i][y] > mount[x][y]:max_num1 = mount[i][y]if mount[i][y] < mount[x][y]:a = max_num1for j in range(y, m):if mount[x][j] > mount[x][y]:max_num2 = mount[x][j]if mount[x][j] < mount[x][y]:b = max_num2return max(a, b)for i in range(n):mount[i] = list(map(int, input().split()))
for i in range(n):for j in range(m):max1 = get_max1(i, j)max2 = get_max2(i, j, n, m)mount[i][j] = max(max1, max2)
ret = sum(map(sum, mount)) / (n * m)
print(f"{ret:.6f}")