1. 项目概述一次对经典赛题的深度复盘最近在整理过去的备赛资料翻到了2019年蓝桥杯国赛C/C B组的真题。作为国内计算机类学生中颇具影响力的赛事蓝桥杯的国赛题目往往能集中体现对算法设计、编程思维和工程实践能力的综合考察。2019年的这套题即便放在今天来看其设计思路和考察点依然具有很强的代表性和学习价值。它不是单纯考你会不会某个语法而是看你如何运用C/C这门工具去高效、优雅地解决实际问题。这篇文章我想从一个过来人的视角和大家一起重新拆解这套真题中的部分典型题目。我的目的不是简单地给出答案而是重点分析题目背后的核心考点、解题思路的构建过程以及在实际编码中容易踩到的“坑”。无论是正在备赛的同学还是希望提升自己算法与编程能力的开发者相信都能从中获得一些启发。我们会看到有些题目需要巧妙的数学思维转化有些则是对基础数据结构和算法的扎实运用还有一些则考验着我们在时间与空间之间的权衡能力。2. 解题核心思路与策略总览面对一套竞赛题尤其是国赛级别的题目直接埋头编码往往是效率最低的。一套有效的解题策略应该始于对题目的整体感知和思路规划。2.1 题目类型分析与时间分配2019年国赛B组的题目通常包含结果填空、代码填空和编程大题等多种形式。对于结果填空题关键在于理解题意寻找规律或建立数学模型有时甚至需要手写程序辅助计算但最终提交的是一个确定的结果。这类题目标准答案唯一要求绝对精确。代码填空题则聚焦于某个关键算法片段的实现考察对经典算法如DFS、BFS、动态规划、贪心等模板的熟悉程度以及上下文逻辑的衔接能力。编程大题是综合能力的试金石。我的策略是先通读所有题目根据自己对题目类型的熟悉程度和直观判断的难度进行初步分级。优先解决思路最清晰、最有把握的题目确保基础分到手。对于一时没有头绪的难题不要长时间纠缠可以先做标记在完成其他题目后再回头利用剩余时间进行攻坚。国赛环境紧张合理的时间分配比死磕一道题更重要。2.2 审题与建模的关键步骤审题是解题的第一步也是最容易出错的一步。我习惯用笔划出题目中的关键约束条件、输入输出格式以及问题描述中的核心动词。例如“求最大值”和“求方案数”就是两类完全不同的问题前者可能用贪心或动态规划后者则可能涉及深度搜索或组合数学。建模是将自然语言描述的问题转化为计算机可处理的形式化问题的过程。对于算法题建模通常意味着定义状态明确我们要计算什么是某个位置的最优值还是某个集合的属性确定状态转移方程当前状态如何由已知的通常是更小的状态推导而来这是动态规划的核心。确定边界条件最小规模的问题初始状态的解是什么选择数据结构用什么来存储状态、中间结果或图/树的结构数组、向量、集合、映射还是自定义结构体一个清晰的模型是正确编码的基础。在接下来的具体题目解析中我们将反复运用这一思考过程。3. 典型真题深度解析与思路实现这里我选取两道当年我认为很有代表性的编程大题进行拆解一道偏重数学思维和规律寻找另一道则侧重于经典算法的应用与优化。3.1 例题A平方拆分问题抽象与枚举优化题目回忆将某个整数拆分成若干个互不相同的正整数的平方和求具体的拆分方案数或方案本身具体表述需回忆此处以典型变体为例进行方法论讲解。例如考察对于数字N有多少种拆分方式。核心考点深度优先搜索、剪枝优化、去重处理。思路拆解问题转化这不是简单的整数划分而是“子集和”问题的一个变体从1², 2², 3², ... , k² (其中 k² ≤ N) 这个集合中选取若干个互不相同的数使得它们的和等于N。算法选择由于每个平方数只能选或不选且顺序无关求组合而非排列自然想到用深度优先搜索来枚举所有可能的子集。建模状态当前搜索到第几个平方数idx当前已选取的平方数和sum当前已选取的平方数列表path。动作对于平方数nums[idx]有两种选择选或不选。目标sum N且path中的元素互不相同由于我们按顺序枚举自然保证不重复选取同一个数但需注意题目要求的正整数互不相同已由nums数组本身保证。关键优化——剪枝这是竞赛题的关键。如果不加优化枚举量会指数级爆炸。可行性剪枝如果sum nums[idx] N那么选择当前数必然导致和超过N这条分支可以剪掉。最优性剪枝本题是计数但思想类似如果当前和sum加上剩余所有可能的平方数从idx到最后一个的最大和仍然小于N那么即使后面全选也达不到N这条分支也可以剪掉。这需要预处理一个后缀和数组suffix_sum[i]表示从i开始的平方数之和。代码框架示意#include iostream #include vector #include cmath using namespace std; int N; vectorint squares; // 存储所有 ≤ N 的平方数 vectorint suffix_sum; // 后缀和用于剪枝 int count 0; // 方案数 vectorint current_path; // 当前路径 void dfs(int idx, int current_sum) { // 找到一个合法方案 if (current_sum N) { count; // 如果需要输出方案可以在这里打印 current_path return; } // 边界条件所有数都考虑完了或者下标越界 if (idx squares.size() || current_sum N) { return; } // 剪枝1: 即使加上当前数也超了后面的数更大更没希望直接返回 if (current_sum squares[idx] N) { // 实际上由于squares递增这里剪枝后连“不选”的分支也不必再深入 // 不 “不选”的分支可能还有希望靠后面的数组合。所以这里不能直接return。 // 正确的可行性剪枝在“选择”分支之前做判断。 } // 剪枝2: 当前和 剩余所有数的最大和 N 直接返回 if (current_sum suffix_sum[idx] N) { return; } // 分支1: 选择当前平方数 if (current_sum squares[idx] N) { // 选择前的可行性剪枝 current_path.push_back(squares[idx]); dfs(idx 1, current_sum squares[idx]); current_path.pop_back(); // 回溯 } // 分支2: 不选择当前平方数 dfs(idx 1, current_sum); } int main() { cin N; // 预处理平方数数组 for (int i 1; i * i N; i) { squares.push_back(i * i); } // 预处理后缀和数组从后往前计算 int m squares.size(); suffix_sum.resize(m, 0); suffix_sum[m-1] squares[m-1]; for (int i m-2; i 0; --i) { suffix_sum[i] suffix_sum[i 1] squares[i]; } dfs(0, 0); cout count endl; return 0; }实操心得剪枝的艺术DFS的威力很大程度上取决于剪枝的效率。suffix_sum剪枝是一种非常有效的“前缀和/后缀和”思想的应用它能提前判断整条分支的最终潜力避免大量无谓的搜索。回溯的细节在递归调用前后对current_path的push_back和pop_back必须成对出现这是回溯算法的标准写法务必熟练。去重本题因“互不相同”且我们按顺序枚举所以不会产生重复集合如{1,4}和{4,1}。如果题目允许重复元素或要求列出所有排列则去重会复杂得多可能需要使用排序跳过相同元素或使用集合来去重。3.2 例题B最优路径问题图论与动态规划结合题目回忆在一个带权有向图中寻找从起点到终点的一条路径该路径满足某些特定约束如经过特定点、边权之和最小但某些代价最大等求该路径的权重或路径本身。核心考点图的最短路径算法变体、状态压缩动态规划。思路拆解 假设一个具体化题目给定一个N个节点编号1~N、M条边的有向图边有权重。现在要从节点1走到节点N但必须至少经过K个指定的“关键节点”K通常较小比如≤10。求满足该条件的最短路径长度。问题分析这是一个典型的最短路径问题但附加了“必须经过特定点集”的约束。经典的Dijkstra或Floyd算法无法直接处理这种“带必经点”的约束。算法选择由于K很小这是一个强烈的提示——可以使用状态压缩动态规划。建模状态定义dp[u][state]表示当前走到节点u并且已经经过的关键点集合为state用一个整数的二进制位表示1表示已经过0表示未经过时的最短路径长度。状态转移对于状态dp[u][state]我们可以考虑从u走到它的邻居v。如果v是一个关键节点其编号为id[v]映射到0到K-1那么新的状态new_state state | (1 id[v])。转移方程为dp[v][new_state] min(dp[v][new_state], dp[u][state] weight(u, v))初始化dp[start][0] 0其他状态为无穷大。如果起点是关键节点则初始状态应为(1 id[start])。目标dp[end][final_state]其中final_state是所有关键点都至少经过一次的状态即(1 K) - 1。但注意题目是“至少经过”所以最终答案是所有state满足包含所有关键点即(state final_mask) final_mask的dp[end][state]中的最小值。实现方式这实际上是一个在“状态图”节点是(u, state)对上的最短路径问题。我们可以使用优先队列优化的Dijkstra算法即堆优化Dijkstra来求解。队列中的元素是(distance, u, state)。代码框架示意#include iostream #include vector #include queue #include cstring #include climits using namespace std; struct Edge { int to, weight; Edge(int t, int w) : to(t), weight(w) {} }; struct Node { int dist, u, state; // 小顶堆 bool operator(const Node other) const { return dist other.dist; } }; int main() { int N, M, K; cin N M K; vectorint key_nodes(K); vectorint is_key(N1, -1); // 映射节点编号 - 关键点索引(0~K-1)-1表示不是关键点 for (int i 0; i K; i) { cin key_nodes[i]; is_key[key_nodes[i]] i; } vectorvectorEdge graph(N1); for (int i 0; i M; i) { int u, v, w; cin u v w; graph[u].emplace_back(v, w); // 如果是有向图则只加一条边 } int start 1, end N; int state_size 1 K; // 状态总数 vectorvectorint dp(N1, vectorint(state_size, INT_MAX)); priority_queueNode, vectorNode, greaterNode pq; int init_state 0; if (is_key[start] ! -1) { init_state | (1 is_key[start]); } dp[start][init_state] 0; pq.push({0, start, init_state}); int final_mask (1 K) - 1; // 所有关键点都经过的掩码 int ans INT_MAX; while (!pq.empty()) { Node cur pq.top(); pq.pop(); int d cur.dist, u cur.u, s cur.state; if (d dp[u][s]) continue; // outdated entry, skip // 如果到达终点且状态包含了所有关键点更新答案 if (u end ((s final_mask) final_mask)) { ans min(ans, d); // 注意不能直接break因为可能还有其他更优路径在其他状态下到达终点 } for (const Edge e : graph[u]) { int v e.to, w e.weight; int next_state s; if (is_key[v] ! -1) { next_state | (1 is_key[v]); } if (dp[v][next_state] d w) { dp[v][next_state] d w; pq.push({dp[v][next_state], v, next_state}); } } } if (ans INT_MAX) { cout -1 endl; // 无解 } else { cout ans endl; } return 0; }实操心得状态设计是灵魂dp[u][state]这种“节点状态”的二维设计是解决此类“带约束的最短路径”问题的经典套路。关键在于识别出那个可以压缩的、规模较小的维度这里是关键点集合K。Dijkstra的适用性因为边权非负我们可以使用Dijkstra。如果边权有负则需要考虑SPFA或针对状态压缩DP的Bellman-Ford变体但竞赛中通常保证非负。内存与时间复杂度状态数是N * 2^K当N100K10时状态数约为100*102410万级别是可接受的。如果K再大此方法将不可行。答案的获取最终答案不一定在dp[end][final_mask]因为题目是“至少经过”可能以其他包含所有关键点的状态到达终点更短。所以需要遍历所有包含final_mask的状态取最小值。4. 通用技巧与常见“坑点”实录除了具体题目的解法在蓝桥杯乃至各类算法竞赛中有一些通用的技巧和几乎每次都会有人踩的“坑点”。4.1 输入输出与性能优化关闭同步流在C中cin/cout默认与C的stdio同步这会带来额外的开销。在需要大量读入输出的题目前使用ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);可以显著提升IO速度。注意一旦关闭同步就不要混用cin/cout和scanf/printf。使用\\n代替endlendl会刷新输出缓冲区导致频繁的IO操作降低效率。在竞赛中除非确需立即输出否则一律使用‘\\n‘。预估数据规模与复杂度这是选择算法的根本依据。如果N≤20可能是指数级算法如状压DP、全排列N≤1000O(N²)的算法可能可行N≤10^5通常需要O(NlogN)或O(N)的算法。在编码前务必进行大致的复杂度估算。4.2 数据类型与范围陷阱整数溢出这是最常见的错误之一。当题目涉及乘法、累加或者结果可能很大时第一时间要问自己会不会超过int的范围int通常是32位最大值约21亿2.1e9。如果可能超过果断使用long long64位。例如求N个数的和即使每个数都是int和也可能超出int范围。浮点数精度尽量避免直接比较两个浮点数是否相等a b。应该判断它们的绝对值差是否小于一个很小的数如1e-9。fabs(a - b) 1e-9。在涉及几何或者需要高精度计算的题目中有时可以尝试通过缩放将浮点数运算转化为整数运算来避免精度问题。数组大小全局数组开在静态存储区局部数组开在栈上。栈空间有限通常几MB开太大的局部数组会导致运行时错误如段错误。如果需要一个很大的数组比如上百万元素应该定义为全局变量或者使用vector动态分配在堆上。4.3 调试与测试策略构造边界测试用例自己测试时不要只用一个例子。要专门测试最小输入N0或1的情况。最大输入题目允许的最大N检查程序是否超时或内存溢出。特殊值例如在图论中测试只有一个节点、没有边的情况在搜索中测试无解的情况。使用assert在代码关键位置使用assert语句需要#include cassert可以帮助在调试阶段快速定位逻辑错误。例如在访问数组前assert(index 0 index n);。输出中间变量当程序结果不对时不要只盯着最终输出。在关键循环或递归函数中打印出重要的中间变量如状态值、循环索引、临时计算结果对比你的预期和实际输出这是定位bug最直接的方法。4.4 记忆化搜索与动态规划的抉择很多问题既可以用记忆化搜索Memoization DFS也可以用递推形式的动态规划DP来解决。记忆化搜索思路更直观直接从“原问题”出发递归地分解为子问题并用一个缓存如数组或哈希表存储已计算过的子问题结果避免重复计算。优点是符合人的自然思维代码容易写对。缺点是递归有栈开销对于深度很大的问题可能栈溢出且常数开销可能比递推略大。递推DP需要更清晰地定义状态转移的顺序通常从基础状态边界开始逐步递推到目标状态。优点是运行效率通常更高没有递归开销。缺点是需要仔细思考递推顺序有时不如记忆化搜索直观。个人建议对于初学者如果对状态转移关系不是百分之百确信优先使用记忆化搜索。它更容易实现且不易出错。当记忆化搜索写出来并AC后如果你有兴趣可以再尝试将其转化为递推DP作为一种练习。5. 备赛建议与资源利用基于对历年真题的分析给正在准备蓝桥杯或类似竞赛的同学几点建议夯实基础竞赛不是炫技扎实的基础是关键。确保对C/C标准库STL的常用容器vector,string,map,set,queue,stack,priority_queue和算法sort,lower_bound等了如指掌。对基础数据结构数组、链表、栈、队列、二叉树和算法排序、二分查找、递归、分治的理解要透彻。专题突破算法学习要成体系。分专题进行练习例如线性结构前缀和、差分、双指针、滑动窗口。搜索DFS、BFS及其剪枝技巧记忆化搜索。动态规划线性DP、区间DP、树形DP、状态压缩DP、数位DP。重点理解“状态定义”和“转移方程”。图论最短路Dijkstra, Floyd, SPFA、最小生成树Prim, Kruskal、拓扑排序。数学简单数论质数筛、最大公约数、快速幂、组合数学、简单计算几何。真题精练历年真题是最好的学习材料。不要满足于“看过”或“知道思路”。一定要动手编码并在OJ在线判题系统上提交直到ACAccepted。然后尝试思考是否有更优的解法代码能否更简洁边界条件处理是否完美模拟实战在备赛后期要严格按照比赛时间进行全真模拟。使用历年的真题套题在4小时内完成。这能有效训练时间分配、压力下的调试能力和策略选择。善用资源官方练习系统蓝桥杯官网的练习系统是首要资源。开源OJ如洛谷、力扣LeetCode尤其其“竞赛”和“学习”板块、AcWing、Codeforces等上面有海量的题目和活跃的社区。经典书籍《算法竞赛入门经典》刘汝佳、《算法竞赛进阶指南》李煜东都是很好的系统性学习资料。回过头看2019年的这些题目它们考察的与其说是某种奇技淫巧不如说是一种系统化的计算思维和严谨的工程实现能力。从审题建模到算法选择再到编码调试每一步都环环相扣。一道题目的价值往往不在于你当时是否把它做出来而在于事后复盘时你是否能清晰地复现整个思考链路并从中提炼出可迁移的方法。希望这次的解析能帮你打通一些关节在下次遇到似曾相识的问题时能更快地抓住本质。 蓝桥杯国赛真题深度解析：从DFS剪枝到状态压缩DP的算法实战
1. 项目概述一次对经典赛题的深度复盘最近在整理过去的备赛资料翻到了2019年蓝桥杯国赛C/C B组的真题。作为国内计算机类学生中颇具影响力的赛事蓝桥杯的国赛题目往往能集中体现对算法设计、编程思维和工程实践能力的综合考察。2019年的这套题即便放在今天来看其设计思路和考察点依然具有很强的代表性和学习价值。它不是单纯考你会不会某个语法而是看你如何运用C/C这门工具去高效、优雅地解决实际问题。这篇文章我想从一个过来人的视角和大家一起重新拆解这套真题中的部分典型题目。我的目的不是简单地给出答案而是重点分析题目背后的核心考点、解题思路的构建过程以及在实际编码中容易踩到的“坑”。无论是正在备赛的同学还是希望提升自己算法与编程能力的开发者相信都能从中获得一些启发。我们会看到有些题目需要巧妙的数学思维转化有些则是对基础数据结构和算法的扎实运用还有一些则考验着我们在时间与空间之间的权衡能力。2. 解题核心思路与策略总览面对一套竞赛题尤其是国赛级别的题目直接埋头编码往往是效率最低的。一套有效的解题策略应该始于对题目的整体感知和思路规划。2.1 题目类型分析与时间分配2019年国赛B组的题目通常包含结果填空、代码填空和编程大题等多种形式。对于结果填空题关键在于理解题意寻找规律或建立数学模型有时甚至需要手写程序辅助计算但最终提交的是一个确定的结果。这类题目标准答案唯一要求绝对精确。代码填空题则聚焦于某个关键算法片段的实现考察对经典算法如DFS、BFS、动态规划、贪心等模板的熟悉程度以及上下文逻辑的衔接能力。编程大题是综合能力的试金石。我的策略是先通读所有题目根据自己对题目类型的熟悉程度和直观判断的难度进行初步分级。优先解决思路最清晰、最有把握的题目确保基础分到手。对于一时没有头绪的难题不要长时间纠缠可以先做标记在完成其他题目后再回头利用剩余时间进行攻坚。国赛环境紧张合理的时间分配比死磕一道题更重要。2.2 审题与建模的关键步骤审题是解题的第一步也是最容易出错的一步。我习惯用笔划出题目中的关键约束条件、输入输出格式以及问题描述中的核心动词。例如“求最大值”和“求方案数”就是两类完全不同的问题前者可能用贪心或动态规划后者则可能涉及深度搜索或组合数学。建模是将自然语言描述的问题转化为计算机可处理的形式化问题的过程。对于算法题建模通常意味着定义状态明确我们要计算什么是某个位置的最优值还是某个集合的属性确定状态转移方程当前状态如何由已知的通常是更小的状态推导而来这是动态规划的核心。确定边界条件最小规模的问题初始状态的解是什么选择数据结构用什么来存储状态、中间结果或图/树的结构数组、向量、集合、映射还是自定义结构体一个清晰的模型是正确编码的基础。在接下来的具体题目解析中我们将反复运用这一思考过程。3. 典型真题深度解析与思路实现这里我选取两道当年我认为很有代表性的编程大题进行拆解一道偏重数学思维和规律寻找另一道则侧重于经典算法的应用与优化。3.1 例题A平方拆分问题抽象与枚举优化题目回忆将某个整数拆分成若干个互不相同的正整数的平方和求具体的拆分方案数或方案本身具体表述需回忆此处以典型变体为例进行方法论讲解。例如考察对于数字N有多少种拆分方式。核心考点深度优先搜索、剪枝优化、去重处理。思路拆解问题转化这不是简单的整数划分而是“子集和”问题的一个变体从1², 2², 3², ... , k² (其中 k² ≤ N) 这个集合中选取若干个互不相同的数使得它们的和等于N。算法选择由于每个平方数只能选或不选且顺序无关求组合而非排列自然想到用深度优先搜索来枚举所有可能的子集。建模状态当前搜索到第几个平方数idx当前已选取的平方数和sum当前已选取的平方数列表path。动作对于平方数nums[idx]有两种选择选或不选。目标sum N且path中的元素互不相同由于我们按顺序枚举自然保证不重复选取同一个数但需注意题目要求的正整数互不相同已由nums数组本身保证。关键优化——剪枝这是竞赛题的关键。如果不加优化枚举量会指数级爆炸。可行性剪枝如果sum nums[idx] N那么选择当前数必然导致和超过N这条分支可以剪掉。最优性剪枝本题是计数但思想类似如果当前和sum加上剩余所有可能的平方数从idx到最后一个的最大和仍然小于N那么即使后面全选也达不到N这条分支也可以剪掉。这需要预处理一个后缀和数组suffix_sum[i]表示从i开始的平方数之和。代码框架示意#include iostream #include vector #include cmath using namespace std; int N; vectorint squares; // 存储所有 ≤ N 的平方数 vectorint suffix_sum; // 后缀和用于剪枝 int count 0; // 方案数 vectorint current_path; // 当前路径 void dfs(int idx, int current_sum) { // 找到一个合法方案 if (current_sum N) { count; // 如果需要输出方案可以在这里打印 current_path return; } // 边界条件所有数都考虑完了或者下标越界 if (idx squares.size() || current_sum N) { return; } // 剪枝1: 即使加上当前数也超了后面的数更大更没希望直接返回 if (current_sum squares[idx] N) { // 实际上由于squares递增这里剪枝后连“不选”的分支也不必再深入 // 不 “不选”的分支可能还有希望靠后面的数组合。所以这里不能直接return。 // 正确的可行性剪枝在“选择”分支之前做判断。 } // 剪枝2: 当前和 剩余所有数的最大和 N 直接返回 if (current_sum suffix_sum[idx] N) { return; } // 分支1: 选择当前平方数 if (current_sum squares[idx] N) { // 选择前的可行性剪枝 current_path.push_back(squares[idx]); dfs(idx 1, current_sum squares[idx]); current_path.pop_back(); // 回溯 } // 分支2: 不选择当前平方数 dfs(idx 1, current_sum); } int main() { cin N; // 预处理平方数数组 for (int i 1; i * i N; i) { squares.push_back(i * i); } // 预处理后缀和数组从后往前计算 int m squares.size(); suffix_sum.resize(m, 0); suffix_sum[m-1] squares[m-1]; for (int i m-2; i 0; --i) { suffix_sum[i] suffix_sum[i 1] squares[i]; } dfs(0, 0); cout count endl; return 0; }实操心得剪枝的艺术DFS的威力很大程度上取决于剪枝的效率。suffix_sum剪枝是一种非常有效的“前缀和/后缀和”思想的应用它能提前判断整条分支的最终潜力避免大量无谓的搜索。回溯的细节在递归调用前后对current_path的push_back和pop_back必须成对出现这是回溯算法的标准写法务必熟练。去重本题因“互不相同”且我们按顺序枚举所以不会产生重复集合如{1,4}和{4,1}。如果题目允许重复元素或要求列出所有排列则去重会复杂得多可能需要使用排序跳过相同元素或使用集合来去重。3.2 例题B最优路径问题图论与动态规划结合题目回忆在一个带权有向图中寻找从起点到终点的一条路径该路径满足某些特定约束如经过特定点、边权之和最小但某些代价最大等求该路径的权重或路径本身。核心考点图的最短路径算法变体、状态压缩动态规划。思路拆解 假设一个具体化题目给定一个N个节点编号1~N、M条边的有向图边有权重。现在要从节点1走到节点N但必须至少经过K个指定的“关键节点”K通常较小比如≤10。求满足该条件的最短路径长度。问题分析这是一个典型的最短路径问题但附加了“必须经过特定点集”的约束。经典的Dijkstra或Floyd算法无法直接处理这种“带必经点”的约束。算法选择由于K很小这是一个强烈的提示——可以使用状态压缩动态规划。建模状态定义dp[u][state]表示当前走到节点u并且已经经过的关键点集合为state用一个整数的二进制位表示1表示已经过0表示未经过时的最短路径长度。状态转移对于状态dp[u][state]我们可以考虑从u走到它的邻居v。如果v是一个关键节点其编号为id[v]映射到0到K-1那么新的状态new_state state | (1 id[v])。转移方程为dp[v][new_state] min(dp[v][new_state], dp[u][state] weight(u, v))初始化dp[start][0] 0其他状态为无穷大。如果起点是关键节点则初始状态应为(1 id[start])。目标dp[end][final_state]其中final_state是所有关键点都至少经过一次的状态即(1 K) - 1。但注意题目是“至少经过”所以最终答案是所有state满足包含所有关键点即(state final_mask) final_mask的dp[end][state]中的最小值。实现方式这实际上是一个在“状态图”节点是(u, state)对上的最短路径问题。我们可以使用优先队列优化的Dijkstra算法即堆优化Dijkstra来求解。队列中的元素是(distance, u, state)。代码框架示意#include iostream #include vector #include queue #include cstring #include climits using namespace std; struct Edge { int to, weight; Edge(int t, int w) : to(t), weight(w) {} }; struct Node { int dist, u, state; // 小顶堆 bool operator(const Node other) const { return dist other.dist; } }; int main() { int N, M, K; cin N M K; vectorint key_nodes(K); vectorint is_key(N1, -1); // 映射节点编号 - 关键点索引(0~K-1)-1表示不是关键点 for (int i 0; i K; i) { cin key_nodes[i]; is_key[key_nodes[i]] i; } vectorvectorEdge graph(N1); for (int i 0; i M; i) { int u, v, w; cin u v w; graph[u].emplace_back(v, w); // 如果是有向图则只加一条边 } int start 1, end N; int state_size 1 K; // 状态总数 vectorvectorint dp(N1, vectorint(state_size, INT_MAX)); priority_queueNode, vectorNode, greaterNode pq; int init_state 0; if (is_key[start] ! -1) { init_state | (1 is_key[start]); } dp[start][init_state] 0; pq.push({0, start, init_state}); int final_mask (1 K) - 1; // 所有关键点都经过的掩码 int ans INT_MAX; while (!pq.empty()) { Node cur pq.top(); pq.pop(); int d cur.dist, u cur.u, s cur.state; if (d dp[u][s]) continue; // outdated entry, skip // 如果到达终点且状态包含了所有关键点更新答案 if (u end ((s final_mask) final_mask)) { ans min(ans, d); // 注意不能直接break因为可能还有其他更优路径在其他状态下到达终点 } for (const Edge e : graph[u]) { int v e.to, w e.weight; int next_state s; if (is_key[v] ! -1) { next_state | (1 is_key[v]); } if (dp[v][next_state] d w) { dp[v][next_state] d w; pq.push({dp[v][next_state], v, next_state}); } } } if (ans INT_MAX) { cout -1 endl; // 无解 } else { cout ans endl; } return 0; }实操心得状态设计是灵魂dp[u][state]这种“节点状态”的二维设计是解决此类“带约束的最短路径”问题的经典套路。关键在于识别出那个可以压缩的、规模较小的维度这里是关键点集合K。Dijkstra的适用性因为边权非负我们可以使用Dijkstra。如果边权有负则需要考虑SPFA或针对状态压缩DP的Bellman-Ford变体但竞赛中通常保证非负。内存与时间复杂度状态数是N * 2^K当N100K10时状态数约为100*102410万级别是可接受的。如果K再大此方法将不可行。答案的获取最终答案不一定在dp[end][final_mask]因为题目是“至少经过”可能以其他包含所有关键点的状态到达终点更短。所以需要遍历所有包含final_mask的状态取最小值。4. 通用技巧与常见“坑点”实录除了具体题目的解法在蓝桥杯乃至各类算法竞赛中有一些通用的技巧和几乎每次都会有人踩的“坑点”。4.1 输入输出与性能优化关闭同步流在C中cin/cout默认与C的stdio同步这会带来额外的开销。在需要大量读入输出的题目前使用ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);可以显著提升IO速度。注意一旦关闭同步就不要混用cin/cout和scanf/printf。使用\\n代替endlendl会刷新输出缓冲区导致频繁的IO操作降低效率。在竞赛中除非确需立即输出否则一律使用‘\\n‘。预估数据规模与复杂度这是选择算法的根本依据。如果N≤20可能是指数级算法如状压DP、全排列N≤1000O(N²)的算法可能可行N≤10^5通常需要O(NlogN)或O(N)的算法。在编码前务必进行大致的复杂度估算。4.2 数据类型与范围陷阱整数溢出这是最常见的错误之一。当题目涉及乘法、累加或者结果可能很大时第一时间要问自己会不会超过int的范围int通常是32位最大值约21亿2.1e9。如果可能超过果断使用long long64位。例如求N个数的和即使每个数都是int和也可能超出int范围。浮点数精度尽量避免直接比较两个浮点数是否相等a b。应该判断它们的绝对值差是否小于一个很小的数如1e-9。fabs(a - b) 1e-9。在涉及几何或者需要高精度计算的题目中有时可以尝试通过缩放将浮点数运算转化为整数运算来避免精度问题。数组大小全局数组开在静态存储区局部数组开在栈上。栈空间有限通常几MB开太大的局部数组会导致运行时错误如段错误。如果需要一个很大的数组比如上百万元素应该定义为全局变量或者使用vector动态分配在堆上。4.3 调试与测试策略构造边界测试用例自己测试时不要只用一个例子。要专门测试最小输入N0或1的情况。最大输入题目允许的最大N检查程序是否超时或内存溢出。特殊值例如在图论中测试只有一个节点、没有边的情况在搜索中测试无解的情况。使用assert在代码关键位置使用assert语句需要#include cassert可以帮助在调试阶段快速定位逻辑错误。例如在访问数组前assert(index 0 index n);。输出中间变量当程序结果不对时不要只盯着最终输出。在关键循环或递归函数中打印出重要的中间变量如状态值、循环索引、临时计算结果对比你的预期和实际输出这是定位bug最直接的方法。4.4 记忆化搜索与动态规划的抉择很多问题既可以用记忆化搜索Memoization DFS也可以用递推形式的动态规划DP来解决。记忆化搜索思路更直观直接从“原问题”出发递归地分解为子问题并用一个缓存如数组或哈希表存储已计算过的子问题结果避免重复计算。优点是符合人的自然思维代码容易写对。缺点是递归有栈开销对于深度很大的问题可能栈溢出且常数开销可能比递推略大。递推DP需要更清晰地定义状态转移的顺序通常从基础状态边界开始逐步递推到目标状态。优点是运行效率通常更高没有递归开销。缺点是需要仔细思考递推顺序有时不如记忆化搜索直观。个人建议对于初学者如果对状态转移关系不是百分之百确信优先使用记忆化搜索。它更容易实现且不易出错。当记忆化搜索写出来并AC后如果你有兴趣可以再尝试将其转化为递推DP作为一种练习。5. 备赛建议与资源利用基于对历年真题的分析给正在准备蓝桥杯或类似竞赛的同学几点建议夯实基础竞赛不是炫技扎实的基础是关键。确保对C/C标准库STL的常用容器vector,string,map,set,queue,stack,priority_queue和算法sort,lower_bound等了如指掌。对基础数据结构数组、链表、栈、队列、二叉树和算法排序、二分查找、递归、分治的理解要透彻。专题突破算法学习要成体系。分专题进行练习例如线性结构前缀和、差分、双指针、滑动窗口。搜索DFS、BFS及其剪枝技巧记忆化搜索。动态规划线性DP、区间DP、树形DP、状态压缩DP、数位DP。重点理解“状态定义”和“转移方程”。图论最短路Dijkstra, Floyd, SPFA、最小生成树Prim, Kruskal、拓扑排序。数学简单数论质数筛、最大公约数、快速幂、组合数学、简单计算几何。真题精练历年真题是最好的学习材料。不要满足于“看过”或“知道思路”。一定要动手编码并在OJ在线判题系统上提交直到ACAccepted。然后尝试思考是否有更优的解法代码能否更简洁边界条件处理是否完美模拟实战在备赛后期要严格按照比赛时间进行全真模拟。使用历年的真题套题在4小时内完成。这能有效训练时间分配、压力下的调试能力和策略选择。善用资源官方练习系统蓝桥杯官网的练习系统是首要资源。开源OJ如洛谷、力扣LeetCode尤其其“竞赛”和“学习”板块、AcWing、Codeforces等上面有海量的题目和活跃的社区。经典书籍《算法竞赛入门经典》刘汝佳、《算法竞赛进阶指南》李煜东都是很好的系统性学习资料。回过头看2019年的这些题目它们考察的与其说是某种奇技淫巧不如说是一种系统化的计算思维和严谨的工程实现能力。从审题建模到算法选择再到编码调试每一步都环环相扣。一道题目的价值往往不在于你当时是否把它做出来而在于事后复盘时你是否能清晰地复现整个思考链路并从中提炼出可迁移的方法。希望这次的解析能帮你打通一些关节在下次遇到似曾相识的问题时能更快地抓住本质。