蓝桥杯C++ B组省赛真题深度解析：从动态规划到算法优化实战

1. 项目概述：一次算法竞赛的深度复盘

又到了每年备赛蓝桥杯的季节，后台和社群里不少同学开始翻找往年的真题，尤其是想找带详细分析和代码的题解。今天，我就以2022年第十三届蓝桥杯软件类省赛C++ B组的真题为例，带大家做一次深度的复盘。这不仅仅是一份“答案”，我更想分享的是面对这些题目时，一个竞赛老手的思考路径、解题策略以及那些容易踩坑的细节。无论你是正在备赛的选手，还是想通过真题提升自己算法能力的C++开发者，相信这份超过5000字的“实战笔记”都能给你带来不一样的启发。

蓝桥杯发展到今天，其省赛题目已经形成了相对稳定的风格：考察点全面，从基础的语法、模拟题，到中等难度的动态规划、搜索，再到需要一定思维深度的贪心、数论问题都有涉及。B组的题目难度适中，非常适合用来检验自己的编程基础和算法入门水平。复盘一场比赛，价值远大于单纯地AC几道题。我们要搞清楚每道题背后的考点、可能的陷阱、时间复杂度的边界，以及如何写出既正确又优雅的代码。接下来，我们就一道一道地拆解。

2. 试题整体分析与解题策略

2.1 赛题结构与时间分配建议

2022年C++ B组省赛共有8道填空题和4道编程大题。这是蓝桥杯的经典题型配置。填空题通常考察一些巧妙的计算、模拟或者基础的数论/排列组合知识，答案一般是数字或字符串。编程题则要求提交完整的源代码，在线评测系统会根据你的输出结果判分。

面对这样一场比赛，合理的时间分配至关重要。我的建议是：

1. 前1小时：快速浏览所有填空题。目标是找出那些一眼就有思路的“签到题”，比如纯模拟或者简单计算。确保这些题的分数稳稳拿到。对于一时没思路的填空题，不要纠结，做好标记后跳过。
2. 中间2-2.5小时：主攻编程大题。优先解决题干描述清晰、数据范围明确、你熟悉的算法模型（如线性DP、BFS/DFS、简单贪心）的题目。每道题争取一次写对，避免因调试占用过多时间。
3. 最后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可能暗示回溯或状压DP；n <= 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。
• 试题E：X进制减法：数位DP或贪心思维。核心是理解“X进制”每一位的基数不同，且为了使A-B最小，每一位的进制数应尽可能小，但不能小于对应数位上的数字+1（因为进制数要大于数字）。最终结果是每一位的权重累加。
• 试题F~H：通常涉及更复杂的模拟、贪心或初步的DP思想。例如，有一道题关于“统计子矩阵”，需要用到二维前缀和+双指针优化，是编程题的常见前置。

填空题的总结：“暴力枚举”是神器。在比赛时间紧张且数据范围允许的情况下（比如状态数在10^7以内），写一个暴力程序跑出答案，是完全可行的策略。尤其是在本地环境运行，不占评测时间。

4. 编程大题核心解析与代码实现

编程大题是区分度的关键。我们选取两道最具代表性的题目进行深度剖析。

4.1 试题I：李白打酒加强版

问题描述：李白壶中初始有2斗酒。遇店加一倍（酒量乘2），遇花喝一斗（酒量减1）。这一路共遇店N次，遇花M次。已知最后一次遇到的是花，且他正好把酒喝光了。求这一路可能的事件顺序（店和花的排列）有多少种。

解题思路：这是经典的动态规划问题。状态设计是核心。

1. 状态定义：dp[i][j][k]表示遇到i次店、j次花后，壶中酒量为k的方案数。其中0 <= i <= N,0 <= j <= M,0 <= k <= M（因为最多喝M斗酒，酒量不可能超过M）。
2. 状态转移：
   • 当前状态可以由“上一次遇到店”转移而来：如果i > 0且k是偶数（因为遇店翻倍），则dp[i][j][k] += dp[i-1][j][k/2]。
   • 当前状态也可以由“上一次遇到花”转移而来：如果j > 0，则dp[i][j][k] += dp[i][j-1][k+1]（因为遇花喝一斗，所以前一次的酒量要比现在多1斗）。
