1. 项目概述一次深度复盘的价值最近整理硬盘翻到了2019年参加第十届蓝桥杯大赛软件类B组国赛的代码和笔记。时间过去几年但当时在赛场上的那种紧张感、解题时的思维碰撞以及赛后复盘时的豁然开朗依然记忆犹新。蓝桥杯的题目尤其是国赛级别的从来都不是单纯考察语法它更像是一个综合能力的试金石将算法思维、代码实现、边界条件处理和临场应变能力熔于一炉。今天我想抛开官方题解那种“标准答案”式的叙述从一个参赛者和后来教学者的双重角度重新拆解这套C/C B组的国赛题目。我的目标不是简单地给出代码而是带你回到解题的“第一现场”分享我当时以及后来反思中的思考路径、遇到的坑以及那些比答案本身更重要的解题“元技能”。无论你是正在备赛的选手还是对算法竞赛感兴趣的开发者希望这份带着“体温”和“教训”的复盘能给你带来一些不一样的启发。2. 整体赛题分析与解题策略定调拿到一套竞赛题尤其是像蓝桥杯国赛这种五个小时五道题的赛制第一步绝对不是埋头就写。这五个小时是战略资源如何分配直接决定了最终的成绩上限。2019年这套B组题整体上承袭了蓝桥杯一贯的风格前面有“送分”的基础题稳定军心中间有需要仔细琢磨的思维题拉开差距最后则是由真正考验算法功底和优化能力的硬核题来角逐顶级名次。2.1 题目难度梯度与时间规划我的策略通常是“三轮扫描法”。第一轮快速通读所有题目对每道题进行初步定级。以这套题为例第一题往往是结果填空或代码填空考察基本语法和简单逻辑。这类题目标志着“必须拿下且快速拿下”计划用时在15-20分钟内包括检查。中间题目如第二、三题复杂度开始提升可能涉及基础算法如模拟、搜索、简单DP或数学思维。这是得分的关键区也是区分中等和良好成绩的战场。每道题我会预留40-60分钟其中包含读题、构思、编码、测试和调试的时间。最后两题尤其是压轴题通常是动态规划、图论优化或复杂的数论问题。对于大多数B组选手目标不一定是AC完全正确而是尽可能拿到部分分数部分正确。我会预留至少1.5小时给最后两题优先保证有清晰思路的题目能写出正确代码对于难题则力求写出能过小数据范围的“暴力解”或思路正确的伪代码争取步骤分。这套2019年的题目印象中第一题是典型的“签到题”考察点可能在日期处理或者简单计算。第二、三题开始引入场景需要建模。第四、五题则明显需要算法知识储备。时间分配上我当时大致是题115分钟、题240分钟、题350分钟、题470分钟、题5剩余时间检查。这个规划不是死的需要根据实际解题情况动态调整。2.2 环境与工具的准备要点国赛现场提供标准的IDE如Dev-C但你的“软环境”同样重要。我强烈建议在赛前就形成自己固定的代码模板和调试习惯。头文件模板提前写好一个包含所有常用头文件iostream,cstdio,vector,algorithm,cmath等、常用宏定义如#define INF 0x3f3f3f3f和简短IO优化的模板文件。比赛开始第一件事就是把它贴进去这能节省大量时间并避免低级错误。调试技巧在竞赛环境中没有强大的图形化调试器printf/cout调试法就是你的王牌。我习惯在代码关键节点如循环开始/结束、函数调用前后输出关键变量的值。对于大数据量题目可以配合文件重定向进行测试。// 假设编译后的程序为main.exe输入数据在in.txt // 在命令行中执行 main.exe in.txt my_output.txt // 然后比较 my_output.txt 和标准答案数据范围分析这是决定算法选择的关键一步。题目描述中给出的数据范围如1 n 10^5直接告诉你暴力搜索O(n^2)是否可行。看到10^5这个量级O(nlogn)的算法如排序、优先队列通常是安全的而O(n^2)则极有可能超时。3. 核心题目逐题精讲与思维还原现在让我们回到具体的题目。由于无法直接重现原题我将基于常见的蓝桥杯国赛题型和当年题目的考察方向重构解题思路和核心实现。我会重点讲“为什么这么想”以及“如何避免踩坑”。3.1 典型签到题稳中求快的基石题目特征问题描述简单可能涉及日期计算、字符串处理、基础数论如质数判断、公约数或简单的逻辑推理。目标是快速、准确无误地拿到分。模拟题型与解法假设题目是“从2019年1月1日到2019年12月31日有多少天的年月日数字之和等于20”此为模拟题型非原题。思路解析这本质上是一个枚举题。数据量很小一年365天直接暴力遍历每一天是完全可行的。关键在于如何优雅地遍历日期。实现细节与避坑日期遍历自己处理每月天数注意闰年固然可以但更稳妥的方法是使用语言自带的日期库C11的chrono太复杂竞赛中常用ctime或者手动模拟。对于这种固定年份的手动模拟更直观。数字分解编写一个digitSum(int n)函数来计算一个整数各位数字之和。注意对于日期如“2019-05-09”我们需要计算20190509还是201959题目必须明确通常是指去掉分隔符后的数字和。这里容易产生歧义。边界检查起始和结束日期是否包含务必读清题目“从…到…”是闭区间还是开区间。#include iostream using namespace std; // 判断闰年 bool isLeapYear(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } // 获取某年某月的天数 int daysOfMonth(int y, int m) { if (m 2) return isLeapYear(y) ? 29 : 28; if (m 4 || m 6 || m 9 || m 11) return 30; return 31; } // 计算数字各位之和 int digitSum(int num) { int sum 0; while (num) { sum num % 10; num / 10; } return sum; } int main() { int year 2019; int totalDays 0; for (int month 1; month 12; month) { int days daysOfMonth(year, month); for (int day 1; day days; day) { // 假设计算规则是 年月日 的各位数字和 int sum digitSum(year) digitSum(month) digitSum(day); if (sum 20) { totalDays; // 可以输出具体日期用于验证 // cout year - month - day endl; } } } cout totalDays endl; return 0; }注意蓝桥杯填空题通常只需要提交最终结果。在代码中最终输出前务必确认计算逻辑与题目要求百分百吻合。一个很好的习惯是用几个显而易见的例子验证你的digitSum函数和日期遍历逻辑。3.2 中等难度题建模与基础算法的应用题目特征问题场景稍复杂需要将文字描述抽象成数学模型并应用一种或多种基础算法。常见的有路径搜索DFS/BFS、简单动态规划、贪心选择、二分查找等。模拟题型与解法假设题目是“在一个N x M的网格中每个格子有不同数量的宝物。从左上角(1,1)出发每次只能向右或向下移动到达右下角(N,M)。求能收集到的宝物最大数量。”此为经典DP问题用于说明思路。思路解析这几乎是动态规划DP的入门模板题。因为移动方向受限只能向右或向下这意味着到达当前格子(i, j)的路径只能来自上方(i-1, j)或左方(i, j-1)。那么到达(i, j)所能获得的最大宝物数就等于max(从上方来的最大收益 从左方来的最大收益) 当前格子宝物数。状态定义与转移方程定义dp[i][j]为从(1,1)走到(i,j)能获得的最大宝物数。转移方程dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]边界处理对于第一行i1只能从左方来对于第一列j1只能从上方来。我们可以初始化dp[0][j]和dp[i][0]为负无穷或0具体看题意或者在代码中单独处理边界。实现与优化#include iostream #include vector #include algorithm using namespace std; int main() { int N, M; cin N M; vectorvectorint grid(N 1, vectorint(M 1, 0)); // 1-indexed vectorvectorint dp(N 1, vectorint(M 1, 0)); for (int i 1; i N; i) for (int j 1; j M; j) cin grid[i][j]; // DP过程 for (int i 1; i N; i) { for (int j 1; j M; j) { if (i 1 j 1) { dp[i][j] grid[i][j]; // 起点 } else if (i 1) { dp[i][j] dp[i][j-1] grid[i][j]; // 第一行 } else if (j 1) { dp[i][j] dp[i-1][j] grid[i][j]; // 第一列 } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } } } cout dp[N][M] endl; return 0; }实操心得对于这类网格DP使用1-index下标从1开始可以大大简化边界条件的判断避免在dp[i-1]时出现负数下标。另外如果网格非常大比如N,M 500需要考虑空间优化因为dp[i][j]只依赖于上一行和当前行可以用滚动数组将空间复杂度从O(N*M)降到O(M)。3.3 压轴难题高级算法与优化策略题目特征数据规模大暴力法必然超时。需要运用较高级的算法或数据结构如树状数组/线段树、复杂DP状压DP、数位DP、图论算法最短路、最小生成树、网络流、高级搜索A*、IDA*等。解题的关键在于识别问题本质。模拟题型与解法假设题目是“有N个任务每个任务有开始时间Si和结束时间Ei以及收益Pi。选择若干个互不重叠的任务使得总收益最大。求最大收益。”此为经典的活动选择加权问题可用DP二分优化。思路解析如果N很小20可以用状态压缩枚举所有子集。但国赛数据N往往在10^5级别必须优化。第一步排序。将所有任务按结束时间Ei升序排序。这样当我们考虑第i个任务时所有结束时间小于等于Si的任务都已经考虑过了。第二步定义状态。设dp[i]表示考虑前i个任务按结束时间排序后能获得的最大收益。第三步状态转移。对于任务i有两种选择不选i则dp[i] dp[i-1]选i则需要找到最后一个结束时间小于等于Si的任务j。那么dp[i] dp[j] Pi。 因此dp[i] max(dp[i-1], dp[j] Pi)。第四步高效查找j。在排序后的数组中寻找最大的j使得E[j] S[i]。这是一个二分查找问题。我们可以预处理一个数组prev[i]来存储这个j或者直接在转移时进行二分查找。关键实现#include iostream #include vector #include algorithm using namespace std; struct Task { int start, end, profit; }; int main() { int N; cin N; vectorTask tasks(N); for (int i 0; i N; i) { cin tasks[i].start tasks[i].end tasks[i].profit; } // 按结束时间排序 sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { return a.end b.end; }); vectorint dp(N, 0); vectorint endTimes(N); // 用于二分查找 for (int i 0; i N; i) { endTimes[i] tasks[i].end; } dp[0] tasks[0].profit; // 初始化第一个任务 for (int i 1; i N; i) { // 不选当前任务 int profit1 dp[i-1]; // 选择当前任务需要找到最后一个结束时间 tasks[i].start 的任务索引 j int j -1; // 手动二分查找 int left 0, right i - 1; while (left right) { int mid left (right - left) / 2; if (tasks[mid].end tasks[i].start) { j mid; left mid 1; // 尝试找更靠后的 } else { right mid - 1; } } int profit2 tasks[i].profit; if (j ! -1) { profit2 dp[j]; } dp[i] max(profit1, profit2); } cout dp[N-1] endl; return 0; }深度剖析这道题的核心优化点有两个。第一是排序将问题转化为线性DP第二是二分查找将寻找兼容任务的时间从O(n)降为O(logn)从而使整体复杂度达到O(nlogn)才能应对大数据。在竞赛中能否快速识别出“排序后具有某种单调性从而可以使用二分或指针优化”是解决难题的关键能力之一。4. 竞赛实战中的通用技巧与“避坑”指南解题思路固然重要但在紧张的竞赛环境中如何少犯错、高效调试、管理心态往往更能决定最终排名。4.1 输入输出与数据类型的陷阱输入格式蓝桥杯题目输入有时很“灵活”可能在一行也可能分多行。务必使用最鲁棒robust的读入方式。cin在读取数字时会自动跳过空白字符空格、换行通常比较安全。但对于需要读取整行字符串再解析的建议使用getline(cin, str)。数据范围与溢出这是新手和老手都会翻车的地方。看到计算结果可能很大时第一时间问自己用int够吗对于涉及乘法、累加的场景10^5个10^5的数相加就会超出int范围约21亿。稳妥起见如果题目数值可能超过10^9或者你心里没底直接使用long long(int64_t)。在C中常量后面加LL如1LL * a * b来强制提升运算类型为long long防止中间结果溢出。// 错误示例n和a都可能是10^5sum可能达到10^10超出int范围。 int n, a, sum 0; cin n; for(int i0; in; i) { cin a; sum a; } // 正确做法 int n, a; long long sum 0; // 使用 long long cin n; for(int i0; in; i) { cin a; sum a; }浮点数精度尽量避免直接比较两个浮点数是否相等。由于二进制表示误差应判断它们的差的绝对值是否小于一个极小值如1e-9。double a, b; // 错误 if (a b) ... // 正确 if (fabs(a - b) 1e-9) ...4.2 调试与测试策略先小后大写完代码后不要直接用题目给的大样例测试。先自己构造几个极小的、手算能知道答案的测试用例。比如边界情况n0 n1 数组全为正数、全为负数、有正有负等。这能快速发现逻辑错误。输出中间变量在怀疑出错的代码段前后打印出关键变量的值。比赛结束后记得注释掉这些调试输出。对拍对于不确定的题目如果你能写出一个绝对正确但很慢的暴力算法用于小数据范围可以写一个脚本随机生成小数据分别用你的“优化算法”和“暴力算法”跑对比结果。这是检验算法正确性的终极武器。虽然比赛时不一定有时间写对拍脚本但备赛时这是极好的练习。4.3 心态与时间管理卡题时的策略如果一道题思考超过30分钟毫无头绪或者调试超过20分钟找不到bug果断暂时放弃。做上标记跳过去做下一题。很多时候在做其他题的过程中大脑会在后台思考之前的问题可能会突然产生灵感。死磕一道题是竞赛大忌。最后半小时不要尝试去开新的难题。应该1) 检查所有已做题目的输入输出格式是否符合要求2) 重新读一遍题目确认没有理解偏差3) 检查填空题的结果是否已正确填写到提交页面4) 确保代码中没有遗留的调试输出。回顾2019年的那场国赛具体的题目细节或许已经模糊但那种从审题、构思、编码到调试的完整思维训练以及从中总结出的经验教训才是比赛留给我的最宝贵财富。竞赛的目的不止于奖项更在于通过高强度的练习迫使自己系统性地掌握算法知识锻炼在压力下清晰思考、稳健编码的能力。这些能力在你日后解决任何复杂的工程问题时都将受益匪浅。希望这份结合了当年实战和后续反思的“题解”能帮你少走一些弯路更高效地享受算法竞赛的乐趣与挑战。
1. 项目概述一次深度复盘的价值最近整理硬盘翻到了2019年参加第十届蓝桥杯大赛软件类B组国赛的代码和笔记。时间过去几年但当时在赛场上的那种紧张感、解题时的思维碰撞以及赛后复盘时的豁然开朗依然记忆犹新。蓝桥杯的题目尤其是国赛级别的从来都不是单纯考察语法它更像是一个综合能力的试金石将算法思维、代码实现、边界条件处理和临场应变能力熔于一炉。今天我想抛开官方题解那种“标准答案”式的叙述从一个参赛者和后来教学者的双重角度重新拆解这套C/C B组的国赛题目。我的目标不是简单地给出代码而是带你回到解题的“第一现场”分享我当时以及后来反思中的思考路径、遇到的坑以及那些比答案本身更重要的解题“元技能”。无论你是正在备赛的选手还是对算法竞赛感兴趣的开发者希望这份带着“体温”和“教训”的复盘能给你带来一些不一样的启发。2. 整体赛题分析与解题策略定调拿到一套竞赛题尤其是像蓝桥杯国赛这种五个小时五道题的赛制第一步绝对不是埋头就写。这五个小时是战略资源如何分配直接决定了最终的成绩上限。2019年这套B组题整体上承袭了蓝桥杯一贯的风格前面有“送分”的基础题稳定军心中间有需要仔细琢磨的思维题拉开差距最后则是由真正考验算法功底和优化能力的硬核题来角逐顶级名次。2.1 题目难度梯度与时间规划我的策略通常是“三轮扫描法”。第一轮快速通读所有题目对每道题进行初步定级。以这套题为例第一题往往是结果填空或代码填空考察基本语法和简单逻辑。这类题目标志着“必须拿下且快速拿下”计划用时在15-20分钟内包括检查。中间题目如第二、三题复杂度开始提升可能涉及基础算法如模拟、搜索、简单DP或数学思维。这是得分的关键区也是区分中等和良好成绩的战场。每道题我会预留40-60分钟其中包含读题、构思、编码、测试和调试的时间。最后两题尤其是压轴题通常是动态规划、图论优化或复杂的数论问题。对于大多数B组选手目标不一定是AC完全正确而是尽可能拿到部分分数部分正确。我会预留至少1.5小时给最后两题优先保证有清晰思路的题目能写出正确代码对于难题则力求写出能过小数据范围的“暴力解”或思路正确的伪代码争取步骤分。这套2019年的题目印象中第一题是典型的“签到题”考察点可能在日期处理或者简单计算。第二、三题开始引入场景需要建模。第四、五题则明显需要算法知识储备。时间分配上我当时大致是题115分钟、题240分钟、题350分钟、题470分钟、题5剩余时间检查。这个规划不是死的需要根据实际解题情况动态调整。2.2 环境与工具的准备要点国赛现场提供标准的IDE如Dev-C但你的“软环境”同样重要。我强烈建议在赛前就形成自己固定的代码模板和调试习惯。头文件模板提前写好一个包含所有常用头文件iostream,cstdio,vector,algorithm,cmath等、常用宏定义如#define INF 0x3f3f3f3f和简短IO优化的模板文件。比赛开始第一件事就是把它贴进去这能节省大量时间并避免低级错误。调试技巧在竞赛环境中没有强大的图形化调试器printf/cout调试法就是你的王牌。我习惯在代码关键节点如循环开始/结束、函数调用前后输出关键变量的值。对于大数据量题目可以配合文件重定向进行测试。// 假设编译后的程序为main.exe输入数据在in.txt // 在命令行中执行 main.exe in.txt my_output.txt // 然后比较 my_output.txt 和标准答案数据范围分析这是决定算法选择的关键一步。题目描述中给出的数据范围如1 n 10^5直接告诉你暴力搜索O(n^2)是否可行。看到10^5这个量级O(nlogn)的算法如排序、优先队列通常是安全的而O(n^2)则极有可能超时。3. 核心题目逐题精讲与思维还原现在让我们回到具体的题目。由于无法直接重现原题我将基于常见的蓝桥杯国赛题型和当年题目的考察方向重构解题思路和核心实现。我会重点讲“为什么这么想”以及“如何避免踩坑”。3.1 典型签到题稳中求快的基石题目特征问题描述简单可能涉及日期计算、字符串处理、基础数论如质数判断、公约数或简单的逻辑推理。目标是快速、准确无误地拿到分。模拟题型与解法假设题目是“从2019年1月1日到2019年12月31日有多少天的年月日数字之和等于20”此为模拟题型非原题。思路解析这本质上是一个枚举题。数据量很小一年365天直接暴力遍历每一天是完全可行的。关键在于如何优雅地遍历日期。实现细节与避坑日期遍历自己处理每月天数注意闰年固然可以但更稳妥的方法是使用语言自带的日期库C11的chrono太复杂竞赛中常用ctime或者手动模拟。对于这种固定年份的手动模拟更直观。数字分解编写一个digitSum(int n)函数来计算一个整数各位数字之和。注意对于日期如“2019-05-09”我们需要计算20190509还是201959题目必须明确通常是指去掉分隔符后的数字和。这里容易产生歧义。边界检查起始和结束日期是否包含务必读清题目“从…到…”是闭区间还是开区间。#include iostream using namespace std; // 判断闰年 bool isLeapYear(int y) { return (y % 4 0 y % 100 ! 0) || (y % 400 0); } // 获取某年某月的天数 int daysOfMonth(int y, int m) { if (m 2) return isLeapYear(y) ? 29 : 28; if (m 4 || m 6 || m 9 || m 11) return 30; return 31; } // 计算数字各位之和 int digitSum(int num) { int sum 0; while (num) { sum num % 10; num / 10; } return sum; } int main() { int year 2019; int totalDays 0; for (int month 1; month 12; month) { int days daysOfMonth(year, month); for (int day 1; day days; day) { // 假设计算规则是 年月日 的各位数字和 int sum digitSum(year) digitSum(month) digitSum(day); if (sum 20) { totalDays; // 可以输出具体日期用于验证 // cout year - month - day endl; } } } cout totalDays endl; return 0; }注意蓝桥杯填空题通常只需要提交最终结果。在代码中最终输出前务必确认计算逻辑与题目要求百分百吻合。一个很好的习惯是用几个显而易见的例子验证你的digitSum函数和日期遍历逻辑。3.2 中等难度题建模与基础算法的应用题目特征问题场景稍复杂需要将文字描述抽象成数学模型并应用一种或多种基础算法。常见的有路径搜索DFS/BFS、简单动态规划、贪心选择、二分查找等。模拟题型与解法假设题目是“在一个N x M的网格中每个格子有不同数量的宝物。从左上角(1,1)出发每次只能向右或向下移动到达右下角(N,M)。求能收集到的宝物最大数量。”此为经典DP问题用于说明思路。思路解析这几乎是动态规划DP的入门模板题。因为移动方向受限只能向右或向下这意味着到达当前格子(i, j)的路径只能来自上方(i-1, j)或左方(i, j-1)。那么到达(i, j)所能获得的最大宝物数就等于max(从上方来的最大收益 从左方来的最大收益) 当前格子宝物数。状态定义与转移方程定义dp[i][j]为从(1,1)走到(i,j)能获得的最大宝物数。转移方程dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]边界处理对于第一行i1只能从左方来对于第一列j1只能从上方来。我们可以初始化dp[0][j]和dp[i][0]为负无穷或0具体看题意或者在代码中单独处理边界。实现与优化#include iostream #include vector #include algorithm using namespace std; int main() { int N, M; cin N M; vectorvectorint grid(N 1, vectorint(M 1, 0)); // 1-indexed vectorvectorint dp(N 1, vectorint(M 1, 0)); for (int i 1; i N; i) for (int j 1; j M; j) cin grid[i][j]; // DP过程 for (int i 1; i N; i) { for (int j 1; j M; j) { if (i 1 j 1) { dp[i][j] grid[i][j]; // 起点 } else if (i 1) { dp[i][j] dp[i][j-1] grid[i][j]; // 第一行 } else if (j 1) { dp[i][j] dp[i-1][j] grid[i][j]; // 第一列 } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]) grid[i][j]; } } } cout dp[N][M] endl; return 0; }实操心得对于这类网格DP使用1-index下标从1开始可以大大简化边界条件的判断避免在dp[i-1]时出现负数下标。另外如果网格非常大比如N,M 500需要考虑空间优化因为dp[i][j]只依赖于上一行和当前行可以用滚动数组将空间复杂度从O(N*M)降到O(M)。3.3 压轴难题高级算法与优化策略题目特征数据规模大暴力法必然超时。需要运用较高级的算法或数据结构如树状数组/线段树、复杂DP状压DP、数位DP、图论算法最短路、最小生成树、网络流、高级搜索A*、IDA*等。解题的关键在于识别问题本质。模拟题型与解法假设题目是“有N个任务每个任务有开始时间Si和结束时间Ei以及收益Pi。选择若干个互不重叠的任务使得总收益最大。求最大收益。”此为经典的活动选择加权问题可用DP二分优化。思路解析如果N很小20可以用状态压缩枚举所有子集。但国赛数据N往往在10^5级别必须优化。第一步排序。将所有任务按结束时间Ei升序排序。这样当我们考虑第i个任务时所有结束时间小于等于Si的任务都已经考虑过了。第二步定义状态。设dp[i]表示考虑前i个任务按结束时间排序后能获得的最大收益。第三步状态转移。对于任务i有两种选择不选i则dp[i] dp[i-1]选i则需要找到最后一个结束时间小于等于Si的任务j。那么dp[i] dp[j] Pi。 因此dp[i] max(dp[i-1], dp[j] Pi)。第四步高效查找j。在排序后的数组中寻找最大的j使得E[j] S[i]。这是一个二分查找问题。我们可以预处理一个数组prev[i]来存储这个j或者直接在转移时进行二分查找。关键实现#include iostream #include vector #include algorithm using namespace std; struct Task { int start, end, profit; }; int main() { int N; cin N; vectorTask tasks(N); for (int i 0; i N; i) { cin tasks[i].start tasks[i].end tasks[i].profit; } // 按结束时间排序 sort(tasks.begin(), tasks.end(), [](const Task a, const Task b) { return a.end b.end; }); vectorint dp(N, 0); vectorint endTimes(N); // 用于二分查找 for (int i 0; i N; i) { endTimes[i] tasks[i].end; } dp[0] tasks[0].profit; // 初始化第一个任务 for (int i 1; i N; i) { // 不选当前任务 int profit1 dp[i-1]; // 选择当前任务需要找到最后一个结束时间 tasks[i].start 的任务索引 j int j -1; // 手动二分查找 int left 0, right i - 1; while (left right) { int mid left (right - left) / 2; if (tasks[mid].end tasks[i].start) { j mid; left mid 1; // 尝试找更靠后的 } else { right mid - 1; } } int profit2 tasks[i].profit; if (j ! -1) { profit2 dp[j]; } dp[i] max(profit1, profit2); } cout dp[N-1] endl; return 0; }深度剖析这道题的核心优化点有两个。第一是排序将问题转化为线性DP第二是二分查找将寻找兼容任务的时间从O(n)降为O(logn)从而使整体复杂度达到O(nlogn)才能应对大数据。在竞赛中能否快速识别出“排序后具有某种单调性从而可以使用二分或指针优化”是解决难题的关键能力之一。4. 竞赛实战中的通用技巧与“避坑”指南解题思路固然重要但在紧张的竞赛环境中如何少犯错、高效调试、管理心态往往更能决定最终排名。4.1 输入输出与数据类型的陷阱输入格式蓝桥杯题目输入有时很“灵活”可能在一行也可能分多行。务必使用最鲁棒robust的读入方式。cin在读取数字时会自动跳过空白字符空格、换行通常比较安全。但对于需要读取整行字符串再解析的建议使用getline(cin, str)。数据范围与溢出这是新手和老手都会翻车的地方。看到计算结果可能很大时第一时间问自己用int够吗对于涉及乘法、累加的场景10^5个10^5的数相加就会超出int范围约21亿。稳妥起见如果题目数值可能超过10^9或者你心里没底直接使用long long(int64_t)。在C中常量后面加LL如1LL * a * b来强制提升运算类型为long long防止中间结果溢出。// 错误示例n和a都可能是10^5sum可能达到10^10超出int范围。 int n, a, sum 0; cin n; for(int i0; in; i) { cin a; sum a; } // 正确做法 int n, a; long long sum 0; // 使用 long long cin n; for(int i0; in; i) { cin a; sum a; }浮点数精度尽量避免直接比较两个浮点数是否相等。由于二进制表示误差应判断它们的差的绝对值是否小于一个极小值如1e-9。double a, b; // 错误 if (a b) ... // 正确 if (fabs(a - b) 1e-9) ...4.2 调试与测试策略先小后大写完代码后不要直接用题目给的大样例测试。先自己构造几个极小的、手算能知道答案的测试用例。比如边界情况n0 n1 数组全为正数、全为负数、有正有负等。这能快速发现逻辑错误。输出中间变量在怀疑出错的代码段前后打印出关键变量的值。比赛结束后记得注释掉这些调试输出。对拍对于不确定的题目如果你能写出一个绝对正确但很慢的暴力算法用于小数据范围可以写一个脚本随机生成小数据分别用你的“优化算法”和“暴力算法”跑对比结果。这是检验算法正确性的终极武器。虽然比赛时不一定有时间写对拍脚本但备赛时这是极好的练习。4.3 心态与时间管理卡题时的策略如果一道题思考超过30分钟毫无头绪或者调试超过20分钟找不到bug果断暂时放弃。做上标记跳过去做下一题。很多时候在做其他题的过程中大脑会在后台思考之前的问题可能会突然产生灵感。死磕一道题是竞赛大忌。最后半小时不要尝试去开新的难题。应该1) 检查所有已做题目的输入输出格式是否符合要求2) 重新读一遍题目确认没有理解偏差3) 检查填空题的结果是否已正确填写到提交页面4) 确保代码中没有遗留的调试输出。回顾2019年的那场国赛具体的题目细节或许已经模糊但那种从审题、构思、编码到调试的完整思维训练以及从中总结出的经验教训才是比赛留给我的最宝贵财富。竞赛的目的不止于奖项更在于通过高强度的练习迫使自己系统性地掌握算法知识锻炼在压力下清晰思考、稳健编码的能力。这些能力在你日后解决任何复杂的工程问题时都将受益匪浅。希望这份结合了当年实战和后续反思的“题解”能帮你少走一些弯路更高效地享受算法竞赛的乐趣与挑战。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
