当前位置: 首页 > news >正文

CSP-J 第二轮集训 :总结 + 专题细分精讲_from_黄老师

CSP-J 第二轮集训资料 总结 + 专题细分精讲
为方便查阅,采用「总-分」结构:

  1. 先用一张 思维导图级总表 让你 30 秒看清全局;
  2. 对专题资料做 “三维”剖析
    • 知识脉络(思维导图)
    • 典型题目(含算法/陷阱/复杂度)
    • 可迁移的“套路模板”与易错点

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

③ 可迁移套路

  • 二分答案三板斧
    1. 确定 check(mid) 含义
    2. 证明单调性
    3. 处理边界 l, r 开闭
  • 贪心证明两板斧
    1. 交换邻项证不差
    2. 数学不等式(排序不等式、均值不等式)

📗 搜索

① 知识脉络

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
  • 状态压缩三问
    1. 哪些信息必须记录?
    2. 能否用位掩码?
    3. 能否预处理子集转移?

📒 图论

① 知识脉络

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

③ 可迁移套路

  • 分层图万能公式
    当状态 = (位置, 模意义下时间/资源) 直接多开一维。
  • 树链剖分两问
    1. 要路径查询还是子树查询?
    2. 线段树维护值还是标记?

📙 贪心

① 知识脉络

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 排序不等式 树状数组

③ 可迁移套路

  • 反悔贪心模板
    1. 按某关键字排序
    2. 用堆维护已选集合
    3. 若新元素更优则 pop 旧再 push 新,累加差值
  • 差分约束建图三步
    1. 不等式转 u-v≤c
    2. 连边 v→uc
    3. 跑最短路判负环

3️⃣ 如何把这些专题吃透吃干抹净

阶段 目标 推荐做法 时间预算
赛前 2 周 模板熟练度 100% 每份资料挑 3 题限时 30 min 敲完 每天 2 h
赛前 1 周 查漏补缺 重做曾经 WA 过的题,写“错题本” 每天 1 h
赛前 3 天 思维保温 只看题想思路,不写代码,保持手感 每天 30 min

4️⃣ 一句话带走

“基础算法保 80,搜索抢 10 分,DP 图论贪心冲满分。”
把上述五份专题资料按“模板 → 错题 → 思维”三遍刷完,CSP-J 第二轮就是考场上最稳的靓仔。祝 RP++!

http://www.hskmm.com/?act=detail&tid=25593

相关文章:

  • ROIR 2024
  • 软件工程第一次随笔 - Nicholas
  • 深入解析:【数据库】关系数据库标准语言-SQL(金仓)下
  • Codeforces Round 1056 (Div. 2) (4/6)
  • 20251006
  • UV使用
  • 动手实验——mybatis generator
  • 学生管理系统面向对象分析报告
  • 荷兰青少年通过Telegram被招募,涉嫌参与俄罗斯支持的黑客活动
  • Moscow International Workshops 2017. Day 4. Lviv NU Contest, GP of Ukraine
  • 小代码使用npm包的方法
  • day18 课程(模块 )
  • Kubernetes(K8s)核心架构解析与实用命令大全 - 教程
  • mzoj 2025/10/6
  • 实验作业1-8 陆绎
  • 全源最短路 Johnson算法
  • 《对象创建的秘密:Java 内存布局、逃逸分析与 TLAB 优化详解》 - 实践
  • go get net/http connections count, using middleware
  • win11开机后卡死,磁盘c盘占用100%,解决方案
  • 跨越国度 解题报告
  • 手写Promise核心代码
  • 手动数据库分库分片策略
  • 大数据分析公司季度业绩与技术进展
  • tmux 终端复用器教程,创建一个持久的会话
  • 理解Transformer中的位置编码
  • 网络风险管理的三大关键洞察
  • 牛客 周赛110 20251007
  • Python列表初始化的陷阱:重复引用的坑
  • MongoDB
  • 实用指南:第三十三天打卡复习