1. 赛题回顾与核心价值解析又到了备赛季后台和社群里关于蓝桥杯真题的讨论又热了起来。尤其是2020年那届因为疫情原因比赛形式和题目风格都有些特殊很多同学在找真题和解析时发现资料要么零散要么只给个答案背后的思路和踩坑点讲得不清不楚。我自己当年带学生备赛对这套题印象很深它不像往年那样有明确的“送分题”几乎每道题都需要你真正理解算法思想而不是靠背模板。今天我就以一名老教练的视角带大家把这套C B组的国赛题从头到尾“盘”一遍不光是讲怎么做重点讲为什么这么做以及当时考场上的真实思考和那些容易掉进去的坑。这套题对于现在备赛的同学来说价值在于它非常“正”。所谓“正”是指它的考点完全贴合蓝桥杯“重思维、重基础、轻偏怪”的风格没有为了难而难的题目但每道题都卡在基础知识的关键应用上。吃透这套题相当于把你的基础算法能力进行了一次全方位的压力测试。无论是正在备赛的同学想找高质量的模拟题还是刚学完数据结构和算法想检验一下学习成果这套题都是一个绝佳的试金石。接下来我会把十道题分成几个大类结合具体的代码和场景拆解其中的门道。2. 试题分类精讲与解题思维重塑很多人刷题是奔着答案去的但蓝桥杯的真题尤其是国赛题答案往往不是最关键的。关键在于你看到题目时那个“第一反应”的解题方向对不对以及能否在有限时间内把正确的思路实现出来并且规避掉所有的细节陷阱。下面我把题目分成几个典型类别每一类都代表了一种常见的算法思维模式。2.1 模拟与日期处理看似简单实则坑多这类题永远排在前面比如2020年的第一题美丽的2。题目大意是问从1到2020中有多少个数字包含数字‘2’。这看起来是一道纯粹的模拟题但恰恰是这种题最容易失分。失分点不在算法而在粗心和对语言特性的不熟悉。核心思路遍历1到2020将每个整数转换为字符串判断字符串中是否包含字符‘2’。避坑要点遍历边界题目是1到2020for循环的边界条件必须是i 2020。很多同学写循环习惯性写这里就漏掉了2020这个数。转换方法C中整数转字符串常用to_string()函数。这是C11的标准确保你的编译环境支持。别再用sprintf或者手写转换了容易出错。判断逻辑字符串查找可以用find()方法判断返回值是否不等于string::npos。这是最稳妥的写法。#include iostream #include string using namespace std; int main() { int cnt 0; for (int i 1; i 2020; i) { if (to_string(i).find(2) ! string::npos) { cnt; } } cout cnt endl; return 0; }我的实操心得考场上一分钟之内必须拿下这种题。我的建议是在练习时就把这些“坑点”固化成本能看到“从a到b”立刻检查循环是还是看到数字判断立刻想到to_string写完代码后立刻用几个边界值测试一下比如1、2020、以及一个不含2和一个含2的数。2.2 数论与思维突破暴力枚举的局限接下来是第二题扩散。这题非常经典它看起来像一道BFS广度优先搜索的网格模拟题但如果你真用BFS去模拟每一秒的扩散计算量会非常大容易超时。这题考察的是数学抽象和规律转化的能力。题目描述有一个无限大的方格纸初始时在(0,0), (2020,11), (11,14), (2000,2000)四个点有黑点。每一秒每个黑点会向上、下、左、右四个方向扩散一个格子新格子变黑旧黑点保留。问经过2020秒后图上有多少个黑点。暴力BFS的困境点会越来越多队列巨大且判断一个点是否在2020秒内被覆盖需要计算曼哈顿距离直接模拟内存和时间都承受不起。正解思路转化思想 任何一个点(x,y)如果它能被初始的某个黑点(x0,y0)在2020秒内扩散到那么需要满足|x - x0| |y - y0| 2020曼哈顿距离小于等于时间。所以问题转化为在平面上找出所有满足到任意一个初始点的曼哈顿距离 2020 的整点个数。实现方法 我们无法枚举平面上的无限点但可以确定一个有限的搜索范围。以每个初始点为中心曼哈顿距离2020构成一个菱形。所有菱形的并集其外接矩形范围是可以估算的。找到x和y坐标的最小值和最大值然后在这个矩形范围内枚举每一个点判断它到四个初始点的最短曼哈顿距离是否2020即可。#include iostream #include cmath using namespace std; // 四个初始点 int points[4][2] {{0,0}, {2020,11}, {11,14}, {2000,2000}}; int main() { int ans 0; // 估算搜索边界适当扩大一些范围确保覆盖 for (int x -2500; x 4500; x) { for (int y -2500; y 4500; y) { for (int i 0; i 4; i) { int dx abs(x - points[i][0]); int dy abs(y - points[i][1]); if (dx dy 2020) { ans; break; // 只要被一个点覆盖就算立即跳出内层循环 } } } } cout ans endl; return 0; }注意事项搜索范围的估算要足够大宁大勿小。可以通过初始点的坐标加减2020再额外加一个余量比如500来快速确定。这道题的价值在于训练你将动态过程转化为静态条件的能力这是优化很多模拟题的关键。2.3 动态规划与状态设计识别经典模型第五题玩具蛇是一道典型的深度优先搜索(DFS)回溯题但也带有排列组合的色彩。题目把1-16的数字填入4x4的格子要求数字相邻上下左右的格子数字也连续。问有多少种摆放方案蛇从1开始16结束。核心思路 这本质是求在4x4网格中“长度为16的连续路径”有多少条。这里“连续”指路径编号连续。既然1必须作为起点那么问题就变成了在4x4网格中固定起点为1用DFS搜索出所有能走满16个格子即不重复地访问所有格子的路径数量。这就是一个枚举所有哈密顿路径的问题。DFS设计要点状态需要一个visited[4][4]数组记录格子是否被访问过。递归函数参数至少包含当前坐标(x, y)和当前已走的步数step从1开始。递归过程如果step 16说明找到一条完整路径方案数1。否则遍历当前点的四个方向如果新坐标合法且未被访问则标记访问递归进入下一步回溯时取消标记。起点枚举因为1的位置不固定不题目说“玩具蛇”可以从任意格子开始但编号1是蛇头。所以我们需要枚举1在16个格子中的所有可能位置对每个位置作为起点进行DFS。#include iostream using namespace std; int grid[4][4]; bool vis[4][4]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; long long ans 0; // 结果可能很大用long long void dfs(int x, int y, int step) { if (step 16) { ans; return; } for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx 4 ny 0 ny 4 !vis[nx][ny]) { vis[nx][ny] true; dfs(nx, ny, step 1); vis[nx][ny] false; // 回溯 } } } int main() { // 枚举1起点的所有可能位置 for (int i 0; i 4; i) { for (int j 0; j 4; j) { // 每次搜索前初始化访问数组 memset(vis, false, sizeof(vis)); vis[i][j] true; // 起点已访问 dfs(i, j, 1); } } cout ans endl; return 0; }踩坑实录结果变量类型这种计数问题答案往往很大一定要用long long。用int很可能溢出导致错误。起点枚举最容易忽略的点。题目问的是“有多少种不同的摆放方案”1的位置不同当然是不同的方案所以必须枚举所有起点。回溯清理DFS递归返回后一定要将vis[nx][ny]重置为false这是回溯法的核心漏掉就会导致搜索不全。性能4x4网格很小直接DFS可行。如果网格更大就需要剪枝或换用其他算法如状态压缩DP。2.4 字符串与枚举优化避免超时的关键第三题阶乘约数和第四题本质上升序列都属于需要精细枚举和避免重复计算的题目。以第四题本质上升序列为例。题目给出一个长长的字符串2020年的题给的是类似“tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl”这样的字符串要你求其中本质不同的上升子序列个数。上升子序列定义为按原序列顺序提取且每个字符的ASCII码严格递增。暴力DFS的不可行性字符串长度很长子序列个数是指数级的直接枚举所有子序列肯定超时。动态规划思路 定义dp[i]表示以第i个字符结尾的本质不同的上升子序列的个数。注意是“以i结尾”并且是“本质不同”。状态转移 对于当前位置i我们看它前面的所有位置j (0 j i)如果s[j] s[i]那么所有以s[j]结尾的上升子序列后面加上s[i]都能构成一个新的以s[i]结尾的上升子序列。所以dp[i] dp[j]。如果s[j] s[i]这里就是去重的关键对于所有j i且s[j] s[i]的位置以s[j]结尾的子序列集合和以s[i]结尾的子序列集合在只考虑前i个字符时会有重复。更具体地说在计算dp[i]时我们需要减去那些已经被前面相同字符计算过的重复子序列。一个常见的技巧是在遍历j时如果遇到s[j] s[i]我们就把dp[j]从累加中减去或者更简单地在遇到相等字符时直接跳出循环不这不对。正确的去重方法是对于每个i我们只累加最后一次出现的某个字符之前的贡献。但实现起来更清晰的方法是使用一个辅助数组last[26]记录每个字母上一次出现时的dp值然后做减法。简化且正确的DP转移 我们可以这样思考dp[i]初始为1表示只包含s[i]本身这个子序列。 然后遍历所有j i如果s[j] s[i]dp[i] dp[j]。如果s[j] s[i]dp[i] - dp[j]。为什么是减因为对于当前i所有以j这个更早的相同字符结尾的子序列在后面加上s[i]所形成的新子序列与直接以s[i]开头或通过其他路径形成的子序列在最终考虑全部字符时会被重复计算。当我们在j处已经计算过一批以s[j]结尾的子序列后在i处如果再简单累加就会把“s[j]...s[i]”这样的序列重复计算。所以当遇到前面有相同字符时要把之前那个字符所贡献的、会引发重复的那部分减掉。更严谨的实现是记录last数组。最终所有dp[i]的总和就是答案。#include iostream #include string #include vector using namespace std; int main() { string s tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl; int n s.length(); vectorlong long dp(n, 1); // dp[i] 初始为1 long long ans 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if (s[j] s[i]) { dp[i] dp[j]; } else if (s[j] s[i]) { dp[i] - dp[j]; // 关键的去重步骤 } } } for (int i 0; i n; i) { ans dp[i]; } cout ans endl; return 0; }经验之谈字符串DP问题尤其是涉及子序列和去重状态设计和转移方程需要反复推敲。这道题的核心陷阱就是“本质不同”。在考场上如果你能想到用DP并且意识到需要去重就已经成功了一大半。实现时多用手推小样例比如“abac”来验证转移方程的正确性。3. 环境准备与编程实践要点聊完具体题目我们回过头来谈谈应对这类比赛的通法。很多同学算法思路都有但一写代码就各种小问题或者时间不够。这其实和编程环境与习惯密切相关。3.1 编译器选择与配置蓝桥杯比赛环境通常是基于Windows的Dev-C或Code::Blocks但它们的编译器版本可能较旧。平时练习我强烈建议使用Visual Studio Code (VSCode) MinGW-w64的组合或者CLion。原因如下代码提示和调试功能强大VSCode和CLion的代码补全、跳转定义、实时错误检查能极大提升编码效率和准确性。特别是调试器对于排查DFS、DP这类复杂逻辑的bug至关重要。单步执行、查看变量值比盲目cout打印高效得多。项目管理方便可以为每道真题创建一个单独的文件夹里面放main.cpp和测试数据。养成好的项目组织结构比赛时才能不慌。熟悉快捷键熟练使用格式化代码AltShiftF、快速运行、调试等快捷键能节省大量时间。注意比赛前一定要用官方指定的IDE练习几次熟悉其界面和调试方法如果提供的话避免比赛时因工具不熟而影响心态。3.2 标准输入输出与文件操作蓝桥杯的题目都是标准输入输出即从cin读向cout写。这里有几个关键习惯关闭同步流在main函数开头加上ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);。这能显著提升C的输入输出速度尤其是当需要读入大量数据如10万行时。注意一旦关闭同步就不要混用scanf/printf和cin/cout了。使用\\n代替endlendl会刷新输出缓冲区导致频繁IO降低效率。除非需要立即输出否则一律用“\\n”。文件重定向调试在本地调试时经常需要反复输入相同测试数据。一个高效的方法是使用文件重定向。将测试数据保存在in.txt文件中。在main函数里添加以下代码方便切换#ifdef LOCAL freopen(in.txt, r, stdin); // freopen(out.txt, w, stdout); // 如果需要将输出也保存到文件 #endif在编译时定义LOCAL宏例如在VSCode的tasks.json里加-DLOCAL则程序会从in.txt读取提交时无需修改代码因为未定义LOCAL宏程序会从标准输入读取。3.3 常用代码模板与头文件准备一个万能头文件bits/stdc.h虽然方便但并非所有竞赛环境都支持。最稳妥的方法是准备一个自己常用的头文件集合放在代码开头#include iostream #include cstdio #include algorithm #include cmath #include cstring #include string #include vector #include queue #include stack #include set #include map using namespace std; typedef long long ll; const int INF 0x3f3f3f3f; const int MAXN 1e5 10; // 根据题目调整 int main() { ios::sync_with_stdio(false); cin.tie(0); // 你的代码逻辑 return 0; }把long long定义为ll把0x3f3f3f3f作为无穷大这些都是竞赛中节省时间、减少错误的小技巧。4. 考场策略与时间分配实战建议4个小时10道题平均每道题不到25分钟这还包括读题、思考、编码、调试和最后检查的时间。没有策略必然手忙脚乱。4.1 三轮答题法我推荐“三轮答题法”这是我带学生屡试不爽的策略第一轮约60-70分钟快速通读所有题目。不要细想只做两件事1) 给题目分类模拟、搜索、DP、图论、数学等2) 预估难度和耗时。把一眼就有清晰思路的“签到题”标记出来比如“美丽的2”这种。第二轮约2小时主攻阶段。按照“先易后难”的原则集中精力解决标记的简单题和中等题。每做一题务必确保样例通过并且自己设计1-2个边界案例测试。在这一轮要争取拿下至少6-7道题的基本分。第三轮约50-60分钟攻坚与检查。剩下的时间挑战难题同时必须留出至少15-20分钟进行整体检查。检查什么1) 文件名、类名、函数名是否符合要求蓝桥杯有时要求提交特定函数。2) 输入输出格式特别是空格和换行。3) 重新运行一遍所有题目用样例和自己造的测试数据验证。4) 检查long long溢出、数组越界等常见错误。4.2 遇到难题的应对思路暴力骗分对于完全没有思路的题如果数据范围很小比如n20果断写一个暴力枚举DFS、全排列的代码。蓝桥杯是OI赛制有部分分。一个能过小数据范围的暴力程序可能就能拿到30%-50%的分数这比空着强太多。打表找规律有些数学题或规律题可以写个小程序枚举前几十项把结果输出然后观察规律。如果发现规律比如是斐波那契数列、卡特兰数等可以直接根据规律写出公式或递推。注意打表程序要单独写找到规律后再用简洁的公式代码提交。放弃的艺术如果一道题卡了超过40分钟依然毫无进展明智的做法是暂时放弃回头检查已做题目或者去尝试其他题。把所有时间赌在一道题上是最不划算的。4.3 代码调试与验证技巧小数据调试用题目给的样例调试是最基本的。此外一定要自己构造最小数据和边界数据。比如排序题试试空数组、单元素数组、已排序数组、逆序数组。输出中间变量在怀疑的代码段前后输出关键变量的值。这是最原始但最有效的调试方法。调试完后记得注释掉这些调试输出语句。使用assert在代码中合理使用assert宏可以帮助你快速定位假设不成立的地方。例如assert(index 0 index n);。对拍对于复杂题如果你写了一个优化算法如DP同时也能写一个绝对正确但很慢的暴力算法如DFS。可以写一个脚本随机生成大量小规模测试数据分别用两个程序跑对比结果是否一致。这是确保算法正确性的终极手段。5. 从2020年真题看备赛重点与能力提升分析完这套题我们可以清晰地看到蓝桥杯国赛的考察重点和趋势这对于备赛有极强的指导意义。5.1 考察能力维度分析扎实的编程基础第一题的字符串处理、循环边界考察的就是最基本、最扎实的编码能力。任何微小的疏忽都会导致丢分。数学建模与转化能力第二题“扩散”是典型代表。它要求你将一个物理扩散过程抽象为曼哈顿距离的数学问题。这种将实际问题转化为可计算模型的能力是高级竞赛的核心。经典算法的深入理解与灵活应用第五题“玩具蛇”考察DFS回溯第四题“本质上升序列”考察DP及其去重。这里不是考你背模板而是考你是否真正理解了这些算法的状态定义和转移过程并能根据具体问题进行调整如去重。优化与剪枝意识在数据范围较大的题目中暴力法往往不可行。你需要有意识地去分析时间复杂度并寻找优化方法例如将O(n²)优化为O(n log n)或者利用数学性质减少计算量。5.2 备赛训练建议基于以上分析我给备赛同学的建议是分模块刷题建立知识体系不要盲目刷题。将算法分为几个大模块基础语法与模拟、排序与查找、递归与搜索DFS/BFS、动态规划、贪心、数论、图论、字符串。每个模块找一本经典的教材或题库如《算法竞赛入门经典》进行系统性学习与练习。重视真题精做而非泛做像2020年这套真题值得做三遍以上。第一遍独立限时完成模拟考场环境。第二遍不看答案重新思考尝试用不同的方法解题并写下详细的解题报告包括思路分析、时间复杂度和空间复杂度。第三遍隔一段时间后再做检验是否真正掌握。建立错题本与思维笔记记录下每道错题或难题分析错误原因是思路错误、边界条件忽略、语法错误还是优化不到位同时记录下优秀的解题思路和技巧比如“扩散”题的曼哈顿距离转化。刻意练习调试能力拿出专门的时间练习调试技巧。故意在代码中制造一些常见bug如数组越界、死循环、初始化错误然后练习如何使用调试器快速定位和修复。组队模拟与讨论如果可能找水平相当的同学组队定期进行模拟赛。赛后一起讨论解题思路分享不同的解法。在讲解给别人听的过程中你自己的理解也会更加深刻。刷题就像练武真题就是最好的“武功秘籍”。2020年这套C B组国赛题就像一套组合拳既检验了你的马步基础是否扎实也考验了你对招式算法的理解是否透彻更测试了你临场应变策略的能力。希望这篇超详细的拆解能帮你不仅看懂这几道题更能摸清蓝桥杯乃至同类算法竞赛的命门所在。记住编程能力的提升没有捷径唯手熟尔。多思考、多总结、多动手下一个在赛场上游刃有余的就是你。如果在练习具体的题目时还有哪里卡壳随时可以再来交流。 
长河君 · 2026/8/28 8:22:16 · 阅读 1.2k 蓝桥杯2020年C++ B组国赛真题深度解析与备赛指南
1. 赛题回顾与核心价值解析又到了备赛季后台和社群里关于蓝桥杯真题的讨论又热了起来。尤其是2020年那届因为疫情原因比赛形式和题目风格都有些特殊很多同学在找真题和解析时发现资料要么零散要么只给个答案背后的思路和踩坑点讲得不清不楚。我自己当年带学生备赛对这套题印象很深它不像往年那样有明确的“送分题”几乎每道题都需要你真正理解算法思想而不是靠背模板。今天我就以一名老教练的视角带大家把这套C B组的国赛题从头到尾“盘”一遍不光是讲怎么做重点讲为什么这么做以及当时考场上的真实思考和那些容易掉进去的坑。这套题对于现在备赛的同学来说价值在于它非常“正”。所谓“正”是指它的考点完全贴合蓝桥杯“重思维、重基础、轻偏怪”的风格没有为了难而难的题目但每道题都卡在基础知识的关键应用上。吃透这套题相当于把你的基础算法能力进行了一次全方位的压力测试。无论是正在备赛的同学想找高质量的模拟题还是刚学完数据结构和算法想检验一下学习成果这套题都是一个绝佳的试金石。接下来我会把十道题分成几个大类结合具体的代码和场景拆解其中的门道。2. 试题分类精讲与解题思维重塑很多人刷题是奔着答案去的但蓝桥杯的真题尤其是国赛题答案往往不是最关键的。关键在于你看到题目时那个“第一反应”的解题方向对不对以及能否在有限时间内把正确的思路实现出来并且规避掉所有的细节陷阱。下面我把题目分成几个典型类别每一类都代表了一种常见的算法思维模式。2.1 模拟与日期处理看似简单实则坑多这类题永远排在前面比如2020年的第一题美丽的2。题目大意是问从1到2020中有多少个数字包含数字‘2’。这看起来是一道纯粹的模拟题但恰恰是这种题最容易失分。失分点不在算法而在粗心和对语言特性的不熟悉。核心思路遍历1到2020将每个整数转换为字符串判断字符串中是否包含字符‘2’。避坑要点遍历边界题目是1到2020for循环的边界条件必须是i 2020。很多同学写循环习惯性写这里就漏掉了2020这个数。转换方法C中整数转字符串常用to_string()函数。这是C11的标准确保你的编译环境支持。别再用sprintf或者手写转换了容易出错。判断逻辑字符串查找可以用find()方法判断返回值是否不等于string::npos。这是最稳妥的写法。#include iostream #include string using namespace std; int main() { int cnt 0; for (int i 1; i 2020; i) { if (to_string(i).find(2) ! string::npos) { cnt; } } cout cnt endl; return 0; }我的实操心得考场上一分钟之内必须拿下这种题。我的建议是在练习时就把这些“坑点”固化成本能看到“从a到b”立刻检查循环是还是看到数字判断立刻想到to_string写完代码后立刻用几个边界值测试一下比如1、2020、以及一个不含2和一个含2的数。2.2 数论与思维突破暴力枚举的局限接下来是第二题扩散。这题非常经典它看起来像一道BFS广度优先搜索的网格模拟题但如果你真用BFS去模拟每一秒的扩散计算量会非常大容易超时。这题考察的是数学抽象和规律转化的能力。题目描述有一个无限大的方格纸初始时在(0,0), (2020,11), (11,14), (2000,2000)四个点有黑点。每一秒每个黑点会向上、下、左、右四个方向扩散一个格子新格子变黑旧黑点保留。问经过2020秒后图上有多少个黑点。暴力BFS的困境点会越来越多队列巨大且判断一个点是否在2020秒内被覆盖需要计算曼哈顿距离直接模拟内存和时间都承受不起。正解思路转化思想 任何一个点(x,y)如果它能被初始的某个黑点(x0,y0)在2020秒内扩散到那么需要满足|x - x0| |y - y0| 2020曼哈顿距离小于等于时间。所以问题转化为在平面上找出所有满足到任意一个初始点的曼哈顿距离 2020 的整点个数。实现方法 我们无法枚举平面上的无限点但可以确定一个有限的搜索范围。以每个初始点为中心曼哈顿距离2020构成一个菱形。所有菱形的并集其外接矩形范围是可以估算的。找到x和y坐标的最小值和最大值然后在这个矩形范围内枚举每一个点判断它到四个初始点的最短曼哈顿距离是否2020即可。#include iostream #include cmath using namespace std; // 四个初始点 int points[4][2] {{0,0}, {2020,11}, {11,14}, {2000,2000}}; int main() { int ans 0; // 估算搜索边界适当扩大一些范围确保覆盖 for (int x -2500; x 4500; x) { for (int y -2500; y 4500; y) { for (int i 0; i 4; i) { int dx abs(x - points[i][0]); int dy abs(y - points[i][1]); if (dx dy 2020) { ans; break; // 只要被一个点覆盖就算立即跳出内层循环 } } } } cout ans endl; return 0; }注意事项搜索范围的估算要足够大宁大勿小。可以通过初始点的坐标加减2020再额外加一个余量比如500来快速确定。这道题的价值在于训练你将动态过程转化为静态条件的能力这是优化很多模拟题的关键。2.3 动态规划与状态设计识别经典模型第五题玩具蛇是一道典型的深度优先搜索(DFS)回溯题但也带有排列组合的色彩。题目把1-16的数字填入4x4的格子要求数字相邻上下左右的格子数字也连续。问有多少种摆放方案蛇从1开始16结束。核心思路 这本质是求在4x4网格中“长度为16的连续路径”有多少条。这里“连续”指路径编号连续。既然1必须作为起点那么问题就变成了在4x4网格中固定起点为1用DFS搜索出所有能走满16个格子即不重复地访问所有格子的路径数量。这就是一个枚举所有哈密顿路径的问题。DFS设计要点状态需要一个visited[4][4]数组记录格子是否被访问过。递归函数参数至少包含当前坐标(x, y)和当前已走的步数step从1开始。递归过程如果step 16说明找到一条完整路径方案数1。否则遍历当前点的四个方向如果新坐标合法且未被访问则标记访问递归进入下一步回溯时取消标记。起点枚举因为1的位置不固定不题目说“玩具蛇”可以从任意格子开始但编号1是蛇头。所以我们需要枚举1在16个格子中的所有可能位置对每个位置作为起点进行DFS。#include iostream using namespace std; int grid[4][4]; bool vis[4][4]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; long long ans 0; // 结果可能很大用long long void dfs(int x, int y, int step) { if (step 16) { ans; return; } for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx 4 ny 0 ny 4 !vis[nx][ny]) { vis[nx][ny] true; dfs(nx, ny, step 1); vis[nx][ny] false; // 回溯 } } } int main() { // 枚举1起点的所有可能位置 for (int i 0; i 4; i) { for (int j 0; j 4; j) { // 每次搜索前初始化访问数组 memset(vis, false, sizeof(vis)); vis[i][j] true; // 起点已访问 dfs(i, j, 1); } } cout ans endl; return 0; }踩坑实录结果变量类型这种计数问题答案往往很大一定要用long long。用int很可能溢出导致错误。起点枚举最容易忽略的点。题目问的是“有多少种不同的摆放方案”1的位置不同当然是不同的方案所以必须枚举所有起点。回溯清理DFS递归返回后一定要将vis[nx][ny]重置为false这是回溯法的核心漏掉就会导致搜索不全。性能4x4网格很小直接DFS可行。如果网格更大就需要剪枝或换用其他算法如状态压缩DP。2.4 字符串与枚举优化避免超时的关键第三题阶乘约数和第四题本质上升序列都属于需要精细枚举和避免重复计算的题目。以第四题本质上升序列为例。题目给出一个长长的字符串2020年的题给的是类似“tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl”这样的字符串要你求其中本质不同的上升子序列个数。上升子序列定义为按原序列顺序提取且每个字符的ASCII码严格递增。暴力DFS的不可行性字符串长度很长子序列个数是指数级的直接枚举所有子序列肯定超时。动态规划思路 定义dp[i]表示以第i个字符结尾的本质不同的上升子序列的个数。注意是“以i结尾”并且是“本质不同”。状态转移 对于当前位置i我们看它前面的所有位置j (0 j i)如果s[j] s[i]那么所有以s[j]结尾的上升子序列后面加上s[i]都能构成一个新的以s[i]结尾的上升子序列。所以dp[i] dp[j]。如果s[j] s[i]这里就是去重的关键对于所有j i且s[j] s[i]的位置以s[j]结尾的子序列集合和以s[i]结尾的子序列集合在只考虑前i个字符时会有重复。更具体地说在计算dp[i]时我们需要减去那些已经被前面相同字符计算过的重复子序列。一个常见的技巧是在遍历j时如果遇到s[j] s[i]我们就把dp[j]从累加中减去或者更简单地在遇到相等字符时直接跳出循环不这不对。正确的去重方法是对于每个i我们只累加最后一次出现的某个字符之前的贡献。但实现起来更清晰的方法是使用一个辅助数组last[26]记录每个字母上一次出现时的dp值然后做减法。简化且正确的DP转移 我们可以这样思考dp[i]初始为1表示只包含s[i]本身这个子序列。 然后遍历所有j i如果s[j] s[i]dp[i] dp[j]。如果s[j] s[i]dp[i] - dp[j]。为什么是减因为对于当前i所有以j这个更早的相同字符结尾的子序列在后面加上s[i]所形成的新子序列与直接以s[i]开头或通过其他路径形成的子序列在最终考虑全部字符时会被重复计算。当我们在j处已经计算过一批以s[j]结尾的子序列后在i处如果再简单累加就会把“s[j]...s[i]”这样的序列重复计算。所以当遇到前面有相同字符时要把之前那个字符所贡献的、会引发重复的那部分减掉。更严谨的实现是记录last数组。最终所有dp[i]的总和就是答案。#include iostream #include string #include vector using namespace std; int main() { string s tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl; int n s.length(); vectorlong long dp(n, 1); // dp[i] 初始为1 long long ans 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if (s[j] s[i]) { dp[i] dp[j]; } else if (s[j] s[i]) { dp[i] - dp[j]; // 关键的去重步骤 } } } for (int i 0; i n; i) { ans dp[i]; } cout ans endl; return 0; }经验之谈字符串DP问题尤其是涉及子序列和去重状态设计和转移方程需要反复推敲。这道题的核心陷阱就是“本质不同”。在考场上如果你能想到用DP并且意识到需要去重就已经成功了一大半。实现时多用手推小样例比如“abac”来验证转移方程的正确性。3. 环境准备与编程实践要点聊完具体题目我们回过头来谈谈应对这类比赛的通法。很多同学算法思路都有但一写代码就各种小问题或者时间不够。这其实和编程环境与习惯密切相关。3.1 编译器选择与配置蓝桥杯比赛环境通常是基于Windows的Dev-C或Code::Blocks但它们的编译器版本可能较旧。平时练习我强烈建议使用Visual Studio Code (VSCode) MinGW-w64的组合或者CLion。原因如下代码提示和调试功能强大VSCode和CLion的代码补全、跳转定义、实时错误检查能极大提升编码效率和准确性。特别是调试器对于排查DFS、DP这类复杂逻辑的bug至关重要。单步执行、查看变量值比盲目cout打印高效得多。项目管理方便可以为每道真题创建一个单独的文件夹里面放main.cpp和测试数据。养成好的项目组织结构比赛时才能不慌。熟悉快捷键熟练使用格式化代码AltShiftF、快速运行、调试等快捷键能节省大量时间。注意比赛前一定要用官方指定的IDE练习几次熟悉其界面和调试方法如果提供的话避免比赛时因工具不熟而影响心态。3.2 标准输入输出与文件操作蓝桥杯的题目都是标准输入输出即从cin读向cout写。这里有几个关键习惯关闭同步流在main函数开头加上ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);。这能显著提升C的输入输出速度尤其是当需要读入大量数据如10万行时。注意一旦关闭同步就不要混用scanf/printf和cin/cout了。使用\\n代替endlendl会刷新输出缓冲区导致频繁IO降低效率。除非需要立即输出否则一律用“\\n”。文件重定向调试在本地调试时经常需要反复输入相同测试数据。一个高效的方法是使用文件重定向。将测试数据保存在in.txt文件中。在main函数里添加以下代码方便切换#ifdef LOCAL freopen(in.txt, r, stdin); // freopen(out.txt, w, stdout); // 如果需要将输出也保存到文件 #endif在编译时定义LOCAL宏例如在VSCode的tasks.json里加-DLOCAL则程序会从in.txt读取提交时无需修改代码因为未定义LOCAL宏程序会从标准输入读取。3.3 常用代码模板与头文件准备一个万能头文件bits/stdc.h虽然方便但并非所有竞赛环境都支持。最稳妥的方法是准备一个自己常用的头文件集合放在代码开头#include iostream #include cstdio #include algorithm #include cmath #include cstring #include string #include vector #include queue #include stack #include set #include map using namespace std; typedef long long ll; const int INF 0x3f3f3f3f; const int MAXN 1e5 10; // 根据题目调整 int main() { ios::sync_with_stdio(false); cin.tie(0); // 你的代码逻辑 return 0; }把long long定义为ll把0x3f3f3f3f作为无穷大这些都是竞赛中节省时间、减少错误的小技巧。4. 考场策略与时间分配实战建议4个小时10道题平均每道题不到25分钟这还包括读题、思考、编码、调试和最后检查的时间。没有策略必然手忙脚乱。4.1 三轮答题法我推荐“三轮答题法”这是我带学生屡试不爽的策略第一轮约60-70分钟快速通读所有题目。不要细想只做两件事1) 给题目分类模拟、搜索、DP、图论、数学等2) 预估难度和耗时。把一眼就有清晰思路的“签到题”标记出来比如“美丽的2”这种。第二轮约2小时主攻阶段。按照“先易后难”的原则集中精力解决标记的简单题和中等题。每做一题务必确保样例通过并且自己设计1-2个边界案例测试。在这一轮要争取拿下至少6-7道题的基本分。第三轮约50-60分钟攻坚与检查。剩下的时间挑战难题同时必须留出至少15-20分钟进行整体检查。检查什么1) 文件名、类名、函数名是否符合要求蓝桥杯有时要求提交特定函数。2) 输入输出格式特别是空格和换行。3) 重新运行一遍所有题目用样例和自己造的测试数据验证。4) 检查long long溢出、数组越界等常见错误。4.2 遇到难题的应对思路暴力骗分对于完全没有思路的题如果数据范围很小比如n20果断写一个暴力枚举DFS、全排列的代码。蓝桥杯是OI赛制有部分分。一个能过小数据范围的暴力程序可能就能拿到30%-50%的分数这比空着强太多。打表找规律有些数学题或规律题可以写个小程序枚举前几十项把结果输出然后观察规律。如果发现规律比如是斐波那契数列、卡特兰数等可以直接根据规律写出公式或递推。注意打表程序要单独写找到规律后再用简洁的公式代码提交。放弃的艺术如果一道题卡了超过40分钟依然毫无进展明智的做法是暂时放弃回头检查已做题目或者去尝试其他题。把所有时间赌在一道题上是最不划算的。4.3 代码调试与验证技巧小数据调试用题目给的样例调试是最基本的。此外一定要自己构造最小数据和边界数据。比如排序题试试空数组、单元素数组、已排序数组、逆序数组。输出中间变量在怀疑的代码段前后输出关键变量的值。这是最原始但最有效的调试方法。调试完后记得注释掉这些调试输出语句。使用assert在代码中合理使用assert宏可以帮助你快速定位假设不成立的地方。例如assert(index 0 index n);。对拍对于复杂题如果你写了一个优化算法如DP同时也能写一个绝对正确但很慢的暴力算法如DFS。可以写一个脚本随机生成大量小规模测试数据分别用两个程序跑对比结果是否一致。这是确保算法正确性的终极手段。5. 从2020年真题看备赛重点与能力提升分析完这套题我们可以清晰地看到蓝桥杯国赛的考察重点和趋势这对于备赛有极强的指导意义。5.1 考察能力维度分析扎实的编程基础第一题的字符串处理、循环边界考察的就是最基本、最扎实的编码能力。任何微小的疏忽都会导致丢分。数学建模与转化能力第二题“扩散”是典型代表。它要求你将一个物理扩散过程抽象为曼哈顿距离的数学问题。这种将实际问题转化为可计算模型的能力是高级竞赛的核心。经典算法的深入理解与灵活应用第五题“玩具蛇”考察DFS回溯第四题“本质上升序列”考察DP及其去重。这里不是考你背模板而是考你是否真正理解了这些算法的状态定义和转移过程并能根据具体问题进行调整如去重。优化与剪枝意识在数据范围较大的题目中暴力法往往不可行。你需要有意识地去分析时间复杂度并寻找优化方法例如将O(n²)优化为O(n log n)或者利用数学性质减少计算量。5.2 备赛训练建议基于以上分析我给备赛同学的建议是分模块刷题建立知识体系不要盲目刷题。将算法分为几个大模块基础语法与模拟、排序与查找、递归与搜索DFS/BFS、动态规划、贪心、数论、图论、字符串。每个模块找一本经典的教材或题库如《算法竞赛入门经典》进行系统性学习与练习。重视真题精做而非泛做像2020年这套真题值得做三遍以上。第一遍独立限时完成模拟考场环境。第二遍不看答案重新思考尝试用不同的方法解题并写下详细的解题报告包括思路分析、时间复杂度和空间复杂度。第三遍隔一段时间后再做检验是否真正掌握。建立错题本与思维笔记记录下每道错题或难题分析错误原因是思路错误、边界条件忽略、语法错误还是优化不到位同时记录下优秀的解题思路和技巧比如“扩散”题的曼哈顿距离转化。刻意练习调试能力拿出专门的时间练习调试技巧。故意在代码中制造一些常见bug如数组越界、死循环、初始化错误然后练习如何使用调试器快速定位和修复。组队模拟与讨论如果可能找水平相当的同学组队定期进行模拟赛。赛后一起讨论解题思路分享不同的解法。在讲解给别人听的过程中你自己的理解也会更加深刻。刷题就像练武真题就是最好的“武功秘籍”。2020年这套C B组国赛题就像一套组合拳既检验了你的马步基础是否扎实也考验了你对招式算法的理解是否透彻更测试了你临场应变策略的能力。希望这篇超详细的拆解能帮你不仅看懂这几道题更能摸清蓝桥杯乃至同类算法竞赛的命门所在。记住编程能力的提升没有捷径唯手熟尔。多思考、多总结、多动手下一个在赛场上游刃有余的就是你。如果在练习具体的题目时还有哪里卡壳随时可以再来交流。