# CSP-S 第一轮（初赛）三年考点分析与一周冲刺方案（完整版） --- ## 第一部分：考试概况与得分策略 ### 1.1 试卷结构（2019年新赛制） | 部分 | 题量 | 分值 | 小计 | |---|---|---|---| | 一、单项选择 | 15题 | 2分/题 | 30分 | | 二、程序阅读理解 | 3题 | 判断题1.5分/题、选择题3分/题 | 40分 | | 三、完善程序 | 2题 | 10个空，3分/空 | 30分 | | **合计** | | | **100分，120分钟** | --- ### 1.2 三层得分结构与“过线思维” | 层级 | 分值目标 | 内容 | 策略 | |---|---|---|---| | 保底 | ~40分 | 常识题、基础单选（复杂度/数据结构概念/组合基础）、前两篇阅读程序 | 训练到**零失误** | | 目标 | ~30分 | 数据结构操作手算题、阅读选择题、完善程序前几空 | 限时稳定得分 | | 冲刺 | ~20–30分 | 每年最后一篇阅读、完善程序末空 | 战略取舍，不硬磕 | - **晋级线由各省自定**，省际差异大（近年大致从30分段到70分段），稳妥目标应定在**70分以上**。 - 判断题错答**不倒扣分**（以当年考场说明为准），**任何题不留空**。 - 完全陌生的算法先看分值：1.5分的判断题可标记跳过，3分/空的填空题必须回攻。 --- ### 1.3 考试形式与物品 - **确认本省是否机考**（部分省份已实行），以及具体考场、时间。 - 纸笔考试：2B铅笔×2、黑色签字笔×2、橡皮、准考证及身份证件。 - 120分钟分配：单选25分钟 + 阅读35分钟 + 填空30分钟 + **30分钟机动**（涂卡检查+回攻标记题）。 --- ## 第二部分：三年考点分布矩阵与明细 ### 2.1 考点类别 × 年份权重矩阵（分值为约估，以官方试卷为准） | 考点类别 | 2023 | 2024 | 2025 | 三年趋势 | |---|---|---|---|---| | 计算机常识 | 单选1题 | 单选1题 | 未见 | 连年小分，必保 | | 组合数学 | 单选1题 | 单选2题 | 单选2题 | 每年出现，难度递增↑ | | 复杂度与算法分析 | 单选3题 | 单选2题 | 单选2题 | **固定曲目** | | 数据结构 | 单选2题 | 单选3题 | 单选5题（10分） | **显著上升★** | --- | 考点类别 | 2023 | 2024 | 2025 | 三年趋势 | |---|---|---|---|---| | 图论 | 单选2题+填空15分 | 单选1题+填空15分 | 单选3题+填空15分 | 弱→**强势回归★** | | 字符串 | 单选1题（LCS） | — | 单选1题（KMP） | 新热点 | | DP/递归/贪心 | — | 阅读1篇 | 单选2–3题 | 稳定 | | 阅读程序算法 | 位运算/筛法/二分 | 递归/状压DP/树哈希 | 回溯/鸡蛋掉落/折半搜索 | **转向非模板★** | > 注：2024年图论收缩为单选1题（欧拉图）+完善程序次短路，并非完全缺席；2025年全线回归。 --- ### 2.2 各年明细 **2023年**：单选——mkdir、数字圆环排列、复杂度对比、哈夫曼、图染色、LCS、概率期望、位运算优先级、快排最坏、树重心、拓扑删边、不动点、斐波那契复杂度；阅读——位运算扰动、埃氏筛、二分框架；完善——k小路径（Dijkstra+状压）、子序列和分治。 **2024年**：单选——pwd、复杂度、栈溢出、颁奖组合、队列FIFO、递推计算、欧拉图、二分条件、乘法逆元、哈希冲突、路径方案数、交换次数、数字和函数、位运算；阅读——递归排序、状压DP、树哈希与欧拉序；完善——序列合并二分优化、次短路（双维度优先队列）。 **2025年**：单选——插空法、KMP next、线段树区间查询、Trie计数、拓扑方案数、哈希线性探查、MST、BST后序重建前序、0-1背包、LCA、主定理、最小堆delete-min、容斥、DP vs朴素递归、贪心调度；阅读——DFS排列计数、鸡蛋掉落（分块优化）、折半搜索；完善——分层图最短路、生产线缺陷检测（组合计数+二进制编码）。 --- ### 2.3 高频必考“固定曲目”（策略：100%拿下） 1. **复杂度分析**（三年必考，2–6分）：大O比较、递归式、主定理 2. **组合计数**（三年必考且逐年升级）：环排列→组合计数→插空法+容斥 3. **数据结构手算**（三年必考）：哈夫曼→哈希冲突→五结构齐发 4. **最短路族**（完善程序三年连考）：Dijkstra→次短路→分层图 5. **阅读程序“算法识别+复杂度分析”**（三年必考） --- ## 第三部分：2025年命题趋势与2026年前瞻 ### 3.1–3.5 五大趋势 1. **数据结构权重显著提升**：从“概念辨析”转向“操作细节”（线段树最少节点访问数、Trie精确计数）。 2. **图论重回核心**：单选3道+完善15分，合计约21%。 3. **数学题从送分变区分**：插空法建模、容斥精确计数、主定理判断。 4. **阅读程序引入非模板算法**：考“算法识别与复杂度分析”，不考“模拟算结果”。 5. **整体难度略降、范围扩大**：KMP、线段树等冷门回归，**覆盖面比深度更重要**。 --- ### 3.6 趋势风险提示（新增） - **“难度下降”不可外推**：范围扩大可能延续，难度可能回升。备考按“范围”准备，不押注难度。 - **完善程序考点轮动**：最短路族已连考三年，下一年可能转向**DP类（背包/区间/树形）、字符串类或贪心构造**，需提前覆盖。 - **冷门回归候选清单**：树状数组、ST表、单调栈/单调队列、**表达式求值（栈应用，历史高频）**、字符串哈希、二分图染色判定、博弈论（Nim异或和）、链表与循环队列操作。 - **图论热度大概率延续**：2025年回归后次年通常惯性出题，二分答案、图的遍历细节要熟。 --- ## 第四部分：知识点速查卡（考前一页纸） ### 4.1 计算机常识 - **Linux**：mkdir/rmdir、ls（-l -a）、cd、cp/mv/rm（-r递归）、cat、pwd、touch、chmod（r=4 w=2 x=1，755=rwxr-xr-x）；编译运行：`g++ a.cpp -o a` → `./a` - **编码**：'0'=48，'A'=65，'a'=97，大小写差32；UTF-8变长1–4字节 - **数据范围**：int 4字节 [-2³¹, 2³¹−1]≈2.1×10⁹；unsigned int≈4.2×10⁹；long long 8字节≈9.2×10¹⁸ - **存储计算**：图像=宽×高×位深÷8；音频=采样率×量化位数×声道×秒÷8 - **进制**：1位十六进制=4位二进制；1KB=1024B - **语言**：C/C++编译型，Python解释型，Java半编译（字节码+JVM）；编译流程：预处理→编译→汇编→链接 - **历史**：图灵（图灵机/图灵奖）、冯·诺依曼（存储程序）、香农（信息论/bit）、Dijkstra（最短路）；1946 ENIAC、1969 ARPANET - **进程/线程**：并发vs并行；死锁四条件（互斥、占有等待、不可剥夺、循环等待）(一般不考) --- ### 4.2 数据结构关键结论 | 结构 | 必记结论 | |:---:|---| | 哈夫曼 | n个叶子→**2n−1个节点**；n−1次合并；无度为1的节点；树形不唯一但**WPL唯一**；WPL=Σ权×深度 | | 堆 | 完全二叉树；数组存储（孩子2i、2i+1）；**建堆O(n)**，插/删O(log n)；delete-min=末元素换根后下滤 | | 哈希 | 线性探查(h+i)mod m会“堆积”；负载因子α=元素数/表长 | | Trie | 节点数=1+每词插入时“新建节点”数累加（公共前缀不重复建） | --- | 结构 | 必记结论 | |:---:|---| | BST | 中序遍历升序；插入序列定形状；**n个互异关键字由前序（或后序）序列唯一确定**；两序列重建须含中序 | | 线段树 | 空间4n；建O(n)；查询/修改O(log n)；“最少访问节点数”类题手画递归路径 | | 栈/队列 | 表达式求值（中缀转后缀）历史高频；循环队列判满/判空（留空位或计数器） | | 排序 | 稳定：冒泡/插入/归并/计数；不稳定：选择/快排/堆排；快排**已序最坏O(n²)**；归并需O(n)辅助 | --- ### 4.3 图论关键结论 - 完全图n(n−1)/2条边；树n−1条边、任意两点路径唯一、加一边恰成一环 - 欧拉回路：连通且**所有点度数为偶**；欧拉路径：恰两个奇度点；有向欧拉回路：每点入度=出度 - 拓扑排序仅DAG有；**方案数DP：f[v]=Σf[u]（沿入边），源点初值1** - Dijkstra不能负权，堆优化O(m log n)；Floyd O(n³)多源；**分层图最短路=状态扩展：dist[点][状态]** - MST：Kruskal O(m log m)+并查集；Prim O(n²)/O(m log n)；树形不唯一但总权唯一 - 二分图判定=无奇环，染色法；树重心：最大子树≤⌊n/2⌋ - DFS/BFS遍历O(n+m) --- ### 4.4 组合数学公式 - 环排列(n−1)!；**插空法**：k个不相邻→先排其余n−k个，插n−k+1个空，A(n−k+1,k)×(n−k)! - **隔板法**：正整数解C(n−1,m−1)；非负整数解C(n+m−1,m−1) - **容斥**：不被a、b、c整除的个数=N−⌊N/a⌋−⌊N/b⌋−⌊N/c⌋+⌊N/ab⌋+⌊N/ac⌋+⌊N/bc⌋−⌊N/abc⌋ - ΣC(n,k)=2ⁿ；重复元素排列n!/(a!b!…) - 卡特兰数Cₙ=C(2n,n)/(n+1)：出栈序列、括号方案、n节点二叉树形态 - 错排D₁=0，D₂=1，Dₙ=(n−1)(Dₙ₋₁+Dₙ₋₂) --- ### 4.5 主定理与复杂度 T(n)=aT(n/b)+f(n)，记E=log_b a： | 情形 | 条件 | 结论 | |---|---|---| | 1 | f(n)=O(n^(E−ε)) | T(n)=Θ(n^E) | | 2 | f(n)=Θ(n^E) | T(n)=Θ(n^E·log n) | | 3 | f(n)=Ω(n^(E+ε))且正则条件 | T(n)=Θ(f(n)) | 常备例：归并2T(n/2)+n→n log n；二分T(n/2)+1→log n；4T(n/2)+n→n²；T(n/2)+n→n。 **手算专项清单**（每类练3–5题，性价比最高）：KMP next手算、哈夫曼构造+WPL、堆建/插/delete-min、哈希线性探查落位、Trie节点计数、BST前后序互推、拓扑方案数DP、容斥计数、主定理五式判断、Kruskal/Prim表格模拟、二分查找l/r/mid变化、3¹⁰ mod 7类快速幂。 --- ## 第五部分：题型作答方法论 ### 5.1 单项选择 - 先看选项反推考点；计算题列出完整算式不心算跳步；组合题先判断用哪个模型（排列/组合/插空/隔板/容斥）。 --- ### 5.2 程序阅读理解（40分，得分大头） **三步法**：① 先读小题，明确问什么 → ② 扫代码识别“算法指纹” → ③ 只在小数据上手工模拟相关片段（不通读逐行算）。 --- **算法指纹速查表**： | 代码特征 | 算法 | |---|---| | priority_queue + dis数组 + 松弛 | 堆优化Dijkstra | | nxt/fail数组 + j回跳 | KMP | | 递归分两半 + 合并求答案 | 二分/折半搜索（meet in the middle） | | 枚举子集s（位运算）+ f[s] | 状压/子集DP | | x&(-x)、__builtin_popcount | lowbit/二进制计数 | --- | 代码特征 | 算法 | |---|---| | 入度数组 + queue | 拓扑排序（Kahn） | | while(l<r)+中点验证 | 二分答案 | | memo数组+递归 | 记忆化搜索 | | 递归+恢复现场 | 回溯 | | 边排序+并查集合并 | Kruskal | | 逐层queue扩展+vis | BFS | --- **数据范围反推复杂度**： | n范围 | 推断 | |---|---| | ≤12 | O(n!)暴力枚举 | | ≤20–26 | O(2ⁿ)状压或折半搜索 | | ≤100–500 | O(n³) | | ≤5000 | O(n²) | | ≤10⁵–10⁶ | O(n log n) | | ≥10⁷ 或 10¹⁸ | O(1)公式/数学结论 | **陷阱清单**：位运算优先级**低于比较运算**（`x&3==1`实为`x&(3==1)`）；int溢出与`mid=(l+r)/2`写法；下标从0还是1；`<`与`<=`边界；短路求值副作用；递归无出口→栈溢出；unsigned回绕；负数取模符号。 --- **判断题 vs 选择题**：判断题——构造小反例（n=0/1、全同元素等极端情况优先）；选择题——代入选项+排除法，“最坏情况”类题构造极端数据。 --- ### 5.3 完善程序（30分） **四类高频空**：①初始化/边界 ②DP/转移语句 ③循环范围/条件 ④统计与输出。 **五步流程**：通读主函数→标注变量含义（卷面上写中文）→先确定“程序在算什么”→逐空定性（属于四类中的哪类）→回代入上下文验证。 **选项排除法**：类型不符、正负号方向、边界开闭、`<=`与`<`、i/j混用先排除；再核对代码风格一致性。 **范例思路**：2025分层图最短路——识别“状态扩展”骨架（dist[节点][状态]二维），填空围绕状态转移和优先队列比较函数展开。 --- ## 第六部分：一周冲刺计划（量化版） ### 6.1 总览 | 天 | 主题 | 核心任务 | 产出 | |---|---|---|---| | D1 | 数据结构手算日 | 速查卡4.2各结构手算各3题；2023真题1套（120分钟） | 错题归因表 | | D2 | 图论+字符串日 | 拓扑方案数×2、Kruskal/Prim×2、Dijkstra×1、KMP next×3；2024真题1套 | 错题归因表 | | D3 | 数学专项日 | 主定理5题、容斥3题、插空/隔板/插空法各3题、逆元与快速幂2题；2025真题1套 | 错题归因表 | | D4 | 阅读程序专项日 | 三年阅读程序按“指纹法”重做；加做2道NOIP旧题 | 识别速度自测 | --- | 天 | 主题 | 核心任务 | 产出 | |---|---|---|---| | D5 | 完善程序专项+模拟① | 三年6道完善程序重走五步流程；模拟题1套 | 模拟分数 | | D6 | 模拟②+错题回顾 | 模拟1套；通刷错题归因表全部条目 | 模拟分数 | | D7 | 轻量复习 | 只过错题本+速查卡+易错点，不做新题，早睡 | — | > 每天固定30分钟小题手感：常识2题+组合1题+复杂度1题（从历年真题/模拟中抽取）。 > 若真题已做过，将真题前移，D5–D6改用CSP-J真题（练速度）或各省初赛模拟卷。 --- ### 6.2 错题归因表模板（每天30分钟） | 题号 | 考点 | 错因（勾选） | 补救动作 | 回顾时间 | |---|---|---|---|---| | | | 知识盲区 / 手算失误 / 审题偏差 / 时间不够 | | D几晚上 | --- ### 6.3 考前与考场执行清单 - **考前一天**：确认考场/时间/机考与否；只复习卡片，22:30前休息 - **开考**：先写姓名考号；做完一个部分**立即涂卡** - **中盘**：难题标记跳过，判断题不留空 - **最后30分钟**：20分钟回攻标记题 + 10分钟核对答题卡与漏题 --- ## 第七部分：资源清单 - **OI Wiki**（oi-wiki.org）：知识点权威查阅，重点看主定理、数据结构各条目的“应用”小节 - **洛谷题库**：搜“CSP-S 初赛”（2019–2025真题）、“NOIP初赛”（2015–2018，题型接近、考点重合度高） - 各省初赛模拟卷（赛前1–2周各机构会出，选2–3套即可）