1. 项目概述一次国赛真题的深度复盘去年带学生备赛蓝桥杯国赛结束后我们第一时间组织了对C B组题目的复盘。这不仅仅是为了对答案更是为了从出题人的视角理解国赛的考察重点、难点分布以及解题策略的演变。第十三届蓝桥杯C B组的国赛题目在我看来清晰地反映了当前算法竞赛对选手综合能力的要求扎实的数学功底、灵活的算法应用、严谨的代码实现以及对时间和空间复杂度的极致敏感。这份题解就是基于我们团队的实战解析和教学沉淀旨在为你还原赛场上的思考路径并提供超越标准答案的优化思路与避坑指南。无论你是即将参赛的选手还是希望提升算法能力的开发者相信这份从实战中淬炼出的解析都能让你有所收获。2. 整体赛题分析与策略总览2.1 题目结构与难度分布第十三届C B组国赛通常包含填空题和编程大题。填空题侧重基础数学、逻辑推理和简单编程是稳定拿分的关键编程大题则覆盖了动态规划、搜索、图论、数论等核心算法领域。从我们复盘的情况看本届题目的一个显著特点是“思维难度与实现精度并重”。有几道题目看似模型经典但在数据范围或状态设计上设置了“陷阱”直接套用模板很可能超时或得不出正确结果。例如一道关于序列操作的题目表面是区间修改查询但深入分析后会发现需要结合贪心思想和数据结构优化才能满足严格的时间限制。这要求选手不能停留在“知道算法”层面必须深入理解其适用场景和变通方法。2.2 核心考察能力拆解数学建模与抽象能力这是将实际问题转化为算法问题的第一步。国赛题目往往包裹着一层现实或游戏化的外壳比如“最优布线”、“资源分配”、“路径规划”等。快速剥离无关细节抽象出关键对象点、边、状态及其关系约束、目标函数是解题的基础。我们训练时强调“五分钟读题建模法”强制在初读题目时用简练的语言描述出输入是什么、输出是什么、核心的操作或规则是什么。算法工具箱的深度与广度广度确保你能识别问题类型深度确保你能解决它。必须熟练掌握的“武器库”包括基础排序、二分、前缀和、差分、双指针。核心DFS/BFS、回溯、动态规划线性、区间、树形、状压、贪心。高级最短路Dijkstra, SPFA、最小生成树、并查集、拓扑排序、快速幂、素数筛、欧几里得算法。数据结构栈、队列、堆优先队列、哈希表、树状数组、线段树。代码实现与调试能力思路正确但代码写崩是最大的遗憾。这包括边界条件处理数组越界、循环起止、递归深度与栈溢出、浮点数精度比较、大整数处理、多测试用例的初始化清零。国赛环境下的调试时间非常宝贵因此清晰的代码结构和良好的编码习惯至关重要。我们建议为每一个功能模块编写独立的函数并使用有意义的变量名。注意很多选手在练习时只关注“做出来”忽略了在压力环境下的一次通过率。平时训练应模拟赛场写完代码后先静态检查再用手工样例和边界样例测试最后才是提交。3. 典型赛题精讲与举一反三由于不能直接引用原题我将以本届比赛中几种典型的题型和考察点为蓝本重构出具有相同考察意图的例题并进行深度解析。你可以将这些题目视为对国赛真题核心精神的提炼和再现。3.1 例题A基于状态压缩的动态规划状压DP题目描述 有一个n x m的网格某些格子是障碍物不可放置。现在需要放置若干1x2大小的多米诺骨牌可以横放或竖放骨牌之间不能重叠且不能覆盖障碍物。问最多能放置多少块骨牌1 n, m 8考点分析 这是一道经典的“棋盘覆盖”问题是状压DP的入门必做题。它考察选手将棋盘每一行的放置状态用二进制压缩表示并进行行间状态转移的能力。n, m较小8是状压DP的典型信号因为单行状态数最多为2^m。思路解析与状态设计状态定义设dp[i][state]表示处理完前i行且第i行的放置状态为state时能放置的最大骨牌数。state是一个m位的二进制数第j位为1表示第i行第j列的格子被一个从第i-1行竖放下来的骨牌占据即当前行这个格子已经被占用。注意横放的骨牌会在同一行内占据两个格子这需要在状态转移时处理。状态转移从dp[i-1][prev_state]转移到dp[i][curr_state]。prev_state表示了第i-1行哪些格子被竖放骨牌的下半部分占据即这些格子已满。对于第i行我们需要枚举所有合法的放置方式。放置时需考虑 a. 不能放在障碍物上。 b. 当前行curr_state中为1的位置必须对应上一行prev_state中为0的位置因为上一行竖放下来的骨牌已经占用了它上面的格子这个格子本身在上一行是“伸出”状态所以上一行对应位置不能有来自更上一行的竖牌。 c. 剩下的空闲位置可以尝试放置横放骨牌连续两个空闲格子或者为下一行预留竖放骨牌将当前格子标记为被下一行占用即curr_state中该位为1。实现要点预处理每一行的障碍物掩码barrier[i]。使用DFS或迭代来生成每一行所有合法的放置状态curr_state及其对应的新增骨牌数cnt。转移方程为dp[i][curr_state] max(dp[i][curr_state], dp[i-1][prev_state] cnt)。最终答案是max(dp[n][state])其中state需要保证第n行没有“伸出”到不存在的第n1行的竖牌即state必须为0或与障碍物掩码一致。核心代码片段Cint n, m; int barrier[10]; // 障碍物掩码 int dp[10][18]; void dfs(int row, int col, int prev_state, int curr_state, int cnt, int idx) { if (col m) { // 枚举完一行进行状态转移 dp[row][curr_state] max(dp[row][curr_state], dp[row-1][prev_state] cnt); return; } // 情况1如果当前位置是障碍物或已被上一行的竖牌占用(prev_state的该位为1)则必须跳过 if ((barrier[row] col 1) || (prev_state col 1)) { dfs(row, col1, prev_state, curr_state, cnt, idx); return; } // 情况2尝试横放骨牌 (需要右边格子也空闲且不是障碍物) if (col1 m !(barrier[row] (col1) 1) !(prev_state (col1) 1)) { dfs(row, col2, prev_state, curr_state, cnt1, idx); } // 情况3尝试竖放骨牌占用了当前行和下一行的当前位置将当前行对应位标记为1 dfs(row, col1, prev_state, curr_state | (1 col), cnt1, idx); // 情况4当前位置不放为下一行竖放做准备不对不放的话这个格子就空着了但可能被上一行的竖牌占了这里已经排除。这里的不放是指既不横放也不作为竖放的起点但可能被下一行竖放覆盖这属于下一行的决策。 // 更准确地说对于当前行的一个空闲格子我们有三种选择1) 作为横放的左半部分2) 作为竖放的上半部分标记curr_state3) **不放**但这个格子在本行就空着了这通常是合法的但不一定最优。在我们的DFS中选择“不放”意味着直接跳到下一个格子不增加cnt也不标记curr_state。 // 所以需要补充“不放”的分支 dfs(row, col1, prev_state, curr_state, cnt, idx); } // 初始化 dp[0][0] 0其他为 -INF // 循环 for i from 1 to n: 枚举所有prev_state和curr_state进行dfs避坑指南状态含义不清最容易混淆的是state表示的是“当前行哪些格子被来自上一行的竖牌占据”而不是“当前行放置了骨牌的所有格子”。横放的骨牌不体现在state中只体现在放置数量cnt里。障碍物处理障碍物格子不能被任何骨牌覆盖在DFS枚举时必须首先检查。滚动数组优化由于dp[i]只依赖于dp[i-1]可以使用滚动数组将空间复杂度从O(n * 2^m)降到O(2^m)。3.2 例题B结合贪心与优先队列的调度问题题目描述 有n个任务每个任务有一个最晚完成时间d_i和需要消耗的连续时间t_i。从时间0开始按顺序处理任务每个任务必须在其最晚时间前完成。问最多能完成多少个任务考点分析 这是经典的“带截止时间的任务调度”问题。它考察选手的贪心思维和数据结构应用能力。直接按截止时间排序并依次尝试并不正确因为可能一个耗时长的任务挤占了多个耗时短的任务的位置。思路解析与算法选择 正确的策略是“反悔贪心”将所有任务按最晚完成时间d_i升序排序。用一个变量current_time记录当前已花费的时间初始为0。用一个最大堆优先队列pq来存储当前已选择任务的耗时t_i。遍历排序后的任务 a. 尝试直接完成该任务current_time t_i并将t_i加入pq。 b. 检查如果current_time d_i说明当前选择的任务集合无法全部在截止前完成。此时我们需要“反悔”从已选择的任务中移除一个耗时最长的任务即弹出pq的堆顶然后current_time减去这个耗时。因为堆顶是耗时最长的移除它最能缓解时间压力。 c. 循环步骤b直到current_time d_i。遍历结束后优先队列pq的大小就是最多能完成的任务数。为什么这样做是对的贪心选择按截止时间顺序处理保证了任务尝试的“可行性窗口”是递增的。当时间溢出时移除耗时最长的任务是一个局部最优决策因为它为后续任务腾出了最多的时间并且被移除的任务是已选集合中“代价”最大的。这等价于在不断维护一个在截止时间约束下总耗时最小的任务集合。核心代码片段C#include bits/stdc.h using namespace std; struct Task { int t, d; // 耗时截止时间 }; int main() { int n; cin n; vectorTask tasks(n); for (int i 0; i n; i) { cin tasks[i].t tasks[i].d; } // 按截止时间升序排序 sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { return a.d b.d; }); priority_queueint pq; // 最大堆存储已选任务的耗时 long long current_time 0; for (const auto task : tasks) { current_time task.t; pq.push(task.t); // 尝试选择该任务 // 如果超时则反悔移除当前已选中最耗时的任务 while (current_time task.d) { current_time - pq.top(); pq.pop(); } } cout pq.size() endl; return 0; }实操心得识别模型遇到“选择若干元素满足某种约束并最大化数量/价值”的问题且元素有“代价”和“限制”时要优先考虑贪心尤其是排序后配合堆进行反悔的贪心。数据范围注意current_time可能超出int范围需使用long long。堆的选择需要动态移除最大值所以使用最大堆。在C中priority_queueint默认是最大堆。3.3 例题C图论中的多源最短路与连通性判断题目描述 给定一个n x n的网格每个格子有一个高度。你可以在相邻上下左右格子间移动当且仅当两个格子的高度差不超过H。现在有k个起点和k个终点k 10你需要为每个起点分配一个唯一的终点并规划一条路径使得所有k条路径的总长度最短且路径之间不允许在任何格子相交包括起点终点。判断在给定H下是否可行并求最短总长度。考点分析 本题综合了二分答案、多源BFS、二分图匹配和最小费用最大流等多个知识点。难度很高是区分顶尖选手的题目。可行性判断二分路径是否连通取决于最大允许高度差H。H越大格子间可通行的限制越少越容易连通。我们可以对H进行二分查找找到最小的能使所有起点终点配对的H。路径不相交这是本题的核心难点。在H确定的地图上需要找到k条从起点集到终点集的一对一不相交路径。这可以转化为网络流中的节点容量问题。将每个网格点拆分为入点和出点中间连一条容量为1的边即可保证每个点最多被一条路径使用。然后建立超级源点连接所有起点超级汇点连接所有终点跑一次最大流。如果最大流等于k则说明存在k条不相交路径。总长度最短在满足流量的基础上要求总路径长度最短这就是最小费用最大流问题。将拆点后格子间的边费用设为1代表路径长度1源汇连接的边费用为0。思路拆解与实现步骤二分查找最小H设定H的范围[0, max_height_diff]。在check(H)函数中构建一个基于当前H的可通行图。在这个图上跑最小费用最大流。如果最大流等于k则记录费用总长度并返回 true尝试更小的H否则返回 false需要增大H。网络流建图节点编号对于格子(i, j)设入点 ID 为i*nj出点 ID 为i*nj n*n。从入点到出点连一条容量为1费用为0的边保证点不重复经过。对于格子(i, j)和它的四个邻居(ni, nj)如果高度差 H则从(i,j)的出点向(ni,nj)的入点连一条容量为1费用为1的边双向都需要连但注意避免重复。超级源点S向每个起点的入点连容量为1费用为0的边。每个终点的出点向超级汇点T连容量为1费用为0的边。算法选择使用 SPFA 或 Dijkstra带势函数求最短增广路的 MCMF 算法。复杂度与优化二分复杂度O(logN)。每次check需要跑一次 MCMF。图中有约2*n*n个点边数约4*n*n。k10流量很小但点较多。使用 Dinic SPFA 的费用流实现通常可以接受。重要优化由于二分过程中需要多次建图跑流而每次只有点之间的连通性边可能随H变化但图的结构点数、拆点方式不变。可以预先建立好所有可能的边根据高度差在check(H)时只将高度差 H的边加入图中这样可以避免重复建图。避坑指南拆点技巧保证点不重复经过的标准做法是“拆点连容量为1的边”。忘记拆点会导致路径相交。边的关系是出点连向邻居的入点不是入点连出点。费用设置只有表示“移动”的边费用为1拆点内部的边和源汇边费用为0。二分边界H的下界可能是0上界需要足够大比如所有格子高度最大值减最小值。4. 备赛策略与赛场实战技巧4.1 高效的备赛训练循环分专题突破不要盲目刷题。将算法分为前述的几大专题每个专题集中训练1-2周。从模板题开始到经典变式最后是综合应用题。每个专题至少保证50-100题的训练量并总结该专题的解题标志看到什么关键词想到什么算法和代码模板。定期参加模拟赛每周安排一次完整的4小时模拟赛使用历年真题或高质量模拟题。严格模拟赛场环境不能查阅资料、不能使用IDE的自动补全和调试器或限制使用、时间一到立刻停止。赛后进行不少于2小时的复盘重点复盘读题偏差、思路卡点、时间分配失误、编码错误。构建错题本与知识库不是简单记录题目和答案。每个错题或难题的记录应包括题目链接与核心描述。最初错误的思路是什么为什么错正确的解法是什么关键突破口在哪涉及的算法知识点和易错点。可以进一步优化或变形的方向。用思维导图软件如XMind整理算法间的联系和区别。4.2 赛场时间分配与决策前1小时快速通读所有题目对每道题进行初步评估。用“三色法”标记绿色简单一眼有思路大概率能快速AC的题。通常是前几道填空或简单编程。黄色中等知道考察方向但实现有细节或优化要求。红色困难暂时没清晰思路或实现非常复杂的题。第2-3小时主攻时间。按绿、黄、红的顺序做题。确保绿色题目全部得分这是保底基础。做黄色题目时如果卡壳超过30分钟果断保存当前代码切换到下一题。很多时候做其他题时的灵感会反过来帮助解决卡住的题。对于编程大题即使不能AC也要努力拿到部分分比如暴力分、小范围数据分。写一个正确的暴力解法有时能通过一半的测试点。最后1小时查漏补缺与冲刺。回头检查绿色题目的输入输出格式、边界条件。尝试解决之前跳过的黄色题目或者优化已有代码争取更多分数。对于红色题目如果时间所剩无几可以尝试写一些特殊情况的判断或输出固定答案碰碰运气。最后15分钟停止写新代码专注于检查已提交代码的潜在问题确保文件已正确保存和提交。4.3 编码与调试的硬核技巧模块化与函数化即使是竞赛也强烈建议将功能封装成函数。例如快速幂qpow()、并查集DSU类、Dijkstra 算法函数等。这不仅能减少重复代码更能降低思维负担让主逻辑清晰。防御性编程数组大小多开10%或10。初始化尤其是多组数据时全局变量和数组一定要在每组数据开始前重新初始化。使用const int INF 0x3f3f3f3f作为无穷大因为它满足INF INF不会溢出成负数。比较浮点数使用fabs(a-b) 1e-8。调试输出法在关键步骤、循环前后输出变量状态。提交前务必注释掉或删除所有调试输出。可以定义宏来方便切换#ifdef LOCAL #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) 42 #endif在本地编译时加上-DLOCAL参数即可开启调试输出。静态查错写完代码后不要立刻运行。花3-5分钟静态检查循环变量i, j是否写错数组下标是否可能越界if-else和{}括号是否匹配递归函数的终止条件是否完备输入数据范围是否考虑了极端情况如 n1, n05. 常见失误点与经典“坑题”剖析根据多年观察选手失分往往不是不会做而是掉进了题目精心设计的“坑”里。下面列举几类高频失误点5.1 整数溢出与精度损失坑点中间计算结果超出int范围即使最终答案在范围内。例如计算组合数C(n, m)或者累加很多个数。对策在乘法、加法前预估数据范围。如果可能超过2e9果断使用long long。对于1e5级别的数组求和总和就可能超过int。涉及取模的题目注意(a * b) % mod应在乘法前就转为long long(1LL * a * b) % mod。浮点数比较用相对误差或绝对误差避免直接。5.2 多组数据初始化坑点题目说“包含多组测试数据”但代码只按一组数据写。导致第二组数据计算时还残留着上一组的数据。对策将所有全局变量和数组的初始化放在while(cin n n)或int T; cin T; while(T--)循环内部。对于使用vector确保每次循环clear()并重新resize。养成“一组数据一初始化”的条件反射。5.3 搜索与DP的状态重复与遗漏坑点DFS/BFS 中没有标记已访问状态导致死循环或重复计数。DP中状态转移方程考虑不全漏掉了某些转移可能。对策搜索进入新状态立即标记vis[state]true回溯时撤销标记。对于网格DFS常用dx[4], dy[4]数组表示方向。DP画状态转移图。明确dp[i]可以从哪些状态转移而来又能够转移到哪些状态。使用“填表法”或“刷表法”时注意循环顺序。5.4 对“字典序最小”等特殊要求的处理坑点题目要求输出字典序最小的解但算法找到的是任意一个解。对策在搜索或构造时强制按字典序顺序尝试选择。例如在DFS中优先尝试标号小的节点或字符小的选项。在动态规划求方案时在状态转移时如果两个前驱状态都能得到最优值要选择能使当前方案字典序更小的那个前驱。这通常需要额外记录前驱状态或进行回溯比较。5.5 读题不细与理解偏差坑点忽略了题目中的关键约束如“编号从0开始”还是“从1开始”“恰好”和“至少”的区别“相邻”是否包含对角线等。对策用笔划出题目中的所有数字约束数据范围和所有条件描述必须、不能、至少、至多。在构思算法前自己构造2-3个小的样例包括边界情况用算法模拟一遍看是否符合题意。如果有样例先确保自己的程序能完全通过样例再思考其他情况。国赛的题目其价值远不止于比赛本身。通过对这些题目的深度剖析和反复练习你锻炼的是一种系统性的问题解决能力——拆解、建模、抽象、优化。这份能力无论是在后续的学习中还是在未来的开发工作中都是极其宝贵的财富。我常对学生说把每次练习都当成一次完整的项目开发从需求分析读题到算法设计架构再到编码实现开发和测试调试联调最后复盘总结项目回顾。这样无论比赛结果如何你都已经走完了一个完整的、高强度的思维训练循环这才是备赛最大的收获。 蓝桥杯国赛C++ B组深度复盘：算法核心、解题策略与备赛指南
1. 项目概述一次国赛真题的深度复盘去年带学生备赛蓝桥杯国赛结束后我们第一时间组织了对C B组题目的复盘。这不仅仅是为了对答案更是为了从出题人的视角理解国赛的考察重点、难点分布以及解题策略的演变。第十三届蓝桥杯C B组的国赛题目在我看来清晰地反映了当前算法竞赛对选手综合能力的要求扎实的数学功底、灵活的算法应用、严谨的代码实现以及对时间和空间复杂度的极致敏感。这份题解就是基于我们团队的实战解析和教学沉淀旨在为你还原赛场上的思考路径并提供超越标准答案的优化思路与避坑指南。无论你是即将参赛的选手还是希望提升算法能力的开发者相信这份从实战中淬炼出的解析都能让你有所收获。2. 整体赛题分析与策略总览2.1 题目结构与难度分布第十三届C B组国赛通常包含填空题和编程大题。填空题侧重基础数学、逻辑推理和简单编程是稳定拿分的关键编程大题则覆盖了动态规划、搜索、图论、数论等核心算法领域。从我们复盘的情况看本届题目的一个显著特点是“思维难度与实现精度并重”。有几道题目看似模型经典但在数据范围或状态设计上设置了“陷阱”直接套用模板很可能超时或得不出正确结果。例如一道关于序列操作的题目表面是区间修改查询但深入分析后会发现需要结合贪心思想和数据结构优化才能满足严格的时间限制。这要求选手不能停留在“知道算法”层面必须深入理解其适用场景和变通方法。2.2 核心考察能力拆解数学建模与抽象能力这是将实际问题转化为算法问题的第一步。国赛题目往往包裹着一层现实或游戏化的外壳比如“最优布线”、“资源分配”、“路径规划”等。快速剥离无关细节抽象出关键对象点、边、状态及其关系约束、目标函数是解题的基础。我们训练时强调“五分钟读题建模法”强制在初读题目时用简练的语言描述出输入是什么、输出是什么、核心的操作或规则是什么。算法工具箱的深度与广度广度确保你能识别问题类型深度确保你能解决它。必须熟练掌握的“武器库”包括基础排序、二分、前缀和、差分、双指针。核心DFS/BFS、回溯、动态规划线性、区间、树形、状压、贪心。高级最短路Dijkstra, SPFA、最小生成树、并查集、拓扑排序、快速幂、素数筛、欧几里得算法。数据结构栈、队列、堆优先队列、哈希表、树状数组、线段树。代码实现与调试能力思路正确但代码写崩是最大的遗憾。这包括边界条件处理数组越界、循环起止、递归深度与栈溢出、浮点数精度比较、大整数处理、多测试用例的初始化清零。国赛环境下的调试时间非常宝贵因此清晰的代码结构和良好的编码习惯至关重要。我们建议为每一个功能模块编写独立的函数并使用有意义的变量名。注意很多选手在练习时只关注“做出来”忽略了在压力环境下的一次通过率。平时训练应模拟赛场写完代码后先静态检查再用手工样例和边界样例测试最后才是提交。3. 典型赛题精讲与举一反三由于不能直接引用原题我将以本届比赛中几种典型的题型和考察点为蓝本重构出具有相同考察意图的例题并进行深度解析。你可以将这些题目视为对国赛真题核心精神的提炼和再现。3.1 例题A基于状态压缩的动态规划状压DP题目描述 有一个n x m的网格某些格子是障碍物不可放置。现在需要放置若干1x2大小的多米诺骨牌可以横放或竖放骨牌之间不能重叠且不能覆盖障碍物。问最多能放置多少块骨牌1 n, m 8考点分析 这是一道经典的“棋盘覆盖”问题是状压DP的入门必做题。它考察选手将棋盘每一行的放置状态用二进制压缩表示并进行行间状态转移的能力。n, m较小8是状压DP的典型信号因为单行状态数最多为2^m。思路解析与状态设计状态定义设dp[i][state]表示处理完前i行且第i行的放置状态为state时能放置的最大骨牌数。state是一个m位的二进制数第j位为1表示第i行第j列的格子被一个从第i-1行竖放下来的骨牌占据即当前行这个格子已经被占用。注意横放的骨牌会在同一行内占据两个格子这需要在状态转移时处理。状态转移从dp[i-1][prev_state]转移到dp[i][curr_state]。prev_state表示了第i-1行哪些格子被竖放骨牌的下半部分占据即这些格子已满。对于第i行我们需要枚举所有合法的放置方式。放置时需考虑 a. 不能放在障碍物上。 b. 当前行curr_state中为1的位置必须对应上一行prev_state中为0的位置因为上一行竖放下来的骨牌已经占用了它上面的格子这个格子本身在上一行是“伸出”状态所以上一行对应位置不能有来自更上一行的竖牌。 c. 剩下的空闲位置可以尝试放置横放骨牌连续两个空闲格子或者为下一行预留竖放骨牌将当前格子标记为被下一行占用即curr_state中该位为1。实现要点预处理每一行的障碍物掩码barrier[i]。使用DFS或迭代来生成每一行所有合法的放置状态curr_state及其对应的新增骨牌数cnt。转移方程为dp[i][curr_state] max(dp[i][curr_state], dp[i-1][prev_state] cnt)。最终答案是max(dp[n][state])其中state需要保证第n行没有“伸出”到不存在的第n1行的竖牌即state必须为0或与障碍物掩码一致。核心代码片段Cint n, m; int barrier[10]; // 障碍物掩码 int dp[10][18]; void dfs(int row, int col, int prev_state, int curr_state, int cnt, int idx) { if (col m) { // 枚举完一行进行状态转移 dp[row][curr_state] max(dp[row][curr_state], dp[row-1][prev_state] cnt); return; } // 情况1如果当前位置是障碍物或已被上一行的竖牌占用(prev_state的该位为1)则必须跳过 if ((barrier[row] col 1) || (prev_state col 1)) { dfs(row, col1, prev_state, curr_state, cnt, idx); return; } // 情况2尝试横放骨牌 (需要右边格子也空闲且不是障碍物) if (col1 m !(barrier[row] (col1) 1) !(prev_state (col1) 1)) { dfs(row, col2, prev_state, curr_state, cnt1, idx); } // 情况3尝试竖放骨牌占用了当前行和下一行的当前位置将当前行对应位标记为1 dfs(row, col1, prev_state, curr_state | (1 col), cnt1, idx); // 情况4当前位置不放为下一行竖放做准备不对不放的话这个格子就空着了但可能被上一行的竖牌占了这里已经排除。这里的不放是指既不横放也不作为竖放的起点但可能被下一行竖放覆盖这属于下一行的决策。 // 更准确地说对于当前行的一个空闲格子我们有三种选择1) 作为横放的左半部分2) 作为竖放的上半部分标记curr_state3) **不放**但这个格子在本行就空着了这通常是合法的但不一定最优。在我们的DFS中选择“不放”意味着直接跳到下一个格子不增加cnt也不标记curr_state。 // 所以需要补充“不放”的分支 dfs(row, col1, prev_state, curr_state, cnt, idx); } // 初始化 dp[0][0] 0其他为 -INF // 循环 for i from 1 to n: 枚举所有prev_state和curr_state进行dfs避坑指南状态含义不清最容易混淆的是state表示的是“当前行哪些格子被来自上一行的竖牌占据”而不是“当前行放置了骨牌的所有格子”。横放的骨牌不体现在state中只体现在放置数量cnt里。障碍物处理障碍物格子不能被任何骨牌覆盖在DFS枚举时必须首先检查。滚动数组优化由于dp[i]只依赖于dp[i-1]可以使用滚动数组将空间复杂度从O(n * 2^m)降到O(2^m)。3.2 例题B结合贪心与优先队列的调度问题题目描述 有n个任务每个任务有一个最晚完成时间d_i和需要消耗的连续时间t_i。从时间0开始按顺序处理任务每个任务必须在其最晚时间前完成。问最多能完成多少个任务考点分析 这是经典的“带截止时间的任务调度”问题。它考察选手的贪心思维和数据结构应用能力。直接按截止时间排序并依次尝试并不正确因为可能一个耗时长的任务挤占了多个耗时短的任务的位置。思路解析与算法选择 正确的策略是“反悔贪心”将所有任务按最晚完成时间d_i升序排序。用一个变量current_time记录当前已花费的时间初始为0。用一个最大堆优先队列pq来存储当前已选择任务的耗时t_i。遍历排序后的任务 a. 尝试直接完成该任务current_time t_i并将t_i加入pq。 b. 检查如果current_time d_i说明当前选择的任务集合无法全部在截止前完成。此时我们需要“反悔”从已选择的任务中移除一个耗时最长的任务即弹出pq的堆顶然后current_time减去这个耗时。因为堆顶是耗时最长的移除它最能缓解时间压力。 c. 循环步骤b直到current_time d_i。遍历结束后优先队列pq的大小就是最多能完成的任务数。为什么这样做是对的贪心选择按截止时间顺序处理保证了任务尝试的“可行性窗口”是递增的。当时间溢出时移除耗时最长的任务是一个局部最优决策因为它为后续任务腾出了最多的时间并且被移除的任务是已选集合中“代价”最大的。这等价于在不断维护一个在截止时间约束下总耗时最小的任务集合。核心代码片段C#include bits/stdc.h using namespace std; struct Task { int t, d; // 耗时截止时间 }; int main() { int n; cin n; vectorTask tasks(n); for (int i 0; i n; i) { cin tasks[i].t tasks[i].d; } // 按截止时间升序排序 sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { return a.d b.d; }); priority_queueint pq; // 最大堆存储已选任务的耗时 long long current_time 0; for (const auto task : tasks) { current_time task.t; pq.push(task.t); // 尝试选择该任务 // 如果超时则反悔移除当前已选中最耗时的任务 while (current_time task.d) { current_time - pq.top(); pq.pop(); } } cout pq.size() endl; return 0; }实操心得识别模型遇到“选择若干元素满足某种约束并最大化数量/价值”的问题且元素有“代价”和“限制”时要优先考虑贪心尤其是排序后配合堆进行反悔的贪心。数据范围注意current_time可能超出int范围需使用long long。堆的选择需要动态移除最大值所以使用最大堆。在C中priority_queueint默认是最大堆。3.3 例题C图论中的多源最短路与连通性判断题目描述 给定一个n x n的网格每个格子有一个高度。你可以在相邻上下左右格子间移动当且仅当两个格子的高度差不超过H。现在有k个起点和k个终点k 10你需要为每个起点分配一个唯一的终点并规划一条路径使得所有k条路径的总长度最短且路径之间不允许在任何格子相交包括起点终点。判断在给定H下是否可行并求最短总长度。考点分析 本题综合了二分答案、多源BFS、二分图匹配和最小费用最大流等多个知识点。难度很高是区分顶尖选手的题目。可行性判断二分路径是否连通取决于最大允许高度差H。H越大格子间可通行的限制越少越容易连通。我们可以对H进行二分查找找到最小的能使所有起点终点配对的H。路径不相交这是本题的核心难点。在H确定的地图上需要找到k条从起点集到终点集的一对一不相交路径。这可以转化为网络流中的节点容量问题。将每个网格点拆分为入点和出点中间连一条容量为1的边即可保证每个点最多被一条路径使用。然后建立超级源点连接所有起点超级汇点连接所有终点跑一次最大流。如果最大流等于k则说明存在k条不相交路径。总长度最短在满足流量的基础上要求总路径长度最短这就是最小费用最大流问题。将拆点后格子间的边费用设为1代表路径长度1源汇连接的边费用为0。思路拆解与实现步骤二分查找最小H设定H的范围[0, max_height_diff]。在check(H)函数中构建一个基于当前H的可通行图。在这个图上跑最小费用最大流。如果最大流等于k则记录费用总长度并返回 true尝试更小的H否则返回 false需要增大H。网络流建图节点编号对于格子(i, j)设入点 ID 为i*nj出点 ID 为i*nj n*n。从入点到出点连一条容量为1费用为0的边保证点不重复经过。对于格子(i, j)和它的四个邻居(ni, nj)如果高度差 H则从(i,j)的出点向(ni,nj)的入点连一条容量为1费用为1的边双向都需要连但注意避免重复。超级源点S向每个起点的入点连容量为1费用为0的边。每个终点的出点向超级汇点T连容量为1费用为0的边。算法选择使用 SPFA 或 Dijkstra带势函数求最短增广路的 MCMF 算法。复杂度与优化二分复杂度O(logN)。每次check需要跑一次 MCMF。图中有约2*n*n个点边数约4*n*n。k10流量很小但点较多。使用 Dinic SPFA 的费用流实现通常可以接受。重要优化由于二分过程中需要多次建图跑流而每次只有点之间的连通性边可能随H变化但图的结构点数、拆点方式不变。可以预先建立好所有可能的边根据高度差在check(H)时只将高度差 H的边加入图中这样可以避免重复建图。避坑指南拆点技巧保证点不重复经过的标准做法是“拆点连容量为1的边”。忘记拆点会导致路径相交。边的关系是出点连向邻居的入点不是入点连出点。费用设置只有表示“移动”的边费用为1拆点内部的边和源汇边费用为0。二分边界H的下界可能是0上界需要足够大比如所有格子高度最大值减最小值。4. 备赛策略与赛场实战技巧4.1 高效的备赛训练循环分专题突破不要盲目刷题。将算法分为前述的几大专题每个专题集中训练1-2周。从模板题开始到经典变式最后是综合应用题。每个专题至少保证50-100题的训练量并总结该专题的解题标志看到什么关键词想到什么算法和代码模板。定期参加模拟赛每周安排一次完整的4小时模拟赛使用历年真题或高质量模拟题。严格模拟赛场环境不能查阅资料、不能使用IDE的自动补全和调试器或限制使用、时间一到立刻停止。赛后进行不少于2小时的复盘重点复盘读题偏差、思路卡点、时间分配失误、编码错误。构建错题本与知识库不是简单记录题目和答案。每个错题或难题的记录应包括题目链接与核心描述。最初错误的思路是什么为什么错正确的解法是什么关键突破口在哪涉及的算法知识点和易错点。可以进一步优化或变形的方向。用思维导图软件如XMind整理算法间的联系和区别。4.2 赛场时间分配与决策前1小时快速通读所有题目对每道题进行初步评估。用“三色法”标记绿色简单一眼有思路大概率能快速AC的题。通常是前几道填空或简单编程。黄色中等知道考察方向但实现有细节或优化要求。红色困难暂时没清晰思路或实现非常复杂的题。第2-3小时主攻时间。按绿、黄、红的顺序做题。确保绿色题目全部得分这是保底基础。做黄色题目时如果卡壳超过30分钟果断保存当前代码切换到下一题。很多时候做其他题时的灵感会反过来帮助解决卡住的题。对于编程大题即使不能AC也要努力拿到部分分比如暴力分、小范围数据分。写一个正确的暴力解法有时能通过一半的测试点。最后1小时查漏补缺与冲刺。回头检查绿色题目的输入输出格式、边界条件。尝试解决之前跳过的黄色题目或者优化已有代码争取更多分数。对于红色题目如果时间所剩无几可以尝试写一些特殊情况的判断或输出固定答案碰碰运气。最后15分钟停止写新代码专注于检查已提交代码的潜在问题确保文件已正确保存和提交。4.3 编码与调试的硬核技巧模块化与函数化即使是竞赛也强烈建议将功能封装成函数。例如快速幂qpow()、并查集DSU类、Dijkstra 算法函数等。这不仅能减少重复代码更能降低思维负担让主逻辑清晰。防御性编程数组大小多开10%或10。初始化尤其是多组数据时全局变量和数组一定要在每组数据开始前重新初始化。使用const int INF 0x3f3f3f3f作为无穷大因为它满足INF INF不会溢出成负数。比较浮点数使用fabs(a-b) 1e-8。调试输出法在关键步骤、循环前后输出变量状态。提交前务必注释掉或删除所有调试输出。可以定义宏来方便切换#ifdef LOCAL #define debug(...) fprintf(stderr, __VA_ARGS__) #else #define debug(...) 42 #endif在本地编译时加上-DLOCAL参数即可开启调试输出。静态查错写完代码后不要立刻运行。花3-5分钟静态检查循环变量i, j是否写错数组下标是否可能越界if-else和{}括号是否匹配递归函数的终止条件是否完备输入数据范围是否考虑了极端情况如 n1, n05. 常见失误点与经典“坑题”剖析根据多年观察选手失分往往不是不会做而是掉进了题目精心设计的“坑”里。下面列举几类高频失误点5.1 整数溢出与精度损失坑点中间计算结果超出int范围即使最终答案在范围内。例如计算组合数C(n, m)或者累加很多个数。对策在乘法、加法前预估数据范围。如果可能超过2e9果断使用long long。对于1e5级别的数组求和总和就可能超过int。涉及取模的题目注意(a * b) % mod应在乘法前就转为long long(1LL * a * b) % mod。浮点数比较用相对误差或绝对误差避免直接。5.2 多组数据初始化坑点题目说“包含多组测试数据”但代码只按一组数据写。导致第二组数据计算时还残留着上一组的数据。对策将所有全局变量和数组的初始化放在while(cin n n)或int T; cin T; while(T--)循环内部。对于使用vector确保每次循环clear()并重新resize。养成“一组数据一初始化”的条件反射。5.3 搜索与DP的状态重复与遗漏坑点DFS/BFS 中没有标记已访问状态导致死循环或重复计数。DP中状态转移方程考虑不全漏掉了某些转移可能。对策搜索进入新状态立即标记vis[state]true回溯时撤销标记。对于网格DFS常用dx[4], dy[4]数组表示方向。DP画状态转移图。明确dp[i]可以从哪些状态转移而来又能够转移到哪些状态。使用“填表法”或“刷表法”时注意循环顺序。5.4 对“字典序最小”等特殊要求的处理坑点题目要求输出字典序最小的解但算法找到的是任意一个解。对策在搜索或构造时强制按字典序顺序尝试选择。例如在DFS中优先尝试标号小的节点或字符小的选项。在动态规划求方案时在状态转移时如果两个前驱状态都能得到最优值要选择能使当前方案字典序更小的那个前驱。这通常需要额外记录前驱状态或进行回溯比较。5.5 读题不细与理解偏差坑点忽略了题目中的关键约束如“编号从0开始”还是“从1开始”“恰好”和“至少”的区别“相邻”是否包含对角线等。对策用笔划出题目中的所有数字约束数据范围和所有条件描述必须、不能、至少、至多。在构思算法前自己构造2-3个小的样例包括边界情况用算法模拟一遍看是否符合题意。如果有样例先确保自己的程序能完全通过样例再思考其他情况。国赛的题目其价值远不止于比赛本身。通过对这些题目的深度剖析和反复练习你锻炼的是一种系统性的问题解决能力——拆解、建模、抽象、优化。这份能力无论是在后续的学习中还是在未来的开发工作中都是极其宝贵的财富。我常对学生说把每次练习都当成一次完整的项目开发从需求分析读题到算法设计架构再到编码实现开发和测试调试联调最后复盘总结项目回顾。这样无论比赛结果如何你都已经走完了一个完整的、高强度的思维训练循环这才是备赛最大的收获。