CSP-J 第二轮集训资料 总结 + 专题细分精讲。
为方便查阅,采用「总-分」结构:
- 先用一张 思维导图级总表 让你 30 秒看清全局;
- 对专题资料做 “三维”剖析:
- 知识脉络(思维导图)
- 典型题目(含算法/陷阱/复杂度)
- 可迁移的“套路模板”与易错点
1️⃣ 总体速览
专题 | 核心定位 | 难度曲线 | 关键词 10 秒版 |
---|---|---|---|
基础算法 | 第一轮补漏 + 第二轮提速 | J 组 80 → 100 分 | 二分、前缀和、贪心证明、数论拆分、模拟 |
搜索 | 拿不到满分时的“救命分” | 暴力 → 记忆化 → 剪枝 | DFS 序、迭代加深、A*、双向广搜、数独 |
动态规划 | 第二轮真正拉差距的主战场 | 会模型 1 题 35 → 满分 | 状态压缩、单调队列、斜率优化、区间 DP |
图论 | 高频必考、模板必须熟 | 最短路 → 树链剖分 | dijkstra、拓扑、并查集、LCA、虚树 |
贪心 | 思维量最大、代码量最小 | 想到 5 分钟,想不到 5 小时 | 反悔堆、排序不等式、差分约束、Huffman |
2️⃣ 逐个专题精讲
📘 基础算法
① 知识脉络
graph TD
A[基础算法] --> B(复杂度分析)
A --> C(前缀/差分)
A --> D(二分答案)
A --> E(数学)
E --> E1(幂次拆分)
E --> E2(模运算)
A --> F(贪心)
F --> F1(证明套路)
② 典型题速览
题 | 考点 | 易错/陷阱 | 模板速记 |
---|---|---|---|
分糖果 | 剩余系贪心 | 余数分类讨论 | ans = max(R % n, L % n, (R-L+1)/n * n ? 0 : R % n) |
次大模数 | 去重 + 次大值 | 只考虑 a_i mod max_j |
set 维护候选 |
优秀拆分 | 2 的正整数次幂 | 1 不能出现 | n & (n-1) 判 2 的幂 |
快速幂警示 | 爆 int 边界 |
中途乘爆 | 边乘边判 -1 |
③ 可迁移套路
- 二分答案三板斧:
- 确定
check(mid)
含义 - 证明单调性
- 处理边界
l, r
开闭
- 确定
- 贪心证明两板斧:
- 交换邻项证不差
- 数学不等式(排序不等式、均值不等式)
📗 搜索
① 知识脉络
graph TD
A[搜索] --> B(DFS 序)
A --> C(剪枝)
C --> C1(最优性剪枝)
C --> C2(可行性剪枝)
A --> D(记忆化)
A --> E(迭代加深/IDA*)
A --> F(双向广搜)
② 典型题速览
题 | 搜索策略 | 剪枝/优化 | 记忆化状态 |
---|---|---|---|
牛奶桶 | 迭代加深 | 桶量只有 0/X/Y 三种有效值 | (x,y,step) |
windy 数 | 数位 DP | 差 ≥2 预处理 | pos, lead, last, tight |
奶酪空洞 | 三维连通性 | 并查集/DFS 均可 | 无 |
01 迷宫 | 连通块染色 | 颜色交替 BFS | color[x][y] |
③ 可迁移套路
- 迭代加深公式:
max_depth = 0 ... ∞
,每层限界f+g>h
剪掉。 - 双向广搜触发条件:
状态空间|S|≤1e6
且分支因子大,正反向各扩一半。
📕 动态规划(第二轮真正拉差距)
① 知识脉络
graph TD
A[DP] --> B(线性 DP)
A --> C(区间 DP)
A --> D(状态压缩)
A --> E(树形 DP)
A --> F(优化)
F --> F1(单调队列)
F --> F2(斜率优化)
F --> F3(四边形不等式)
② 典型题速览
题 | 状态设计 | 转移/优化 | 复杂度 |
---|---|---|---|
Luogu3842 平面序列 | f[i][k] 前 i 点加 k 个点的最长链 |
离散化 + 线段树 max | O((n+k) log n) |
CF2033D 美丽区间 | pre[i] 前缀和最早出现位置 |
贪心选不重叠 | O(n) |
CF1105C 和 mod3=0 | dp[i][0/1/2] 计数 |
滚动数组 | O(n) |
Luogu7074 方格取数 | f[i][j][k] 三进制状态 |
插头 DP | O(nm 3^m) |
③ 可迁移套路
- 区间 DP 万能模板
for len=1..n; for l=1..n-len+1; r=l+len-1; for k=l..r-1
- 状态压缩三问
- 哪些信息必须记录?
- 能否用位掩码?
- 能否预处理子集转移?
📒 图论
① 知识脉络
graph TD
A[图论] --> B(最短路)
B --> B1(Dijkstra)
B --> B2(SPFA 已死)
A --> C(生成树)
C --> C1(Kruskal)
C --> C2(Prim)
A --> D(拓扑排序)
A --> E(LCA)
E --> E1(倍增)
E --> E2(树链剖分)
A --> F(虚树)
② 典型题速览
题 | 算法核心 | 易错点 | 模板提示 |
---|---|---|---|
Luogu3243 菜肴拓扑 | 字典序最小拓扑 | 反图 + 优先队列 | 大根堆 |
Luogu9751 旅游巴士 | 分层图最短路 | 时间模 k 建图 | dist[u][t%k] |
Luogu5683 拆道路 | 双限制最短路 | 两次 Dijkstra 贪心删边 | 并查集维护 |
Luogu11855 子树加 | 树差分 | 入出时间戳 | dfs in/out |
③ 可迁移套路
- 分层图万能公式
当状态 = (位置, 模意义下时间/资源) 直接多开一维。 - 树链剖分两问
- 要路径查询还是子树查询?
- 线段树维护值还是标记?
📙 贪心
① 知识脉络
graph TD
A[贪心] --> B(排序贪心)
A --> C(反悔贪心)
C --> C1(堆)
C --> C2(链表合并)
A --> D(差分约束)
A --> E(Huffman)
A --> F(拟阵)
② 典型题速览
题 | 贪心策略 | 证明关键点 | 数据结构 |
---|---|---|---|
Luogu2512 糖果均分 | 环形均分 | 中位数最优 | 排序 |
Luogu2949 任务调度 | 截止期越早越先做 | 交换邻项 | 优先队列 |
Luogu2168 k 进制前缀 | Huffman 变种 | Kraft 不等式 | 多叉堆 |
Luogu6155 最小花费 | 先 swap 再贪心增 1 | 排序不等式 | 树状数组 |
③ 可迁移套路
- 反悔贪心模板
- 按某关键字排序
- 用堆维护已选集合
- 若新元素更优则
pop
旧再push
新,累加差值
- 差分约束建图三步
- 不等式转
u-v≤c
- 连边
v→u
权c
- 跑最短路判负环
- 不等式转
3️⃣ 如何把这些专题吃透吃干抹净
阶段 | 目标 | 推荐做法 | 时间预算 |
---|---|---|---|
赛前 2 周 | 模板熟练度 100% | 每份资料挑 3 题限时 30 min 敲完 | 每天 2 h |
赛前 1 周 | 查漏补缺 | 重做曾经 WA 过的题,写“错题本” | 每天 1 h |
赛前 3 天 | 思维保温 | 只看题想思路,不写代码,保持手感 | 每天 30 min |
4️⃣ 一句话带走
“基础算法保 80,搜索抢 10 分,DP 图论贪心冲满分。”
把上述五份专题资料按“模板 → 错题 → 思维”三遍刷完,CSP-J 第二轮就是考场上最稳的靓仔。祝 RP++!