L2~L3部分学习安排与计划
课程链接：戳这 <—（您的支持是我最大的动力！）
L2~L3 部分作为天梯赛国奖冲刺的核心模块，分为两个阶段进行，目标是实现L2 部分 80 分保底、L3 部分争取 30 分，为冲击个人国奖 175+ 分奠定关键基础。第一阶段聚焦图论优化与动态规划，第二阶段突破高级算法与应试策略，通过 “模板攻坚 + 真题拆解 + 模拟竞赛” 三阶训练，帮助学员达成复杂问题 90 分钟内构建解题框架的竞技能力。
第一阶段：L2进阶强化
一、最短路与图论优化
核心目标：掌握 Dijkstra 堆优化、Floyd 算法及路径还原技巧，解决带权图最短路径问题
理论学习：
- 图的存储方式介绍和对比（邻接矩阵 vs 邻接表）
- Dijkstra 堆优化模板（时间复杂度O ( m l o g n ) O(mlogn)O(mlogn)）
- Floyd 算法适用场景
代码训练：
- 实现邻接表存储图模板
- 编写 Dijkstra 堆优化模板（priority_queue 版）
真题实战：
- L2-036 网红点打卡攻略（25 分）：邻接矩阵存储图
- L2-001 紧急救援（25 分）：最短路径条数统计 + 救援队最大数量
二、最小生成树基础模型（Kruskal）
核心目标：掌握最小生成树基础思路，并且把代码实现
代码训练：
- 实现 Kruskal 算法（含路径压缩并查集）
- 完成最小生成树模板题
任务产出：
- 图论算法模板库（含注释）
- 真题解题报告 2 份
第二阶段：L3冲刺突破
一、动态规划与状态优化
核心目标：掌握 01 背包、完全背包及线性 DP 模型，提升复杂问题建模能力
理论学习：
- 动态规划两大要素（状态设计，转移方程）
- 背包问题空间优化（滚动数组，从二维到一维）
- 线性 DP 状态转移方程构建方法
代码训练：
- 实现 01 背包空间优化模板（滚动数组）
- 开发最长上升子序列 (LIS)O ( n 2 ) O(n^2)O(n2)解法
真题实战：
- L3-001 凑零钱（30 分）：背包变种 + 状态路径记录
任务产出：
- DP 问题分类笔记（含状态转移方程库）
- 空间优化前后代码对比分析
二、应试策略与骗分技巧
核心目标：掌握部分分获取策略、测试点分析方法，实现有限时间内分数最大化
理论学习：
- 题目难度预判三要素（数据范围 / 关键词 / 样例）
- 部分分获取常见手段（暴力剪枝 / 特殊情况处理）
- 比赛时间分配黄金比例（L 1 : L 2 : L 3 = 1 : 2 : 1 L1:L2:L3 = 1:2:1L1:L2:L3=1:2:1）
代码训练：
- 研究 L3 难题的部分分解法
- 尝试针对单测题输出特殊结果
真题实战：
- L2-008 最长对称子串（25 分）：用暴力解法和测试特殊点
- L2-056 被 n 整除的 n 位数（25 分）：用暴力解法获取部分分
任务产出：
- 骗分技巧手册（含代码模板）
- 个人限时模拟竞赛记录 3 份
常见问题解决方案
- 超时问题：
- 使用 map 进行离散化（平均O ( l o g n ) O(logn)O(logn)复杂度）
- DFS 中添加剪枝操作，避免重复计算
- 内存溢出：
- 全局数组改动态 vector（尤其N ∗ M = 10 5 N*M=10^5N∗M=105时）
- 能使用 BFS 尽量使用，减少 DFS 栈溢出现象
- 逻辑漏洞：
- 建立测试用例库（含边界情况：空输入、最大 N 值、极端数据）
- 采用 “自顶向下” 编程法，先写框架再填细节
特别提示：每天学习结束前，将 AC 代码整理好，命名格式为"日期_题目编号.cpp"，如"20231120_L2021.cpp"，方便之后复习。
课后习题安排
- 第六周：课后编程题六道
- 第七周：课后编程题四道