3. 初始化：dp[0][0][2] = 1，表示初始状态（0店0花）酒量为2有一种方案。
4. 最终答案：dp[N][M][0]，注意题目要求最后一次是花且酒喝完，所以状态是遇到N店、M花后酒量为0。并且，在转移过程中，要保证j < M时，酒量k不能为0（因为最后一次遇到花之前酒就喝完的话，不符合题意）。

注意事项：

• 模运算：答案可能很大，题目通常要求取模（如1000000007）。每次状态转移相加后都要立即取模。
• 边界判断：在转移时，要确保数组下标不越界。特别是从dp[i][j-1][k+1]转移时，要保证k+1 <= 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斗酒的方案数 vector<vector<vector<long long>>> dp(n+1, vector<vector<long long>>(m+1, vector<long long>(m+2, 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[i+1][j][k*2] = (dp[i+1][j][k*2] + val) % MOD; } // 2. 下一次遇到花 if(j < m) { // 关键：如果不是最后一次遇花，则酒量必须大于0才能喝 // 如果是最后一次遇花（j+1 == m），则要求k==1，喝完后为0 // 我们可以统一处理为：只要k > 0，就可以转移。 // 但最终答案我们只取dp[n][m][0]，这个状态只能由dp[n][m-1][1]转移而来，自然满足了最后一次遇花喝完的条件。 if(k > 0) { dp[i][j+1][k-1] = (dp[i][j+1][k-1] + val) % MOD; } } } } } // 最终状态：遇店n次，遇花m次，酒量为0。注意，由于我们的转移保证了遇花时k>0，所以dp[n][m][0]只能由“上一次酒量为1，遇花喝完”转移来。 // 但更严谨的答案应该是 dp[n][m-1][1]，表示在遇到第m次花之前酒量为1，然后最后一次遇花喝完。 // 实际上，我们的dp定义中，dp[i][j][k]是“已遇”i店j花后的状态。所以答案是dp[n][m][0]。 // 验证：当j=m时，不能再遇花了，所以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. 预处理出每棵竹子从初始高度到1的整个“高度变化序列”。例如，竹子i的高度变化为：hi -> a1 -> a2 -> ... -> 1。
2. 从高度1开始向上（逆向）考虑。操作的总次数，可以看作是所有竹子“高度变化序列”合并后，序列中不同“层”的数量。但相邻竹子的相同高度变化可以合并计算。
3. 一种有效的方法是使用优先队列（大根堆）。每次取出当前所有竹子中高度最高的那一棵（假设是第i棵，高度为maxH）进行操作。但这样模拟仍然很慢。
4. 正解是贪心+数学性质分析。经过观察或推导，可以发现函数f(x)下降得非常快。一个很大的数（如10^18）也只需要很少的次数（大概几十次）就能变成1。因此，我们可以对每棵竹子单独计算出其高度变化序列（长度很小）。
5. 然后，我们考虑如何合并操作。想象一个时间轴，从最后一步（高度变为1）向前推。如果两棵相邻的竹子，在某个时刻（或者说，在它们各自的高度变化序列中）拥有相同的高度，那么它们可以在同一次操作中达到这个高度（即，从上一个状态砍下来）。我们的目标是最大化这种“合并”。
6. 实现时，可以用一个栈来辅助。从第一棵竹子开始，依次处理每棵竹子的高度序列（从当前高度向1递减）。在处理第i棵竹子时，将其高度序列与第i-1棵竹子的高度序列进行比较（从低向高比较）。如果遇到相同的高度，则可以合并操作（即这个高度的操作不需要额外计数）。否则，就需要新的操作。

核心难点：在于理解“操作合并”的条件和实现方法。这需要将每棵竹子的砍伐过程看作一个栈（从高到低），然后比较相邻两个栈的公共前缀。

简化版思路与代码框架： 由于严格的正解代码较长，这里给出一个易于理解且能通过大部分测试点的思路：我们分别计算每棵竹子变成1所需的步骤序列。然后，总操作次数 = 所有竹子步骤数之和 - 可以合并的步骤。 如何计算可合并的步骤？对于相邻的两棵竹子i和i+1，从高度1开始向上比较它们的变化序列。如果它们有连续的一段相同的高度，那么这段对应的操作就可以合并。合并的数量就是这段相同序列的长度（注意，高度1本身是终点，不消耗操作，所以从高度1之后开始算）。

#include <bits/stdc++.h> using namespace std; typedef long long ll; // 计算一棵竹子从h砍到1的序列（包含h和1） vector<ll> get_seq(ll h) { vector<ll> 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; vector<ll> height(n); for(int i = 0; i < n; ++i) cin >> height[i]; vector<vector<ll>> 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[i+1]，从低到高（即从序列尾部开始） int p1 = seqs[i].size() - 1; // 指向高度1 int p2 = seqs[i+1].size() - 1; while(p1 >= 0 && p2 >= 0 && seqs[i][p1] == seqs[i+1][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 赛场实用调试技巧

1. 静态查错：写完代码后，先不要运行，静下心来从头到尾读一遍。检查变量名是否写错、括号是否匹配、分号是否缺失、if/else逻辑是否正确。
2. 小数据测试：自己设计几个小的、边界的数据测试。比如输入为0、1、最大值等情况。
3. 对拍：对于不确定的题目，可以写一个绝对正确但可能很慢的暴力程序（brute force），用随机生成的数据同时运行你的优化程序和暴力程序，比较输出是否一致。这是发现逻辑错误的大杀器。
4. 输出中间变量：在怀疑出错的代码段前后，输出关键变量的值，观察其变化是否符合预期。
5. 使用assert：在代码中加入断言，例如assert(index >= 0 && index < n);，可以帮助快速定位数组越界等非法状态。

6. 备赛建议与资源推荐

如果你想在蓝桥杯或类似的算法竞赛中取得好成绩，仅靠刷真题是不够的，需要系统性的学习和训练。

6.1 系统学习路径

1. 巩固C++基础：熟练掌握STL容器（vector,string,map/set,queue/stack/priority_queue）的用法和特性。这是竞赛的“武器库”。
2. 掌握基础算法：
   • 枚举与模拟：这是基础，必须做到快速、准确。
   • 排序与查找：理解sort、二分查找（lower_bound）。
   • 递归与搜索：深度优先搜索（DFS）、广度优先搜索（BFS），包括回溯和剪枝技巧。
   • 动态规划（DP）：从经典的线性DP（背包、LIS、LCS）开始，理解状态设计和转移方程。
   • 贪心算法：学会证明或至少能理解贪心策略的正确性。
   • 数论与组合数学基础：最大公约数（gcd）、最小公倍数（lcm）、素数判断、快速幂、简单的排列组合。
3. 进阶数据结构：并查集、树状数组、线段树、哈希表等，根据目标奖项决定学习深度。

6.2 有效训练方法

• 专题训练：不要盲目刷题。一段时间内集中攻克一个知识点（如“本周专攻DFS”），在洛谷、AcWing等OJ上找到该专题的题目，由易到难进行练习。
• 一题多解：对于一道不错的题目，尝试用不同的方法解决。例如，一道题可能既可以用DFS，也可以用BFS，甚至可以用DP。比较它们的优劣。
• 写解题报告：每做完一道有挑战性的题目，强迫自己写一份简单的解题报告，记录思路、关键点和易错点。这能极大加深理解。
• 参加虚拟比赛：定期在OJ上参加一场时间限制的比赛，模拟真实赛场环境，锻炼时间管理和心理素质。

6.3 资源推荐

• 在线评测平台（OJ）：
  • 洛谷：国内最友好的OJ之一，题目分类清晰，题解丰富，社区活跃。
  • AcWing：有非常系统的算法基础课和进阶课，配套的题库和社区质量很高。
  • 蓝桥杯官方练习系统：直接使用历年真题和模拟题进行练习，熟悉比赛环境和题型。
• 书籍：
  • 《算法竞赛入门经典（第2版）》（刘汝佳）：俗称“紫书”，经典中的经典，适合入门和进阶。
  • 《算法竞赛进阶指南》（李煜东）：俗称“蓝书”，在紫书基础上更深入，适合冲击更高奖项。
• 社区与讨论：多逛一逛像CSDN、知乎、相关贴吧的算法竞赛板块，看看别人的解题思路和总结，但切记不要只做“收藏家”，动手实践才是关键。

最后想说的是，算法竞赛的魅力在于思考和解决问题的过程。一道题卡住几个小时，最终豁然开朗的瞬间，是成长最快的时候。2022年的这套省赛题，整体上既有考察基本功的送分题，也有需要仔细思考的中等题，还有像“砍竹子”这样需要深入分析思维题。希望大家通过这次复盘，不仅能得到答案，更能学到分析问题、设计算法、编写代码和调试排错这一整套方法论。在平时的练习中，多总结，多反思，你的进步速度会远超你的想象。