蓝桥杯Python组国赛复习计划

好吧，上周末本来以为是最后一战了，还写了一篇退役感想大模型时代，手搓代码还有什么意义？，结果忽然入围了国赛。

犹豫很久，还是决定冲一把。虽然国考、创赛项目和专业课已经压得我有些透不过气，但我还是觉得需要给最后的机会一个交代。所以，好好复习吧，这回真是最后一战了。

考虑到目前的准备状态，接下来大约一个月时间，每天写复习和刷题记录。优先掌握国赛常考且模板相对固定的模块，对于过难或极偏的内容果断跳过。

详细计划

DP强化（树形DP + 区间DP + 状态压缩DP）

1. 树形DP（2天）

• 基础：树的存储（邻接表）、DFS后序遍历。
• 经典模型：
• 树的最大独立集（没有上司的舞会）
• 树的最小点覆盖（监控树）
• 树形背包（例如在树上选k个节点，子树合并）

2. 区间DP（1.5天）

• 核心思想：枚举区间长度，逐步扩大。
• 经典模型：
• 石子合并（最小/最大代价）
• 括号匹配（最长有效括号）
• 回文串分割

3. 状态压缩DP（2.5天）

• 核心：用二进制位表示集合状态，如dp[mask][i]。
• 经典模型：TSP（旅行商问题）

高级数据结构与字符串

1. 线段树（2.5天）

• 核心操作：区间修改（加/赋值）、区间查询（和、最值）。
• 必会：
• 建树、单点更新、区间查询
• 懒标记（区间加/区间赋值）

2. 字典树（Trie）（1天）

• 核心：多模式串存储、前缀查询。
• 经典应用：
• 统计前缀出现次数
• 最大异或对（将整数二进制插入Trie）

3. KMP（1.5天）

• 核心：next数组（部分匹配表），字符串匹配。
• 重点：
• 手写get_next函数
• 理解匹配过程

图论进阶

1. 并查集（1天）

• 基础：路径压缩+按秩合并
• 扩展：
• 带权并查集（食物链）
• 并查集维护集合大小、集合到根距离

2. 图论最短路与拓扑排序（2天）

• Dijkstra（堆优化）：必会，O((n+m) log n)
• Floyd：三重循环，适用于n≤200
• 拓扑排序：Kahn算法（入度队列），用于判断环、求最优顺序
• 模板题：
• 洛谷P4779 单源最短路（Dijkstra）
• 洛谷P1347 排序（拓扑排序）

3. 滑动窗口/双指针（1天）

• 核心：维护窗口内满足条件，左指针右移缩小。
• 经典问题：
• 最长无重复子串
• 最小覆盖子串
• 定长窗口的和/最值

4. 贪心策略进阶（1天）

• 区间贪心：
• 最多不相交区间（按右端点排序）
• 区间选点（按右端点排序，取右端点）
• 区间覆盖（按左端点排序）
• 任务调度：
• 单机调度（按截止时间排序）
• 多机调度（LPT贪心）

数学进阶

1. 数学进阶（0.5天）

• 基础：复习扩展欧几里得、乘法逆元
• 扩展：“求逆元”和“组合数取模”

2. 数学综合（0.5天）

• 欧拉筛与欧拉函数
• “可见点数”或“互质对”问题
• 中国剩余定理（CRT）

3. 博弈论（0.5天）

• Nim 博弈、SG 函数（Sprague-Grundy）

4. 数学推演（1.5天）

• 高斯消元、行列式计算、莫比乌斯反演

规划

1. 必须掌握：树形DP、状压DP、KMP、Dijkstra堆优化、快速幂与逆元。区间DP、字典树、SPFA判负环、欧拉函数。
2. 有时间再看：字符串哈希、最小环、次短路、高级数论。
3. 保持手感：每天必须在LeetCode或洛谷随机一道中等难度的题