1. 项目概述作为一名算法竞赛爱好者我最近在洛谷平台开启了为期30天的刷题挑战。今天要分享的是第六天的刷题实录主要涉及动态规划、图论和贪心算法的经典题型。不同于前五天的基础训练第六天的题目难度明显提升更考验对算法本质的理解和灵活运用能力。选择洛谷作为刷题平台有几个明显优势题目分类清晰、测试用例全面、社区讨论活跃。特别是每道题目的题解区经常能看到各路高手的不同解法这对拓宽解题思路非常有帮助。我的刷题策略是每天固定3-5道中等难度题目保证每道题都吃透原理而不是单纯追求数量。2. 刷题准备与环境配置2.1 开发环境搭建我使用的开发环境是VS Code C17标准配合Competitive Companion插件实现一键抓题。这个组合的优势在于代码补全和错误检查功能完善插件自动生成题目模板和测试用例支持一键提交和结果反馈配置要点包括安装MinGW-w64作为编译器配置tasks.json实现编译运行快捷键设置代码片段模板如快速生成头文件注意竞赛编程与工程开发不同通常需要关闭同步流以提升IO速度。我的常用配置是ios::sync_with_stdio(false); cin.tie(nullptr);2.2 刷题方法论经过前五天的实践我总结出一套有效的刷题流程理解题意至少读题3遍用自己语言复述问题确定算法根据题目特征匹配算法类型如看到最优化考虑DP手写测试在纸上模拟小规模案例代码实现先写伪代码再填充细节调试优化针对特殊边界条件测试特别重要的是建立错题本记录每道错题的错误原因逻辑/边界/复杂度正确解法思路同类题目链接3. 今日刷题实录3.1 动态规划专题P1048 采药这道经典DP题实质是0-1背包问题的变种。药材对应物品时间限制对应背包容量。我的解题过程状态定义dp[i][j]表示前i株药材在j时间内的最大价值转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-time[i]] value[i])空间优化使用滚动数组将空间复杂度从O(NM)降到O(M)踩坑记录初始化为-INF而不是0允许时间不满第二层循环需要倒序遍历防止重复计算药材编号从1开始更符合直觉最终AC代码的关键部分vectorint dp(T1); for(int i1; iM; i){ for(int jT; jt[i]; --j){ dp[j] max(dp[j], dp[j-t[i]] v[i]); } }3.2 图论实战P3371 单源最短路径这道题要求实现Dijkstra算法但有几点需要注意数据规模较大n≤1e4邻接表存储更优需要处理重边情况使用优先队列优化时间复杂度我的实现步骤链式前向星建图小根堆维护待处理节点松弛操作时判断距离更新性能优化技巧使用pairint,int时默认按first排序提前判断if(dis[u]d) continue节省时间输入使用快速读入函数实测对比普通队列实现500ms堆优化后仅120ms3.3 贪心算法P1223 排队接水这道题展示了贪心算法的典型特征局部最优导致全局最优。解题关键在于发现短任务优先的规律。数学证明 设两个任务时间分别为t1和t2且t1t2顺序1→2等待时间t1 (t1t2)顺序2→1等待时间t2 (t2t1) 显然第一种顺序更优实现细节使用结构体数组保存原始序号自定义排序函数按时间升序计算前缀和得到总等待时间易错点平均数计算要用double类型输出格式要求保留两位小数序号从1开始但数组从0存储4. 调试技巧与性能分析4.1 常见错误排查在今天的刷题过程中遇到了几个典型错误段错误(Segmentation Fault)原因数组越界访问解决方法检查循环边界条件使用.at()方法捕获异常TLE(Time Limit Exceeded)案例Dijkstra未使用堆优化优化方案时间复杂度从O(V^2)降到O(ElogV)WA(Wrong Answer)调试方法构造极端测试用例如空输入、最大值边界4.2 性能分析工具推荐使用洛谷自带的测试点详情功能可以查看每个测试点的通过情况对比时间/内存消耗定位性能瓶颈对于本地测试我常用的方法g -O2 -stdc17 -o test test.cpp time ./test input.txt5. 算法学习资源推荐经过六天的刷题我发现这些资源特别有帮助书籍类《算法竞赛入门经典》- 刘汝佳《挑战程序设计竞赛》- 秋叶拓哉在线资源OI Wiki全面系统的算法百科CP-Algorithms英文版算法详解视频课程洛谷官方算法课Codeforces教育频道6. 明日刷题计划基于今日的经验明天计划巩固DP中的状态压缩技巧学习图论中的最小生成树算法尝试一道难度评级为「省选/NOI-」的题目具体题目选择P1433 吃奶酪状压DP经典P3366 【模板】最小生成树P1073 最优贸易图论综合题刷题过程中我会特别注意复杂度的预先计算状态转移的数学证明边界条件的全面考虑今天最大的收获是理解了贪心算法的证明方法——不是所有看似合理的贪心策略都正确必须通过严格的数学证明或反例验证。比如在接水问题中如果改为先处理等待时间长的任务就会得到错误结果。 
长河君 · 2026/11/4 3:07:39 · 阅读 1.2k 洛谷刷题实战：动态规划与图论算法精解
1. 项目概述作为一名算法竞赛爱好者我最近在洛谷平台开启了为期30天的刷题挑战。今天要分享的是第六天的刷题实录主要涉及动态规划、图论和贪心算法的经典题型。不同于前五天的基础训练第六天的题目难度明显提升更考验对算法本质的理解和灵活运用能力。选择洛谷作为刷题平台有几个明显优势题目分类清晰、测试用例全面、社区讨论活跃。特别是每道题目的题解区经常能看到各路高手的不同解法这对拓宽解题思路非常有帮助。我的刷题策略是每天固定3-5道中等难度题目保证每道题都吃透原理而不是单纯追求数量。2. 刷题准备与环境配置2.1 开发环境搭建我使用的开发环境是VS Code C17标准配合Competitive Companion插件实现一键抓题。这个组合的优势在于代码补全和错误检查功能完善插件自动生成题目模板和测试用例支持一键提交和结果反馈配置要点包括安装MinGW-w64作为编译器配置tasks.json实现编译运行快捷键设置代码片段模板如快速生成头文件注意竞赛编程与工程开发不同通常需要关闭同步流以提升IO速度。我的常用配置是ios::sync_with_stdio(false); cin.tie(nullptr);2.2 刷题方法论经过前五天的实践我总结出一套有效的刷题流程理解题意至少读题3遍用自己语言复述问题确定算法根据题目特征匹配算法类型如看到最优化考虑DP手写测试在纸上模拟小规模案例代码实现先写伪代码再填充细节调试优化针对特殊边界条件测试特别重要的是建立错题本记录每道错题的错误原因逻辑/边界/复杂度正确解法思路同类题目链接3. 今日刷题实录3.1 动态规划专题P1048 采药这道经典DP题实质是0-1背包问题的变种。药材对应物品时间限制对应背包容量。我的解题过程状态定义dp[i][j]表示前i株药材在j时间内的最大价值转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-time[i]] value[i])空间优化使用滚动数组将空间复杂度从O(NM)降到O(M)踩坑记录初始化为-INF而不是0允许时间不满第二层循环需要倒序遍历防止重复计算药材编号从1开始更符合直觉最终AC代码的关键部分vectorint dp(T1); for(int i1; iM; i){ for(int jT; jt[i]; --j){ dp[j] max(dp[j], dp[j-t[i]] v[i]); } }3.2 图论实战P3371 单源最短路径这道题要求实现Dijkstra算法但有几点需要注意数据规模较大n≤1e4邻接表存储更优需要处理重边情况使用优先队列优化时间复杂度我的实现步骤链式前向星建图小根堆维护待处理节点松弛操作时判断距离更新性能优化技巧使用pairint,int时默认按first排序提前判断if(dis[u]d) continue节省时间输入使用快速读入函数实测对比普通队列实现500ms堆优化后仅120ms3.3 贪心算法P1223 排队接水这道题展示了贪心算法的典型特征局部最优导致全局最优。解题关键在于发现短任务优先的规律。数学证明 设两个任务时间分别为t1和t2且t1t2顺序1→2等待时间t1 (t1t2)顺序2→1等待时间t2 (t2t1) 显然第一种顺序更优实现细节使用结构体数组保存原始序号自定义排序函数按时间升序计算前缀和得到总等待时间易错点平均数计算要用double类型输出格式要求保留两位小数序号从1开始但数组从0存储4. 调试技巧与性能分析4.1 常见错误排查在今天的刷题过程中遇到了几个典型错误段错误(Segmentation Fault)原因数组越界访问解决方法检查循环边界条件使用.at()方法捕获异常TLE(Time Limit Exceeded)案例Dijkstra未使用堆优化优化方案时间复杂度从O(V^2)降到O(ElogV)WA(Wrong Answer)调试方法构造极端测试用例如空输入、最大值边界4.2 性能分析工具推荐使用洛谷自带的测试点详情功能可以查看每个测试点的通过情况对比时间/内存消耗定位性能瓶颈对于本地测试我常用的方法g -O2 -stdc17 -o test test.cpp time ./test input.txt5. 算法学习资源推荐经过六天的刷题我发现这些资源特别有帮助书籍类《算法竞赛入门经典》- 刘汝佳《挑战程序设计竞赛》- 秋叶拓哉在线资源OI Wiki全面系统的算法百科CP-Algorithms英文版算法详解视频课程洛谷官方算法课Codeforces教育频道6. 明日刷题计划基于今日的经验明天计划巩固DP中的状态压缩技巧学习图论中的最小生成树算法尝试一道难度评级为「省选/NOI-」的题目具体题目选择P1433 吃奶酪状压DP经典P3366 【模板】最小生成树P1073 最优贸易图论综合题刷题过程中我会特别注意复杂度的预先计算状态转移的数学证明边界条件的全面考虑今天最大的收获是理解了贪心算法的证明方法——不是所有看似合理的贪心策略都正确必须通过严格的数学证明或反例验证。比如在接水问题中如果改为先处理等待时间长的任务就会得到错误结果。