1. 赛后感言与整体复盘刚结束第十三届蓝桥杯国赛B组的征程从考场出来心情是复杂的。既有攻克难题后的酣畅淋漓也有对某些细节处理不当的懊恼。蓝桥杯国赛作为国内覆盖面极广的软件和信息技术专业赛事其B组的题目向来以“思维灵活、注重基础、陷阱隐蔽”著称。它不像一些纯算法竞赛那样追求极致的时空复杂度而是更贴近工程实践考察选手在有限时间内对问题建模、算法选择、代码实现以及边界处理的全方位能力。这次国赛的题目再次印证了这一特点没有出现需要艰深数论或复杂图论才能解决的“板子题”但每一道题都需要你静下心来仔细读题理解其背后的实际场景然后选择最合适、最稳健的方法去实现。对于准备参赛或者对算法感兴趣的朋友来说国赛真题是最好的练兵场它能帮你跳出盲目刷模板题的误区真正提升解决实际问题的能力。接下来我将结合我的解题思路和考场上的实际思考过程对B组的题目进行逐一拆解。我的分享不会只给出冷冰冰的AC代码更重要的是还原解题时的决策链条为什么想到这个方法其他方法为什么被排除实现过程中有哪些坑需要避开我希望这份“热气腾腾”的题解能让你不仅知道答案更能理解题目背后的设计逻辑和考察意图从而获得举一反三的能力。2. 试题A进制转换与字符串处理2.1 题目核心与场景还原第一题通常承担着“送温暖”和“查基础”的双重角色。本届A题也不例外题目描述了一个将某个大整数可能超过long long范围从十进制转换为指定进制比如16进制的场景并要求处理字母大小写等格式问题。这题看似简单但国赛的“简单题”往往在输入输出格式、边界条件上设置考验。核心考点非常明确大整数的表示与运算当数字超出内置整数类型范围时如何存储和计算这是区分选手是否只会用int和long long的关键。进制转换算法原理“除基取余法”的深刻理解与实现。不仅要知道怎么算更要能处理被除数是“大数”的情况。字符串的灵活操作包括反转、字符与数字的映射特别是A-F对应10-15、大小写转换。在考场上我第一眼就意识到这题的关键在于“大数”。题目中给出的示例或描述的数字长度暗示了普通整数类型会溢出。因此解题的起点不是直接写转换函数而是决定大数的存储方式。2.2 算法选择与实现细节对于大数我们通常用字符串string或数组vectorint来存储每一位十进制数字。这里我选择string因为它便于输入输出和切片操作。算法步骤拆解输入与初始化读入表示大数的字符串num_str和目标进制base比如16。模拟除法过程这是一个重复的过程直到商为0。初始化一个空字符串result用于存储转换后的结果逆序。初始化一个临时变量remainder为0用于存储每一轮除法的余数。遍历num_str的每一位数字字符从最高位开始将当前位的数字与上一轮遗留的remainder * 10相加得到当前被除数current。current remainder * 10 (num_str[i] - 0)。计算当前位的商和余数。quotient current / baseremainder current % base。这里有一个关键技巧quotient可能为0我们如何记录这一整轮除法后的“整体商”呢答案是将每一步计算出的quotient按顺序拼接起来形成新的被除数字符串用于下一轮除法。但要注意高位的0需要被妥善处理不能直接丢弃否则会出错。一个更清晰的做法是在一轮除法完成后我们得到了一串数字字符可能包含前导零这就是下一轮的num_str。处理余数每一轮除法结束后得到的remainder就是目标进制下的一个位数0-15。我们需要将其转换为对应的字符0-9 A-F。逆序与输出因为“除基取余法”得到的结果是从低位到高位的所以最后需要将result字符串反转。题目可能要求大写或小写在字符映射时控制好即可。代码实现要点伪代码风格string decimalToBaseX(string num_str, int base, bool uppercase) { vectorchar digits; // 存储结果数字逆序 while (!num_str.empty() !(num_str.size() 1 num_str[0] 0)) { int remainder 0; string next_num_str; // 存储下一轮的商 for (char digit_char : num_str) { int current remainder * 10 (digit_char - 0); next_num_str.push_back((current / base) 0); // 商的当前位 remainder current % base; } // 将余数转换为目标进制字符 char base_char; if (remainder 10) base_char 0 remainder; else base_char (uppercase ? A : a) (remainder - 10); digits.push_back(base_char); // 处理下一轮的被除数去掉前导零 int start 0; while (start next_num_str.size() next_num_str[start] 0) start; num_str (start next_num_str.size()) ? 0 : next_num_str.substr(start); } // 反转并返回结果 reverse(digits.begin(), digits.end()); return digits.empty() ? 0 : string(digits.begin(), digits.end()); }注意上述循环条件!(num_str.size() 1 num_str[0] 0)是处理输入就是“0”的情况。更稳健的判断是当next_num_str全为0时终止。2.3 常见失误与避坑指南这道题失分点往往不在算法本身而在细节前导零的处理在模拟除法生成下一轮被除数字符串时可能会产生前导零。绝对不能简单地将其转换为整数因为可能立刻溢出。必须将其作为字符串处理并小心地移除前导零但要保留至少一个“0”表示数字0本身。输入就是”0“必须特判否则循环可能无法进入或出错输出应为”0“。大小写要求仔细看题输出是大写字母A-F还是小写a-f忽略这一点会导致答案格式错误。进制范围题目给的base是否可能大于36通常不会但我们的映射逻辑要能扩展到base 36用0-9 A-Z表示。效率问题虽然是大数但本题规模通常可控。如果使用vectorint存储每位数字每次除法需要处理整个数组代码稍复杂但原理相同。字符串处理在本题中更直观。我的考场心得拿到题先花1分钟完整读题圈出“大整数”、“进制转换”、“字母格式”等关键词。在草稿纸上手动模拟一遍小例子比如将”255“转16进制确保流程清晰。实现时先写好核心的除法循环框架再逐个填充边界条件处理。这道题稳稳拿下能为整个比赛开个好头建立信心。3. 试题B动态规划与状态压缩3.1 问题抽象与模型建立B题开始提升难度通常涉及经典的算法思想。本届B题是一个典型的状态压缩动态规划问题我将其抽象为在一个N x M的网格上放置某种形状的物件物件之间不能重叠求铺满整个网格的方案数。这很像经典的“铺瓷砖”或“骨牌覆盖”问题的变种。为什么是状态压缩DP因为网格的宽度M通常较小比如M 10而行数N较大。我们可以以“行”为单位进行推进。每一行的摆放状态可以用一个M位的二进制数来表示1表示该位置被当前行的物件占据0表示空位可能是留给下一行物件的延伸部分或者就是空的。我们需要从上一行的状态推导出下一行的合法状态并计数。核心难点在于状态定义dp[i][state]表示处理完前i行且第i行的摆放状态为state时总的方案数。状态转移给定第i-1行的状态prev_state如何枚举出所有合法的第i行状态curr_state这需要根据物件的具体形状来判断。初始化与最终答案初始化dp[0][0] 1表示第0行之前没有任何摆放状态为全0有一种方案。最终答案是dp[N][0]即处理完所有N行后最后一行没有任何向下一行延伸的部分状态为0。3.2 状态转移的深度解析这是本题最核心的部分。我们假设物件是1x2的骨牌横放或竖放。那么转移规则是如果prev_state中某一位是1表示这个位置已经被上一行竖放的骨牌上半部分占据那么curr_state的对应位必须是0因为被填满了。对于prev_state中为0的位置curr_state可以放一个横放的骨牌连续两位设为1也可以作为竖放骨牌的下半部分设为1但需要和上一行对应位为1配对——这其实已经由第一条规则保证了或者不放保持为0可能和后面的位置组成横放或者留给下一行。实际上更通用的方法是使用DFS深度优先搜索来生成所有合法的(prev_state, curr_state)配对。我们可以从一行的左边开始逐位考虑如果prev_state的当前位是1则curr_state的当前位只能是0被上一行占据然后处理下一位。如果prev_state的当前位是0可以选择在curr_state放一个横放的骨牌即curr_state的当前位和下一位都设为1然后跳过下一位继续处理。可以选择在curr_state放一个竖放的骨牌这需要curr_state的当前位为1但这意味着上一行的对应位必须是0已满足并且这个1会被消耗掉它对应的是“本行开始的一个竖放骨牌的上半部分”它的下半部分会在下一行即i1行的相同位置以prev_state的1出现。所以在生成配对时我们实际上是在决定curr_state中哪些1是横放的哪些位置是空的0。竖放骨牌是由prev_state中的1和curr_state中的0来隐式表示的。更准确地说在状态转移DFS中我们关注的是如何用骨牌覆盖prev_state为0的那些位置。我们可以放横牌影响curr_state的两位也可以放竖牌在curr_state放一个1但这个1意味着“这里是一个竖牌的开头”它需要消耗下一行的一个位置。为了简化一种经典写法是同时枚举两行的状态并检查其兼容性。经典预处理技巧预处理出所有合法的“行状态”state。一个行状态自身要合法不能有奇数个连续的1如果只允许横放或者说1必须成对出现对于1x2横放。更一般的需要根据物件形状写一个check(state)函数。对于每一个合法的prev_state预处理出所有能转移到它的curr_state列表trans[prev_state]。这样在DP循环时可以直接遍历这个列表提升效率。3.3 代码框架与优化策略int M, N; vectorint valid_states; // 所有合法的单行状态 vectorvectorint trans; // trans[prev] {所有合法的curr状态列表} // 1. 预处理所有合法单行状态 for (int s 0; s (1 M); s) { if (isValid(s)) valid_states.push_back(s); } // 2. 预处理状态转移关系 trans.resize(1 M); for (int prev : valid_states) { for (int curr : valid_states) { if (isCompatible(prev, curr)) { trans[prev].push_back(curr); } } } // 3. DP过程 vectorvectorlong long dp(N 1, vectorlong long(1 M, 0)); dp[0][0] 1; // 初始化 for (int i 1; i N; i) { for (int prev_state : valid_states) { if (dp[i-1][prev_state] 0) continue; for (int curr_state : trans[prev_state]) { dp[i][curr_state] dp[i-1][prev_state]; // 注意取模如果题目要求 // dp[i][curr_state] % MOD; } } } long long ans dp[N][0]; // 最后一行必须全0优化与注意事项滚动数组由于dp[i]只依赖于dp[i-1]可以使用两个一维数组滚动节省大量内存。这是竞赛中的必备技巧。取模方案数可能巨大题目通常要求对某个数取模如1e97。必须在加法过程中就取模防止溢出。isValid和isCompatible函数这两个函数是实现正确性的核心必须根据题目描述的物件形状精确实现。在考场上务必在草稿纸上多画几个例子来验证逻辑。M1的特殊情况当只有一列时横放无法进行只有竖放一种可能如果N是偶数。需要检查你的isValid函数是否能正确处理边界情况。我的考场心得状态压缩DP代码相对模板化但关键在于正确理解状态定义和转移条件。我通常会先忽略代码在草稿纸上画出几行网格手动枚举几个状态和转移确保脑海中的模型和题目要求完全匹配。实现isCompatible函数时我会写出详细的注释明确每个if条件判断的物理意义。这道题如果模型建对了就是一路坦途如果一开始理解偏差就会陷入调试深渊。因此审题和建模的时间绝对不能省。4. 试题C图论建模与最短路径4.1 题意转化与图模型构建C题通常会将一个生活或工程问题抽象成图论问题。本届C题描述了一个资源传输或者信号传递的场景有若干个节点城市、设备等节点之间有双向通道每条通道有固定的“容量”或“成本”并且可能存在“拥堵”或“延迟”系数随时间或流量变化。题目最终要求的是在满足某些约束下如总时间最小、在某个时限内传输最大资源等从起点到终点的最优方案。第一步永远是建图。我们需要确定顶点是什么通常是题目中给出的各个实体。边是什么是实体间的连接关系权重可能包含距离、时间、成本、容量等一个或多个维度。问题是什么是最短路径、最大流、最小费用流还是带有约束的最优化以一道经典的“带限制的最短路径”为例每条边有通过时间t和消耗资源c总资源上限为C求在资源消耗不超过C的前提下从起点到终点的最短时间。这显然是一个二维约束的最短路问题可以使用扩展的Dijkstra算法或DP。4.2 多维状态最短路算法实现传统的Dijkstra使用dist[node]记录到某个节点的最短距离。现在我们需要增加一维资源消耗所以状态变为dist[node][used_resource]表示从起点到节点node恰好消耗了used_resource资源时的最短时间。算法流程基于优先队列的Dijkstra变种初始化dist[V][C1]为无穷大dist[start][0] 0。使用优先队列元素为(time, node, used_resource)按time从小到大排序。弹出当前时间最小的状态(cur_time, u, used_c)。如果cur_time dist[u][used_c]说明是旧状态跳过。遍历节点u的所有邻居v边上的时间和资源消耗为(t_uv, c_uv)。计算新状态new_used used_c c_uvnew_time cur_time t_uv。剪枝如果new_used C资源超限则跳过。如果new_time dist[v][new_used]则更新dist[v][new_used] new_time并将(new_time, v, new_used)入队。最终答案遍历dist[dest][0...C]取其中的最小值即为在资源限制C内能到达终点的最短时间。如果全部都是无穷大则说明无法在资源限制内到达。struct State { int node; int cost; // 已消耗资源 long long time; // 当前总时间 bool operator(const State other) const { return time other.time; // 最小堆按时间排序 } }; long long dist[MAX_N][MAX_C]; void dijkstra(int start, int C) { memset(dist, 0x3f, sizeof(dist)); dist[start][0] 0; priority_queueState, vectorState, greaterState pq; pq.push({start, 0, 0}); while (!pq.empty()) { State cur pq.top(); pq.pop(); int u cur.node, used cur.cost; if (cur.time dist[u][used]) continue; for (auto [v, t_edge, c_edge] : graph[u]) { int new_used used c_edge; if (new_used C) continue; // 资源超限 long long new_time cur.time t_edge; if (new_time dist[v][new_used]) { dist[v][new_used] new_time; pq.push({v, new_used, new_time}); } } } }4.3 边界处理与优化思考状态数量节点数V乘以资源上限C可能很大导致dist数组和队列操作开销大。如果C很大比如1e9这种方法不可行。此时可能需要换思路比如二分答案时间然后检查在给定时间内消耗的最小资源是否不超过C或者使用更高级的算法。无穷大设置dist初始化的无穷大值要足够大通常用0x3f3f3f3f对于int或1e18对于long long。优先队列的排序一定要按“当前时间”排序才能保证Dijkstra的正确性。图的存储使用邻接表vectorvectortupleint, int, int graph(V)比邻接矩阵更节省空间。答案检索最终答案可能在dist[dest][i]的任何一个i中需要遍历所有0iC。有时题目要求“恰好用完资源”或“资源消耗最少”检索方式会不同。我的考场心得遇到图论题先花几分钟在草稿纸上画出样例图标出权值手动算一下预期答案这能极大帮助理解题意。对于多维状态最短路关键是设计好dist数组的维度想清楚每个维度的含义。在实现时我会先写出状态结构体和比较函数然后再写核心循环。调试这类题的一个好方法是打印出队列的状态变化对于小样例可以手动验证更新是否正确。如果发现超时首先要检查是不是状态维度过大或者剪枝不够。5. 试题D贪心策略与证明5.1 问题分析与策略猜想D题往往考察贪心思维。题目可能关于任务调度、区间选择、资源分配等。例如有若干个任务每个任务有开始时间、结束时间和报酬同一时间只能做一个任务求能获得的最大总报酬。贪心题目的特点是每一步都做出当前看起来最优的选择希望最终结果也是全局最优。但贪心算法必须要有正确性证明否则可能就是错的。对于任务调度问题常见的贪心策略有按结束时间从小到大排序。按开始时间从小到大排序。按任务时长排序。按报酬密度报酬/时长排序。我们需要通过分析甚至反例来排除错误的策略。对于“最大报酬无重叠区间”问题按结束时间排序是正确的。为什么因为结束得早就能给后面的任务留下更多的时间。5.2 算法流程与正确性证明算法步骤将N个任务按结束时间end_i从小到大排序。如果结束时间相同可以按开始时间排序通常不影响。初始化当前已安排的最后结束时间last_end 0总报酬total_reward 0。遍历排序后的任务列表如果当前任务的开始时间start_i last_end说明它和已选任务不冲突。选择该任务total_reward reward_i更新last_end end_i。否则跳过该任务。正确性证明思路交换论证法 假设我们按上述贪心算法得到了一个解序列G。假设存在一个最优解序列O其总报酬比G高。我们可以找到G和O中第一个选择不同的任务。假设在某个时间点G选择了任务g而O选择了任务oo可能与g不同也可能O在这里没选任务。由于我们是按结束时间排序的任务g的结束时间一定不晚于任务o的结束时间如果O在这里有选任务的话。那么我们可以构造一个新的解O‘将O中的任务o如果存在替换成任务g并调整O’中g之后的任务因为g结束得更早或相同所以g之后的任务依然可以不冲突。O‘的总报酬不会低于O因为g的报酬可能更高或相等且我们只替换了一个。并且O’在第一个不同位置之后的选择变得和G更相似了。重复上述操作我们可以一步步将最优解O“转换”成我们的贪心解G并且总报酬不会减少。这就证明了贪心解G至少和任意一个最优解一样好因此G就是最优解。5.3 实现细节与变种讨论struct Task { int start, end, reward; }; bool cmp(const Task a, const Task b) { return a.end b.end; // 按结束时间排序 } int maxReward(vectorTask tasks) { sort(tasks.begin(), tasks.end(), cmp); int last_end 0; int total 0; for (const auto task : tasks) { if (task.start last_end) { total task.reward; last_end task.end; } } return total; }注意事项排序是关键必须严格按照结束时间排序。边界条件开始时间等于上一个结束时间算不算冲突通常题目会说“同一时间只能做一个任务”如果开始时间等于last_end意味着上一个任务刚结束这个任务可以立刻开始通常不冲突。但务必根据题目描述确定例如题目说“区间闭区间[start, end]”那么start_i last_end就冲突了。如果要求输出具体任务序列在选择任务时将其索引记录下来即可。变种与扩展最多能完成多少个任务每个任务报酬相同这就是经典的“活动选择问题”贪心策略完全一样。任务带权重即本题上述策略依然正确。每个任务有工作时间段求最大工作时间可以将报酬视为任务时长策略不变。使用最少资源完成所有任务例如有多个教室安排所有课程求最少需要多少教室。这需要按开始时间排序使用优先队列最小堆来维护当前正在进行的任务的结束时间。这是另一个经典的贪心问题。我的考场心得做贪心题最忌想当然。即使直觉上某个策略很合理也必须尝试构造反例或者思考证明。我习惯先写出几个策略然后用小数据比如3-4个任务手动模拟看哪个能得到正确结果。如果时间允许最好能简要写下证明思路。实现代码通常很简单难点全在于策略的选择和证明。这道题如果策略选对5分钟就能写完如果选错可能浪费半小时还得不到分。