1. 项目概述一次算法竞赛的深度复盘又到了每年备赛蓝桥杯的季节后台和社群里不少同学开始翻找往年的真题尤其是想找带详细分析和代码的题解。今天我就以2022年第十三届蓝桥杯软件类省赛C B组的真题为例带大家做一次深度的复盘。这不仅仅是一份“答案”我更想分享的是面对这些题目时一个竞赛老手的思考路径、解题策略以及那些容易踩坑的细节。无论你是正在备赛的选手还是想通过真题提升自己算法能力的C开发者相信这份超过5000字的“实战笔记”都能给你带来不一样的启发。蓝桥杯发展到今天其省赛题目已经形成了相对稳定的风格考察点全面从基础的语法、模拟题到中等难度的动态规划、搜索再到需要一定思维深度的贪心、数论问题都有涉及。B组的题目难度适中非常适合用来检验自己的编程基础和算法入门水平。复盘一场比赛价值远大于单纯地AC几道题。我们要搞清楚每道题背后的考点、可能的陷阱、时间复杂度的边界以及如何写出既正确又优雅的代码。接下来我们就一道一道地拆解。2. 试题整体分析与解题策略2.1 赛题结构与时间分配建议2022年C B组省赛共有8道填空题和4道编程大题。这是蓝桥杯的经典题型配置。填空题通常考察一些巧妙的计算、模拟或者基础的数论/排列组合知识答案一般是数字或字符串。编程题则要求提交完整的源代码在线评测系统会根据你的输出结果判分。面对这样一场比赛合理的时间分配至关重要。我的建议是前1小时快速浏览所有填空题。目标是找出那些一眼就有思路的“签到题”比如纯模拟或者简单计算。确保这些题的分数稳稳拿到。对于一时没思路的填空题不要纠结做好标记后跳过。中间2-2.5小时主攻编程大题。优先解决题干描述清晰、数据范围明确、你熟悉的算法模型如线性DP、BFS/DFS、简单贪心的题目。每道题争取一次写对避免因调试占用过多时间。最后0.5-1小时回头攻坚剩下的填空题和编程题中的难点。检查已做题目的输入输出格式、边界条件。对于填空题可以尝试暴力枚举、打表等“笨”方法在时间允许且数据范围可控的情况下这是非常有效的策略。2.2 环境与编码习惯比赛使用的是类似OJ的环境通常需要从标准输入cin读取数据向标准输出cout输出结果。有几点必须注意文件读写除非明确要求否则绝对不要使用文件操作freopen,ifstream。代码中一旦出现评测时会导致找不到文件而运行错误。万能头文件为了节省时间强烈建议使用#include bits/stdc.h和using namespace std;。在竞赛中这能避免因忘记包含某个头文件而编译失败。输入输出优化当输入输出数据量较大时比如超过10^5默认的cin/cout可能与scanf/printf存在效率差距。一个简单的优化是在main函数开头加入ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);。这可以解除C标准流与C标准流的同步提升速度。之后可以安全地混用cin/cout和scanf/printf但更建议统一使用cin/cout可读性更好。变量初始化这是新手最容易出错的地方之一。特别是用于计数的变量、累加的变量在使用前一定要初始化如int sum 0;。全局变量默认初始化为0但局部变量不会其值是未定义的垃圾值。注意在编程大题中务必仔细阅读数据规模与约定。它直接决定了你算法的可行性。例如n 20可能暗示回溯或状压DPn 10^5则要求你的算法至少是O(n log n)或O(n)的复杂度。3. 填空题详解与思维拓展填空题虽然只要求答案但理解其求解过程对锻炼思维至关重要。我们挑几道有代表性的进行解析。3.1 试题A九进制转十进制问题描述计算九进制数2022对应的十进制数。解题思路这是一道纯签到题考察进制转换的基本功。对于任何进制数将其按权展开求和即可。 公式(abcd...)_n a*n^(k-1) b*n^(k-2) ... d*n^0其中k是数字位数。 所以(2022)_9 2*9^3 0*9^2 2*9^1 2*9^0 2*729 0 2*9 2*1 1458 0 18 2 1478。答案1478思维拓展在代码中如何实现任意进制转十进制核心是一个循环string s “2022”; // 九进制数字符串 int base 9; int ans 0; for(char c : s) { ans ans * base (c - ‘0’); // 秦九韶算法边读边算 } cout ans endl;3.2 试题B顺子日期问题描述找出2022年中日期表示是8位数字yyyymmdd且其中包含一个3位连续递增数字的日期有多少个。例如20220123中“123”就是一个顺子。解题思路这是一道模拟题需要仔细理解题意。关键点在于“顺子”的定义必须是3位连续递增的数字。日期是8位数我们需要检查这8位数中是否存在任意连续的3位满足后一位恰好比前一位大1。 暴力枚举即可。我们可以枚举2022年的每一天构造出8位字符串然后检查其中是否存在长度为3的顺子。注意顺子“789”和“890”也是合法的但“891”不算因为9到1不是递增1。更高效的做法是直接思维枚举。月份和日期是有限的。顺子可能出现在1) 跨月和日的连接处2) 日期的内部。经过手动枚举和校验这是一个很好的练习我们可以得出答案。答案14实操心得这类题目最容易出错的地方是边界条件和理解偏差。比如顺子“012”是否合法题目说“连续递增数字”0,1,2是连续的所以合法。再比如日期是否要有效当然必须是2022年的真实有效日期。写代码验证时一定要处理好月份和日期的有效性检查闰年2022年不是闰年2月只有28天。3.3 试题C刷题统计问题描述小明决定从下周一开始周一刷题。他周一至周五每天做a道题周六和周日每天做b道题。给定a, b和总题数n问小明需要多少天才能完成。解题思路简单模拟或数学计算。先计算一周的总刷题量week_sum 5*a 2*b。 用总题数n除以week_sum得到完整的周数weeks和剩余题数remain。 然后用剩余题数remain模拟一周内的每天减去相应的题数直到remain 0。总天数就是weeks * 7 模拟的天数。答案取决于输入a, b, n。这是一道编程题填空题需要写代码计算。代码框架#include bits/stdc.h using namespace std; typedef long long ll; // 注意数据范围总题数n可能很大需要用long long int main() { ll a, b, n; cin a b n; ll week_sum 5*a 2*b; ll weeks n / week_sum; ll remain n % week_sum; ll days weeks * 7; ll daily[] {a, a, a, a, a, b, b}; // 周一到周日 for(int i 0; i 7 remain 0; i) { remain - daily[i]; days; } cout days endl; return 0; }3.4 其他填空题要点由于篇幅限制其他填空题只做要点提示试题D修剪灌木找规律题。对于位置i的灌木其最大高度取决于它到两端距离的最大值乘以2。公式为max(i-1, n-i) * 2。试题EX进制减法数位DP或贪心思维。核心是理解“X进制”每一位的基数不同且为了使A-B最小每一位的进制数应尽可能小但不能小于对应数位上的数字1因为进制数要大于数字。最终结果是每一位的权重累加。试题F~H通常涉及更复杂的模拟、贪心或初步的DP思想。例如有一道题关于“统计子矩阵”需要用到二维前缀和双指针优化是编程题的常见前置。填空题的总结“暴力枚举”是神器。在比赛时间紧张且数据范围允许的情况下比如状态数在10^7以内写一个暴力程序跑出答案是完全可行的策略。尤其是在本地环境运行不占评测时间。4. 编程大题核心解析与代码实现编程大题是区分度的关键。我们选取两道最具代表性的题目进行深度剖析。4.1 试题I李白打酒加强版问题描述李白壶中初始有2斗酒。遇店加一倍酒量乘2遇花喝一斗酒量减1。这一路共遇店N次遇花M次。已知最后一次遇到的是花且他正好把酒喝光了。求这一路可能的事件顺序店和花的排列有多少种。解题思路这是经典的动态规划问题。状态设计是核心。状态定义dp[i][j][k]表示遇到i次店、j次花后壶中酒量为k的方案数。其中0 i N,0 j M,0 k M因为最多喝M斗酒酒量不可能超过M。状态转移当前状态可以由“上一次遇到店”转移而来如果i 0且k是偶数因为遇店翻倍则dp[i][j][k] dp[i-1][j][k/2]。当前状态也可以由“上一次遇到花”转移而来如果j 0则dp[i][j][k] dp[i][j-1][k1]因为遇花喝一斗所以前一次的酒量要比现在多1斗。初始化dp[0][0][2] 1表示初始状态0店0花酒量为2有一种方案。最终答案dp[N][M][0]注意题目要求最后一次是花且酒喝完所以状态是遇到N店、M花后酒量为0。并且在转移过程中要保证j M时酒量k不能为0因为最后一次遇到花之前酒就喝完的话不符合题意。注意事项模运算答案可能很大题目通常要求取模如1000000007。每次状态转移相加后都要立即取模。边界判断在转移时要确保数组下标不越界。特别是从dp[i][j-1][k1]转移时要保证k1 M。空间优化这是一个三维DP如果N和M在100左右三维数组101*101*101大约需要1e6个long long空间是足够的约8MB。如果数据更大可以考虑滚动数组优化第一维或第二维。核心代码实现#include bits/stdc.h using namespace std; const int MOD 1000000007; int main() { int n, m; cin n m; // dp[i][j][k]: 已遇i店j花剩k斗酒的方案数 vectorvectorvectorlong long dp(n1, vectorvectorlong long(m1, vectorlong long(m2, 0))); dp[0][0][2] 1; // 初始化 for(int i 0; i n; i) { for(int j 0; j m; j) { for(int k 0; k m; k) { // 酒量不可能超过m if(dp[i][j][k] 0) continue; long long val dp[i][j][k]; // 1. 下一次遇到店 if(i n k * 2 m) { // 注意酒量翻倍后不能超过上限m dp[i1][j][k*2] (dp[i1][j][k*2] val) % MOD; } // 2. 下一次遇到花 if(j m) { // 关键如果不是最后一次遇花则酒量必须大于0才能喝 // 如果是最后一次遇花j1 m则要求k1喝完后为0 // 我们可以统一处理为只要k 0就可以转移。 // 但最终答案我们只取dp[n][m][0]这个状态只能由dp[n][m-1][1]转移而来自然满足了最后一次遇花喝完的条件。 if(k 0) { dp[i][j1][k-1] (dp[i][j1][k-1] val) % MOD; } } } } } // 最终状态遇店n次遇花m次酒量为0。注意由于我们的转移保证了遇花时k0所以dp[n][m][0]只能由“上一次酒量为1遇花喝完”转移来。 // 但更严谨的答案应该是 dp[n][m-1][1]表示在遇到第m次花之前酒量为1然后最后一次遇花喝完。 // 实际上我们的dp定义中dp[i][j][k]是“已遇”i店j花后的状态。所以答案是dp[n][m][0]。 // 验证当jm时不能再遇花了所以dp[n][m][0]这个状态只能通过“在状态(n, m-1, 1)时遇花”达到。 cout dp[n][m][0] endl; return 0; }这道题是动态规划的经典练习很好地考察了对状态的设计和对题目条件的转化能力。4.2 试题J砍竹子问题描述有n棵竹子排成一排初始高度分别为h1, h2, ..., hn。每次操作可以选择一棵高度大于1的竹子将其砍倒竹子高度会变为floor(sqrt(floor(h/2)1))。问最少需要多少次操作才能让所有竹子的高度都变为1。解题思路这道题需要仔细分析操作的性质。直接对每棵竹子模拟砍伐过程然后求和操作次数是不行的因为操作可以同时进行题目理解每次操作是选择一棵竹子砍但不同竹子的操作次数可以并行计算吗需要审题。实际上问题等价于对于每棵竹子计算它从初始高度hi通过不断应用函数f(x) floor(sqrt(floor(x/2)1))直到变为1所需的步数。然后对于相邻的竹子如果它们在砍伐过程中出现了相同的高度那么这些步骤可以视为“同时”发生从而减少总操作次数。更具体的贪心策略是预处理出每棵竹子从初始高度到1的整个“高度变化序列”。例如竹子i的高度变化为hi - a1 - a2 - ... - 1。从高度1开始向上逆向考虑。操作的总次数可以看作是所有竹子“高度变化序列”合并后序列中不同“层”的数量。但相邻竹子的相同高度变化可以合并计算。一种有效的方法是使用优先队列大根堆。每次取出当前所有竹子中高度最高的那一棵假设是第i棵高度为maxH进行操作。但这样模拟仍然很慢。正解是贪心数学性质分析。经过观察或推导可以发现函数f(x)下降得非常快。一个很大的数如10^18也只需要很少的次数大概几十次就能变成1。因此我们可以对每棵竹子单独计算出其高度变化序列长度很小。然后我们考虑如何合并操作。想象一个时间轴从最后一步高度变为1向前推。如果两棵相邻的竹子在某个时刻或者说在它们各自的高度变化序列中拥有相同的高度那么它们可以在同一次操作中达到这个高度即从上一个状态砍下来。我们的目标是最大化这种“合并”。实现时可以用一个栈来辅助。从第一棵竹子开始依次处理每棵竹子的高度序列从当前高度向1递减。在处理第i棵竹子时将其高度序列与第i-1棵竹子的高度序列进行比较从低向高比较。如果遇到相同的高度则可以合并操作即这个高度的操作不需要额外计数。否则就需要新的操作。核心难点在于理解“操作合并”的条件和实现方法。这需要将每棵竹子的砍伐过程看作一个栈从高到低然后比较相邻两个栈的公共前缀。简化版思路与代码框架 由于严格的正解代码较长这里给出一个易于理解且能通过大部分测试点的思路我们分别计算每棵竹子变成1所需的步骤序列。然后总操作次数 所有竹子步骤数之和 - 可以合并的步骤。 如何计算可合并的步骤对于相邻的两棵竹子i和i1从高度1开始向上比较它们的变化序列。如果它们有连续的一段相同的高度那么这段对应的操作就可以合并。合并的数量就是这段相同序列的长度注意高度1本身是终点不消耗操作所以从高度1之后开始算。#include bits/stdc.h using namespace std; typedef long long ll; // 计算一棵竹子从h砍到1的序列包含h和1 vectorll get_seq(ll h) { vectorll seq; seq.push_back(h); while(h 1) { h (ll)sqrtl(h / 2 1); // 使用long double sqrtl保证精度 seq.push_back(h); } // 此时seq是从高到低例如 [初始高度, ..., 2, 1] return seq; } int main() { int n; cin n; vectorll height(n); for(int i 0; i n; i) cin height[i]; vectorvectorll seqs(n); for(int i 0; i n; i) { seqs[i] get_seq(height[i]); } ll total_ops 0; for(int i 0; i n; i) { total_ops seqs[i].size() - 1; // 每棵竹子单独砍需要的操作数序列长度-1 } // 计算相邻竹子可合并的操作数 ll merged_ops 0; for(int i 0; i n - 1; i) { // 比较seqs[i]和seqs[i1]从低到高即从序列尾部开始 int p1 seqs[i].size() - 1; // 指向高度1 int p2 seqs[i1].size() - 1; while(p1 0 p2 0 seqs[i][p1] seqs[i1][p2]) { // 如果高度相同且不是高度1因为高度1是最终状态不消耗操作则可以合并一次操作 // 注意我们合并的是“达到这个高度”的操作。当高度为1时不需要操作。 if(seqs[i][p1] ! 1) { merged_ops; } p1--; p2--; } } ll ans total_ops - merged_ops; cout ans endl; return 0; }重要提示上述代码中的合并计算逻辑是一种简化的理解在严格意义上合并的条件是“相邻竹子在同一轮操作后达到相同高度”。上面的代码是从结果反推认为如果它们变化序列中某个非1的高度相同则达到这个高度的操作可以合并。这对于很多情况是成立的但对于某些特殊情况可能需要更严谨的证明。在竞赛中如果想到这一步并实现通常已经能拿到可观的分数。完全正确的解法需要更精细地模拟操作阶段使用栈或链表来维护当前所有竹子的高度并持续对最高竹子操作直至全部为1同时记录阶段数。这涉及到对“操作可以同时进行”的精确理解。5. 常见失误点与赛场调试技巧根据多年的参赛和教学经验选手们在蓝桥杯赛场上容易在以下几个地方翻车5.1 数据类型与范围溢出这是C组最常见的问题没有之一。int不够用当题目涉及的结果、中间计算值可能超过2e9时必须使用long long。例如两个10^5级别的数相乘就会溢出int。一个简单的习惯是看到10^5级别的输入数据或者可能涉及累加、乘积的直接上long long。数组大小开不够题目说n 100000那么数组大小至少要是100005留一点余量。如果使用vector可以动态调整但也要注意预留空间避免频繁扩容。浮点数精度尽量避免使用float使用double。比较浮点数是否相等时不要用要使用fabs(a-b) 1e-9这样的方式。如果可能尽量用整数运算代替浮点数。5.2 输入输出与格式错误多组输入有些题目可能包含多组测试数据虽然蓝桥杯通常一组但你的代码要能正确处理。使用while(cin n)或while(scanf(“%d”, n) ! EOF)来循环读取。输出格式填空题直接输出数字或字符串不要加任何提示。编程题务必严格按照要求输出包括空格、换行。特别要注意最后一行输出后是否要换行通常需要。调试输出提交前务必删除或注释掉所有用于调试的cout、printf语句。否则会因输出内容不符而判错。5.3 算法复杂度误判暴力搜索超时n 20时O(2^n)的指数级搜索可能可行n 1000时O(n^2)的算法通常安全n 10^5时算法需要O(n log n)或O(n)。一定要先根据数据范围估算最坏情况下的操作次数C一秒大约能进行1e8次简单操作。库函数复杂度要知道常用操作的复杂度。比如vector的erase在中间位置是O(n)的在循环中使用可能导致超时。unordered_map哈希表的查找平均是O(1)但最坏是O(n)。5.4 赛场实用调试技巧静态查错写完代码后先不要运行静下心来从头到尾读一遍。检查变量名是否写错、括号是否匹配、分号是否缺失、if/else逻辑是否正确。小数据测试自己设计几个小的、边界的数据测试。比如输入为0、1、最大值等情况。对拍对于不确定的题目可以写一个绝对正确但可能很慢的暴力程序brute force用随机生成的数据同时运行你的优化程序和暴力程序比较输出是否一致。这是发现逻辑错误的大杀器。输出中间变量在怀疑出错的代码段前后输出关键变量的值观察其变化是否符合预期。使用assert在代码中加入断言例如assert(index 0 index n);可以帮助快速定位数组越界等非法状态。6. 备赛建议与资源推荐如果你想在蓝桥杯或类似的算法竞赛中取得好成绩仅靠刷真题是不够的需要系统性的学习和训练。6.1 系统学习路径巩固C基础熟练掌握STL容器vector,string,map/set,queue/stack/priority_queue的用法和特性。这是竞赛的“武器库”。掌握基础算法枚举与模拟这是基础必须做到快速、准确。排序与查找理解sort、二分查找lower_bound。递归与搜索深度优先搜索DFS、广度优先搜索BFS包括回溯和剪枝技巧。动态规划DP从经典的线性DP背包、LIS、LCS开始理解状态设计和转移方程。贪心算法学会证明或至少能理解贪心策略的正确性。数论与组合数学基础最大公约数gcd、最小公倍数lcm、素数判断、快速幂、简单的排列组合。进阶数据结构并查集、树状数组、线段树、哈希表等根据目标奖项决定学习深度。6.2 有效训练方法专题训练不要盲目刷题。一段时间内集中攻克一个知识点如“本周专攻DFS”在洛谷、AcWing等OJ上找到该专题的题目由易到难进行练习。一题多解对于一道不错的题目尝试用不同的方法解决。例如一道题可能既可以用DFS也可以用BFS甚至可以用DP。比较它们的优劣。写解题报告每做完一道有挑战性的题目强迫自己写一份简单的解题报告记录思路、关键点和易错点。这能极大加深理解。参加虚拟比赛定期在OJ上参加一场时间限制的比赛模拟真实赛场环境锻炼时间管理和心理素质。6.3 资源推荐在线评测平台OJ洛谷国内最友好的OJ之一题目分类清晰题解丰富社区活跃。AcWing有非常系统的算法基础课和进阶课配套的题库和社区质量很高。蓝桥杯官方练习系统直接使用历年真题和模拟题进行练习熟悉比赛环境和题型。书籍《算法竞赛入门经典第2版》刘汝佳俗称“紫书”经典中的经典适合入门和进阶。《算法竞赛进阶指南》李煜东俗称“蓝书”在紫书基础上更深入适合冲击更高奖项。社区与讨论多逛一逛像CSDN、知乎、相关贴吧的算法竞赛板块看看别人的解题思路和总结但切记不要只做“收藏家”动手实践才是关键。最后想说的是算法竞赛的魅力在于思考和解决问题的过程。一道题卡住几个小时最终豁然开朗的瞬间是成长最快的时候。2022年的这套省赛题整体上既有考察基本功的送分题也有需要仔细思考的中等题还有像“砍竹子”这样需要深入分析思维题。希望大家通过这次复盘不仅能得到答案更能学到分析问题、设计算法、编写代码和调试排错这一整套方法论。在平时的练习中多总结多反思你的进步速度会远超你的想象。