1. 从一场“国赛”说起为什么2021蓝桥杯CB组值得深挖如果你是一名计算机相关专业的学生或者是一位对算法竞赛感兴趣的开发者那么“蓝桥杯”这个名字你一定不陌生。它早已是国内覆盖面最广、影响力最大的IT类学科竞赛之一。而“国赛”即全国总决赛则是这场赛事金字塔的顶端汇聚了从各省市预赛中脱颖而出的顶尖选手。今天我们不聊宏观的赛事意义也不做泛泛的备考指导我们就聚焦在2021年蓝桥杯国赛C B组这一套具体的真题上。你可能会有疑问都过去几年了一套老题还有什么好分析的这正是我想分享的核心观点一套高质量的竞赛真题其价值远超一场考试本身。它像是一个精心设计的“压力测试场”和“思维训练营”。对于2021年国赛B组这套题我的体会尤为深刻。它没有追求偏、怪、难的“竞赛八股”而是非常扎实地考察了选手在有限时间内对基础算法思想的灵活运用、对问题本质的洞察能力以及代码实现的严谨性。许多题目看似背景简单但陷阱和优化点都藏在细节里非常考验基本功。无论是为了备战未来的比赛还是单纯想提升自己的算法与编程能力静下心来啃透这样一套题收获会比刷十套简单题大得多。接下来的内容我将带你一起重回2021年的赛场。我不会仅仅给出答案而是会拆解每道题背后的核心考点、解题思路的建立过程、代码实现中的关键细节以及我个人在复盘时发现的那些容易“踩坑”的地方。我们的目标不是“知道答案”而是“掌握推导出答案并完美实现的能力”。无论你是正在备赛的选手还是希望检验自己算法水平的开发者相信这篇长文都能给你带来实实在在的帮助。2. 赛题全景与核心考点拆解2021国赛B组究竟考了什么在深入每一道题之前我们有必要先站在高处俯瞰一下这套题的整体面貌。2021年蓝桥杯国赛C B组共有8道题题型覆盖了填空题、编程题考察的知识点既有经典的“模板题”也有需要一定思维发散的“应用题”。根据我的复盘可以将核心考点归纳为以下几个维度2.1 基础算法与数据结构这是竞赛的基石本套题中体现得淋漓尽致。搜索DFS/BFS这是出现频率最高的考点之一用于解决路径、状态、排列组合等问题。题目往往不会直接说“请用DFS”而是需要你从问题描述中抽象出状态模型。动态规划DP另一大核心考点考察对最优子结构和状态转移方程的把握。题目难度从基础的线性DP到需要一定技巧的区间DP或状态压缩DP都有可能。贪心算法在特定条件下寻求局部最优以得到全局最优的策略常与排序结合考察。数论与计算涉及模运算、快速幂、素数判断、最大公约数等基础数论知识是填空题的常客。位运算高效处理状态、集合运算的利器在状态压缩或特定计算中至关重要。2.2 关键思维能力这是区分普通选手和优秀选手的关键。问题建模能力能否将一个具体的、可能带有生活场景描述的问题准确转化为一个抽象的、可用算法解决的数学模型。这是解题的第一步也是最难的一步。边界条件与细节处理能力竞赛题目的“坑”往往就在这里。数据范围int还是long long、数组下标从0开始还是1开始、初始化状态、递归终止条件、浮点数精度比较等任何一个细节疏忽都可能导致丢分。时间复杂度分析能力在动手写代码前必须估算算法在最坏情况下的运行时间确保不会超时TLE。这要求对数据范围和算法复杂度有清晰的认知。2.3 2021年B组特色相较于往年或其他组别我认为这套题有两个突出特点强调思维而非记忆直接套用“板子”模板代码就能解决的题目变少了更多题目需要你在理解经典算法思想的基础上进行适配和修改。对代码实现质量要求更高题目设计上可能有多条路径可以通向答案但其中只有兼顾了正确性和效率的实现才能拿到满分。这促使选手去思考更优的解法。了解了这些我们再具体到题目上时就能有的放矢不仅关注“怎么做”更思考“为什么这么做”以及“怎么做得更好”。3. 典型赛题深度剖析思路、实现与避坑指南接下来我们选择几道具有代表性的题目进行深度剖析。我会按照“题意解析 - 思路建立 - 代码实现 - 避坑要点”的流程来讲解。3.1 填空题质数行者题意简述在一个三维网格空间大小为n*m*p中起点(1,1,1)终点(n,m,p)。每一步只能沿x、y、z轴正方向移动一个单位长度。但是空间中存在一些“质数点”其三维坐标值都是质数不能经过。求从起点到终点的不同路径总数。结果可能很大需要对10^97取模。思路建立过程问题转化这是一个典型的“带障碍物的网格路径计数”问题只不过从常见的二维升级到了三维障碍物是“质数点”。算法选择由于只能向右、下、前移动无后效性很自然想到用动态规划DP。定义dp[i][j][k]表示从起点走到点(i, j, k)的路径数。状态转移对于非障碍点(i, j, k)其路径数等于从三个方向过来的路径数之和dp[i][j][k] dp[i-1][j][k] dp[i][j-1][k] dp[i][j][k-1]。注意边界处理i, j, k 为1时。障碍处理初始化所有“质数点”的dp值为0并且在状态转移时如果当前点是障碍则直接跳过保持为0也不作为其他点的来源。质数判断需要预处理判断坐标值是否为质数。注意数据范围坐标值最大为500因为n,m,p500可以用简单的埃氏筛或欧拉筛预处理1~500以内的质数表实现O(1)判断。关键代码实现与注释#include bits/stdc.h using namespace std; typedef long long ll; const int MOD 1e9 7; const int MAX 505; // 坐标最大值 bool isPrime[MAX]; ll dp[MAX][MAX][MAX]; // 埃氏筛法预处理质数表 void initPrime() { memset(isPrime, true, sizeof(isPrime)); isPrime[0] isPrime[1] false; // 0和1不是质数 for (int i 2; i MAX; i) { if (isPrime[i]) { for (int j i * i; j MAX; j i) { isPrime[j] false; } } } } int main() { initPrime(); int n, m, p; cin n m p; // 初始化DP数组 memset(dp, 0, sizeof(dp)); dp[1][1][1] 1; // 起点 for (int i 1; i n; i) { for (int j 1; j m; j) { for (int k 1; k p; k) { // 如果是起点跳过已初始化 if (i 1 j 1 k 1) continue; // 如果当前点是质数点障碍则路径数为0 if (isPrime[i] isPrime[j] isPrime[k]) { dp[i][j][k] 0; continue; } // 状态转移注意取模 ll ways 0; if (i 1) ways (ways dp[i-1][j][k]) % MOD; if (j 1) ways (ways dp[i][j-1][k]) % MOD; if (k 1) ways (ways dp[i][j][k-1]) % MOD; dp[i][j][k] ways; } } } cout dp[n][m][p] endl; return 0; }避坑要点与心得坑点1质数判断的边界。题目要求“坐标值都是质数”注意是且的关系。同时质数定义不包括0和1预处理筛法时务必将其设为false。坑点2取模运算。结果很大每次加法后都要取模防止溢出。dp数组和中间变量ways最好使用long long类型。坑点3起点处理。起点(1,1,1)的dp值初始化为1。在三重循环中需要跳过起点否则会错误地从“不存在的”前驱状态转移过来。心得这道题是三维DP的入门级应用难点在于准确理解状态定义和处理好障碍物。在竞赛中这类题目属于“必须拿下”的基础题考察的是选手的细心和模板熟悉度。3.2 编程题异或三角题意简述给定T组询问每组询问给出一个正整数n。要求找出所有满足条件的三元组(a, b, c)其中1 a, b, c n且满足a ^ b ^ c 0^表示按位异或a b c,a c b,b c a构成三角形的边长条件求满足条件的三元组数量。T 10^5,n 10^18。结果对10^97取模。思路建立过程 这道题的n的范围巨大10^18直接三重循环枚举a, b, c显然不可能时间复杂度O(n^3)。必须寻找数学规律或利用位运算性质进行优化。从异或条件入手a ^ b ^ c 0等价于c a ^ b。因为异或运算满足自反性a ^ b ^ c 0 a ^ b c。这样我们就将三个变量减少为两个独立变量a和bc由它们决定。代入三角形条件条件变为a b (a ^ b)a (a ^ b) b- 化简为a b ^ (a ^ b)? 不这样更复杂。更好的方法是利用对称性。由于a, b, c在条件中是对称的我们只需保证a b c 并且a b c通过排序避免重复计数然后乘以排列数6a,b,c的全排列。但注意当a,b,c有相等时排列数会减少。关键观察对于任意两个正整数a和ba b与a ^ b有什么关系考虑二进制位。ab可以看作是不带进位的加法(a^b)加上所有进位的结果。进位发生在二进制位同为1的时候。因此a b (a ^ b) 2 * (a b)。其中(a b)是进位信息左移一位乘以2。转化不等式将a b a ^ b代入上式(a ^ b) 2*(a b) (a ^ b)2*(a b) 0(a b) 0。这意味着a和b的二进制表示至少有一位同时为1。另外两个三角形条件由于我们令c a ^ b且(a b) 0可以推导出a c b和b c a在a, b, c为正整数且满足前两个条件下几乎总是成立但需要严格验证边界情况如ab。一个更严谨的方法是三角形条件等价于a, b, c中任意两个之和大于第三个数。结合c a ^ b和(a b) 0可以证明只要a ! b通常都成立。当a b时c a ^ a 0不满足c为正整数的条件所以a ! b。问题简化现在问题简化为统计有多少对正整数(a, b)满足1 a, b n且(a b) 0并且a ! b。注意c a ^ b会自动满足1 c n吗不一定需要额外检查。但根据a, b n和异或性质c可能大于n。所以我们需要在计数时确保a ^ b n。数位DP登场由于n高达10^18我们需要按二进制位来统计。这正是指数级复杂度算法如暴力枚举的克星——数位DP。我们可以设计一个DP状态逐位确定a和b的二进制位同时记录是否已经满足了(a b) 0这个条件以及当前a, b, c是否已经小于等于n数位DP的常规限制。核心数位DP状态设计 定义dp[pos][limitA][limitB][limitC][hasAnd]pos: 当前正在处理从高到低的第pos位二进制位。limitA,limitB,limitC: 布尔值表示当前a, b, c的前pos位是否已经严格小于n的前pos位0表示已小于后续位可任意填1表示等于后续位不能超过n的对应位。hasAnd: 布尔值表示到目前为止a和b的二进制位是否已经出现过同为1的情况即(ab)0是否已满足。然后从最高位向最低位进行记忆化搜索DFS枚举当前位a和b的取值0或1根据c a ^ b计算出c的当前位。同时更新limit和hasAnd状态。最终在最低位pos-1时如果hasAnd为真则说明找到一组有效的(a,b)返回1。关键代码框架#include bits/stdc.h using namespace std; typedef long long ll; const int MOD 1e9 7; ll n; ll dp[70][2][2][2][2]; // pos, lima, limb, limc, hasAnd vectorint bits; // 存储n的二进制位 ll dfs(int pos, bool lima, bool limb, bool limc, bool hasAnd) { if (pos 0) { // 递归终点成功构造到底并且满足(ab)0 return hasAnd ? 1 : 0; } if (dp[pos][lima][limb][limc][hasAnd] ! -1) { return dp[pos][lima][limb][limc][hasAnd]; } int upA lima ? bits[pos] : 1; int upB limb ? bits[pos] : 1; // 注意c的位由a^b决定但其上限受limc和bits[pos]约束 ll res 0; for (int aBit 0; aBit upA; aBit) { for (int bBit 0; bBit upB; bBit) { int cBit aBit ^ bBit; // 检查cBit是否超过限制 if (limc cBit bits[pos]) continue; bool newLima lima (aBit upA); bool newLimb limb (bBit upB); bool newLimc limc (cBit bits[pos]); bool newHasAnd hasAnd || (aBit 1 bBit 1); res (res dfs(pos-1, newLima, newLimb, newLimc, newHasAnd)) % MOD; } } return dp[pos][lima][limb][limc][hasAnd] res; } ll solve(ll x) { if (x 0) return 0; bits.clear(); while (x) { bits.push_back(x 1); x 1; } memset(dp, -1, sizeof(dp)); // 从最高位开始初始状态所有数都等于上限limtrue return dfs(bits.size()-1, true, true, true, false); } int main() { int T; cin T; while (T--) { cin n; // 注意我们统计的是有序对(a,b)使得 a,b,cn, (ab)0。 // 但题目要求的是三元组(a,b,c)。由于我们固定了ca^b且a,b,c互异时对应6种排列有相等时对应3种或1种。 // 更严谨的做法是在数位DP中直接统计满足条件的三元组数量需要考虑a,b,c的大小关系以避免重复。 // 这里为了简化先给出利用数位DP计算满足(ab)0且a,b,cn的对(a,b)数量的思路。 // 完整的去重计算较为复杂需要另一个维度的状态来记录a,b,c的大小关系。 cout 需要在此处调用并整合solve函数的结果并处理排列组合 endl; } return 0; }避坑要点与心得坑点1对异或和三角形条件的数学转化。这是本题最大的思维难点。如果不能推导出(a b) 0这个关键条件题目将无从下手。这需要选手对位运算的性质有深刻的理解。坑点2数位DP的状态设计。状态需要包含对a, b, c三个数的上限限制以及hasAnd标志。状态维度较高容易遗漏或设计错误。坑点3去重处理。上述DP计算的是有序对(a, b)的数量。而题目要求的是无序三元组{a, b, c}。当a, b, c互不相等时一个三元组对应6个不同的有序对(a,b)因为c由a,b决定。当其中有数字相等时情况更复杂。必须在DP状态中增加维度来记录a, b, c之间的大小关系或者在DP后通过组合数学公式进行去重计算。这是本题实现上最繁琐的部分。心得这道题是典型的“思维难度高实现细节多”的竞赛压轴题。它完美地结合了位运算、数学推导、数位DP和组合计数。即使无法在赛时完全解出理解其解题思路也是一次极佳的思维训练。它告诉我们面对大数据范围一定要放弃暴力枚举的想法转而寻找数学规律或利用位运算、数位DP等工具进行降维打击。4. 通用备赛策略与赛场实战技巧通过对具体题目的剖析我们看到了竞赛题目对思维和细节的苛刻要求。那么在日常备赛和实际比赛中有哪些普适的策略和技巧呢结合我带学生和自身参赛的经验分享以下几点4.1 备赛阶段构建你的“算法武器库”分模块系统学习不要盲目刷题。将算法分为“数据结构”、“搜索”、“动态规划”、“图论”、“数论”、“字符串”等模块每个模块选择一本经典教材如《算法竞赛入门经典》、《算法导论》特定章节或一个高质量的专题网课进行系统学习。理解算法思想、适用场景和时间复杂度是根本。精刷经典题每个算法模块找10-20道经典题目如洛谷、力扣上的模板题或经典问题进行精刷。精刷意味着独立思考并尝试解决 - 对比题解学习最优思路 - 独立复现代码 - 总结该题考察点和易错点 - 尝试一题多解。建立错题本/代码模板库将刷题过程中遇到的典型错题、巧妙思路、自己写的清晰可靠的代码模板如快速幂、并查集、Dijkstra堆优化整理成电子文档。定期回顾考前重点复习。进行模拟赛训练每周安排一次完整的4小时模拟赛可以用往年真题。严格计时模拟真实赛场环境。赛后不仅要订正错题更要复盘时间分配是否合理哪道题卡太久有没有因为低级错误如没开long long丢分这是提升应试能力的关键。4.2 赛场实战有限时间内的最优决策通读全卷快速分类拿到题目后花5-10分钟快速浏览所有题目对每道题的难度、题型、可能涉及的算法做一个初步判断。按照“一眼题”、“可做题”、“难题”进行分类。制定答题策略通常采用“先易后难”的策略。优先解决“一眼题”和“可做题”确保拿到基础分。切忌在“难题”上钻牛角尖浪费大量时间导致简单题没时间做。编程题的“四步法”彻底理解题意仔细阅读输入输出格式、数据范围、特殊限制。最好用笔在纸上划出关键信息。设计算法与验证在草稿纸上设计算法并用手工或简单样例验证逻辑是否正确。务必估算时间复杂度确保不会超时。编码与静态检查编写代码保持清晰的结构和适当的注释。写完后先不要急于运行而是静态检查一遍变量初始化了吗数组大小够吗边界条件处理了吗int会不会溢出测试与调试用题目给的样例测试然后设计一些边界数据如最小输入、最大输入、答案为0的情况进行测试。如果出错使用cout输出中间变量或利用调试工具定位问题。填空题的特殊技巧填空题通常不需要写完整程序可以手算、编写小程序暴力枚举如果范围允许、或者利用数学工具如Excel、Python脚本辅助计算。务必确认结果格式如单位、小数点后几位、是否取模。4.3 代码实现中的“防坑” checklist在竞赛中很多错误不是算法想不到而是代码写不对。提交前在心里快速过一遍这个清单[ ]数据范围int还是long long数组大小是否足够通常开n10[ ]多组数据输入是否清空了全局变量、容器[ ]初始化dp数组、vis数组、累加和等是否在正确的位置初始化了[ ]边界条件循环的起止点对吗递归的终止条件完备吗[ ]取模操作加法、乘法后是否及时取模负数取模是否做了处理[ ]浮点数比较是否使用了eps如1e-8来避免精度误差[ ]输入输出cin/cout是否在数据量大时关闭了同步流ios::sync_with_stdio(false)或改用scanf/printf5. 从2021年真题看蓝桥杯命题趋势与深度准备建议分析完一套真题我们不妨跳出来看看它反映了怎样的命题趋势以及我们该如何进行更有深度的准备。5.1 命题趋势分析以2021年国赛B组为例结合近年其他赛题我认为蓝桥杯的命题呈现出以下特点基础与思维并重像“质数行者”这样的三维DP考察的是对基础模型的理解和迁移能力。而“异或三角”则完全是在考察思维发散和数学转化能力。这说明比赛既要求选手有扎实的“基本功”又要求具备解决新问题的“创造力”。对位运算和数论的考察增多位运算异或、与、或、移位因其高效和巧妙越来越多地出现在赛题中用于状态表示、优化计算或作为问题的核心条件。数论也不再局限于gcd、lcm开始涉及模逆元、组合数取模、原根等进阶知识。数据结构考察更灵活不再单纯考察如何调用STL的queue或stack而是考察你能否利用基本数据结构数组、链表的思想来解决复杂问题或者将多种数据结构如并查集线段树结合使用。题目背景生活化、趣味化“质数行者”、“异或三角”这些题目名称和描述都试图从一个有趣的角度切入降低心理门槛但内核依然是严谨的算法问题。5.2 深度准备建议针对这些趋势备赛不能只停留在刷题层面。吃透经典算法思想而非死记模板重点理解动态规划的“状态”与“转移”概念搜索的“状态空间”与“剪枝”策略贪心的“局部最优”证明思路。做到给你一个新问题你能判断它可能属于哪类问题并尝试套用或修改已知的思想。加强数学素养特别是离散数学、初等数论和组合数学。学习二进制、位运算的常用技巧如lowbit运算、枚举子集。理解模运算的法则。这些知识能帮你更快地看透题目本质。进行专题强化与融合训练在基础模块学习完后要进行跨专题的训练。例如“DP状态压缩”、“图论二分答案”、“数据结构离线查询”等。找一些综合性强、代码量稍大的题目进行练习提升工程实现能力。复盘与讲题尝试把自己学会的题目讲给别人听或者写下详细的解题报告。在“讲”和“写”的过程中你会发现自己理解上的模糊点从而加深印象。这也是我撰写这篇长文的初衷之一。最后我想说竞赛的意义绝不仅仅是奖牌。通过准备蓝桥杯这样一场比赛你所锻炼出的系统性学习能力、在压力下分析解决问题的能力、以及写出高效严谨代码的习惯将会在你未来的学习、科研和职业发展中持续产生价值。希望这篇对2021年国赛B组真题的深度剖析能成为你算法学习之路上一块有用的垫脚石。当你觉得某道题特别难时别灰心把它拆解、吃透你就又向上迈进了一步。