<!doctype html>
<html lang="zh-CN">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>近10年CSP-S(含NOIP提高组)初赛常考内容整理</title>
<link rel="icon" href="data:image/svg+xml,%3Csvg xmlns='http://www.w3.org/2000/svg' viewBox='0 0 64 64'%3E%3Crect width='64' height='64' rx='14' fill='%230f7b8c'/%3E%3Ctext x='32' y='44' font-size='34' text-anchor='middle' fill='%23fff' font-family='monospace'%3EC%3C/text%3E%3C/svg%3E">
<style>
:root{
--bg:#f5f7f9; --card:#ffffff; --ink:#1f2733; --muted:#5b6472;
--primary:#0f7b8c; --primary-soft:#e3f2f4; --accent:#e08a2e; --accent-soft:#fdf0df;
--line:#dfe5ea; --code-bg:#0f172a; --code-ink:#e2e8f0;
--radius:12px;
}
*{box-sizing:border-box}
html{scroll-behavior:smooth}
body{margin:0;background:var(--bg);color:var(--ink);
font-family:"Noto Sans SC","PingFang SC","Microsoft YaHei",system-ui,-apple-system,sans-serif;
line-height:1.75;font-size:15px}
h1,h2,h3,h4{line-height:1.35;margin:0 0 .5em}
p{margin:.5em 0}
a{color:var(--primary);text-decoration:none}
a:hover{text-decoration:underline}
.wrap{max-width:1080px;margin:0 auto;padding:0 20px}
/* 顶栏 */
.topbar{position:sticky;top:0;z-index:50;background:rgba(255,255,255,.94);backdrop-filter:blur(6px);
border-bottom:1px solid var(--line)}
.topbar .wrap{display:flex;align-items:center;gap:16px;height:56px;flex-wrap:wrap}
.brand{font-weight:800;color:var(--primary);white-space:nowrap}
nav{display:flex;gap:4px;overflow-x:auto;flex:1}
nav a{padding:6px 10px;border-radius:8px;color:var(--muted);font-size:13.5px;white-space:nowrap}
nav a:hover{background:var(--primary-soft);color:var(--primary);text-decoration:none}
/* Hero */
.hero{background:linear-gradient(135deg,#0f7b8c 0%,#124e63 100%);color:#fff;padding:36px 0 30px}
.hero h1{font-size:26px;margin-bottom:6px}
.hero .sub{opacity:.88;font-size:14px;max-width:820px}
.hero .tags{margin-top:12px;display:flex;gap:8px;flex-wrap:wrap}
.hero .tags span{background:rgba(255,255,255,.16);border:1px solid rgba(255,255,255,.25);
padding:3px 10px;border-radius:999px;font-size:12.5px}
/* 统计卡 */
.stats{display:grid;grid-template-columns:repeat(4,1fr);gap:14px;margin:20px 0 6px}
.stat{background:var(--card);border:1px solid var(--line);border-radius:var(--radius);padding:14px 16px}
.stat b{display:block;font-size:22px;color:var(--primary)}
.stat span{font-size:12.5px;color:var(--muted)}
/* 区块 */
section{padding:30px 0 6px}
.card{background:var(--card);border:1px solid var(--line);border-radius:var(--radius);
padding:20px 22px;margin:14px 0}
.sec-head{display:flex;align-items:center;gap:10px;margin-bottom:8px}
.sec-head .no{background:var(--primary);color:#fff;border-radius:8px;min-width:30px;height:30px;
display:flex;align-items:center;justify-content:center;font-weight:700;font-size:14px}
.sec-head h2{font-size:21px;margin:0}
.sec-head .en{color:var(--muted);font-size:12.5px}
/* 表格 */
table{width:100%;border-collapse:collapse;margin:10px 0;font-size:13.5px}
th,td{border:1px solid var(--line);padding:8px 10px;text-align:left;vertical-align:top}
th{background:#eef2f5;font-weight:600;white-space:nowrap}
tbody tr:nth-child(even){background:#fafbfc}
.tbl-scroll{overflow-x:auto}
/* 公式块 */
.formula{background:var(--primary-soft);border:1px solid #cde6ea;border-radius:10px;
padding:12px 16px;margin:12px 0;font-family:"Times New Roman","STIXGeneral",Georgia,serif;
font-size:16.5px;line-height:1.9;overflow-x:auto}
.formula .name{font-family:"Noto Sans SC",sans-serif;font-weight:700;color:var(--primary);
font-size:13px;display:block;margin-bottom:2px}
.formula.small{font-size:15px}
/* 要点卡 */
.kp{border-left:4px solid var(--primary);background:#f8fbfc;padding:10px 14px;margin:10px 0;border-radius:0 8px 8px 0}
.kp.warn{border-color:var(--accent);background:#fdf9f2}
.kp b{color:var(--primary)}
.kp.warn b{color:#b06a14}
.kp .tag{display:inline-block;background:var(--accent-soft);color:#b06a14;font-size:11.5px;
border-radius:6px;padding:1px 8px;margin-right:6px;white-space:nowrap}
/* 代码块 */
pre{background:var(--code-bg);color:var(--code-ink);border-radius:10px;padding:14px 16px;
overflow-x:auto;font-size:13px;line-height:1.65;position:relative;margin:12px 0;
font-family:"JetBrains Mono","SF Mono",Consolas,"Courier New",monospace}
pre .cap{display:block;width:calc(100% - 72px);color:#7dd3c8;font-size:12px;margin-bottom:8px;font-family:"Noto Sans SC",sans-serif}
code{font-family:inherit}
.copy-btn{position:absolute;top:8px;right:10px;background:rgba(255,255,255,.1);color:#cbd5e1;
border:1px solid rgba(255,255,255,.18);border-radius:6px;font-size:11.5px;padding:2px 8px;cursor:pointer}
.copy-btn:hover{background:rgba(255,255,255,.2)}
/* 图表 */
.chart-box{background:var(--card);border:1px solid var(--line);border-radius:var(--radius);
padding:16px;margin:14px 0}
.chart-box h3{margin:0 0 2px;font-size:16px}
.chart-box .cap{color:var(--muted);font-size:12.5px;margin-bottom:8px}
.chart{width:100%;height:360px}
.caption{color:var(--muted);font-size:12px;margin-top:8px}
/* 列表 */
ul,ol{margin:.4em 0;padding-left:1.4em}
li{margin:.25em 0}
.two{display:grid;grid-template-columns:1fr 1fr;gap:14px}
@media(max-width:820px){
.stats{grid-template-columns:repeat(2,1fr)}
.two{grid-template-columns:1fr}
.chart{height:320px}
body{font-size:16px}
table{font-size:13.5px}
.kp,ul,ol{font-size:15.5px}
pre{font-size:12.5px}
nav a{font-size:13px}
}
@media(max-width:480px){
.hero h1{font-size:21px}
.stats{grid-template-columns:1fr 1fr}
}
/* 真题索引 */
table.years td:first-child{white-space:nowrap;font-weight:600}
.tag-chip{display:inline-block;background:#eef4f6;border:1px solid #d8e5e9;color:#2a5c68;
border-radius:6px;padding:0 6px;margin:2px 3px 0 0;font-size:12px}
/* 参考 */
.refs{font-size:13px;color:var(--muted)}
.refs li{margin:.35em 0}
footer{background:#124e63;color:#cfe3e9;margin-top:40px;padding:22px 0;font-size:12.5px}
footer .wrap{display:flex;justify-content:space-between;gap:16px;flex-wrap:wrap}
</style>
</head>
<body>
<div class="topbar"><div class="wrap">
<div class="brand">CSP-S 初赛整理</div>
<nav>
<a href="#overview">考点总览</a>
<a href="#principles">选择题原理</a>
<a href="#math">数学公式</a>
<a href="#code">常考代码</a>
<a href="#years">真题索引</a>
<a href="#refs">参考资料</a>
</nav>
</div></div>
<div class="hero"><div class="wrap">
<h1>近10年 CSP-S(含 NOIP 提高组)初赛常考内容整理</h1>
<p class="sub">覆盖 2015–2025 年 NOIP 提高组初赛与 CSP-S 第一轮认证:考试结构与十年考点分布、单选题高频运用原理、常考数学公式讲解、常考代码讲解与可运行示例,附历年真题考点索引。</p>
<div class="tags"><span>单项选择 30分</span><span>阅读程序 40分</span><span>完善程序 30分</span><span>2015–2025 十年真题</span><span>依据 NOI 大纲 2025 修订版</span></div>
</div></div>
<div class="wrap">
<section id="overview">
<div class="sec-head"><div class="no">1</div><h2>考试结构与十年考点总览</h2><span class="en">EXAM STRUCTURE & TOPIC OVERVIEW</span></div>
<div class="stats">
<div class="stat"><b>30分</b><span>单项选择 15题×2分</span></div>
<div class="stat"><b>40分</b><span>阅读程序 3大题(判断+选择)</span></div>
<div class="stat"><b>30分</b><span>完善程序 2大题×5空×3分</span></div>
<div class="stat"><b>100分 / 120分钟</b><span>2019年起为 CSP-S 第一轮,此前为 NOIP 提高组初赛</span></div>
</div>
<div class="chart-box">
<h3>十年初赛考点模块占比:提高组 vs 普及组</h3>
<p class="cap">数据来自公开的 2012–2021 年 CSP/NOIP 初赛真题统计(提高组侧),编程与算法是绝对主体,信息学基础以记忆性送分题为主</p>
<div id="chart1" class="chart"></div>
<p class="caption">数据口径:近十年初赛真题逐题归类后的分值占比(来源:掘金《CSP/NOIP历年初赛考点分析》,2022-03 发布)。</p>
</div>
<div class="chart-box">
<h3>2019–2025 年提高组初赛主题出现频次</h3>
<p class="cap">按“某年至少出现 1 题”统计,7 届真题中位运算/逻辑、排序与复杂度、图论、排列组合、动态规划几乎年年必考</p>
<div id="chart2" class="chart" style="height:400px"></div>
<p class="caption">数据口径:由 2019–2025 年公开真题解析逐题归类汇总(来源:小码王《CSP-S提高组近5年考点汇总》、博客园/CSDN 历年真题解析),为近似统计。</p>
</div>
<div class="card">
<h3 style="margin-top:0">2019–2025 年考点速查(每年考了什么)</h3>
<div class="tbl-scroll"><table>
<thead><tr><th>年份</th><th>单项选择高频考点</th><th>阅读程序 / 完善程序</th></tr></thead>
<tbody>
<tr><td>2025</td><td>排列组合(插空 C(6,5)=6)、KMP next 数组、线段树区间查询结点数、Trie 结点数、DAG 拓扑排序计数、哈希线性探查、MST 总权重、BST 后序推前序、0-1 背包、LCA、主定理、最小堆、容斥原理、递归 vs 动态规划、EDF 调度</td><td>阅读:DFS 全排列计数(回溯 flag)、双蛋问题(√n 分段策略);完善:双状态 Dijkstra(带免费边)、组合设计/二分编码</td></tr>
<tr><td>2024</td><td>Linux(pwd)、时间复杂度、栈溢出原理、排列组合(颁奖方式)、队列 FIFO、递推函数、欧拉图性质、二分查找条件、模逆元、哈希冲突复杂度、组合数学(路径方案)、序列交换次数、数位和函数、位运算</td><td>阅读:快排递归层数、子序列状态压缩(位运算 DP)、树哈希与欧拉序列;完善:序列合并二分优化(upper_bound)、次短路(双维度优先队列)</td></tr>
<tr><td>2023</td><td>Linux(mkdir)、数字圆环排列、时间复杂度对比、哈夫曼树构造、图染色、LCS、概率期望、位运算优先级、快排最坏情况、树重心、拓扑排序删边、函数不动点、斐波那契复杂度</td><td>阅读:位运算扰动函数(x^=X<<6)、埃氏筛优化、二分答案;完善:第 k 小路径(Dijkstra+状压)、子序列和分治</td></tr>
<tr><td>2022</td><td>Linux(cd)、二进制逻辑运算、栈操作序列、排序稳定性、哈希函数设计、贪心限制、图存储结构、完全二叉树编号、强连通图、2-正规图边数、组队组合、最坏比较次数、信息熵</td><td>阅读:Boyer-Moore 变体、基数排序、Base64 编解码;完善:归并第 k 小元素、容器分水(BFS 状态)</td></tr>
<tr><td>2021</td><td>Linux(ls)、二进制加法、递归层数、排序稳定性、哈夫曼应用、二叉树遍历序列、字符串操作代价、斐波那契复杂度、苹果组合计数、三角形构成、最短路径</td><td>阅读:球体体积交、区间最值 DP(运算符重载)、Base64;完善:魔法数字 BFS、RMQ 分块</td></tr>
<tr><td>2020</td><td>进制转换比较、操作系统功能、视频存储计算、栈操作序列、哈希函数、贪心适用性、DFS 复杂度、二分图最大边、BFS 数据结构、同余方程、阶梯热量递推、后缀表达式</td><td>阅读:子序列最大和、快速选择(随机化分割)、子序列判定;完善:分数背包贪心、取石子 DP</td></tr>
<tr><td>2019</td><td>Linux(mkdir)、逻辑或运算、编译过程定义、浮点精度、数字三角形 DP、组合计数、稳定排序判定、非连通图边数、进制转换(16→10)</td><td>阅读:位运算找规律(函数对称性)、并查集(集合合并计数)、子序列删除代价;完善:技能学习拓扑、取石子 DP</td></tr>
</tbody>
</table></div>
<p class="caption">来源:小码王《CSP-S提高组近5年考点汇总》(2019–2024) 与博客园《CSP-S 2025 初赛解析》、CSDN 各年真题解析。</p>
</div>
<div class="kp">
<b>高频规律:</b>排列组合、位运算/逻辑运算优先级、排序稳定性与复杂度、二叉树遍历、图论(最短路/拓扑/欧拉)、DP(背包/区间/状压)是单选常客;阅读程序偏爱“位运算规律、字符串算法、搜索回溯、分治”;完善程序偏爱“二分、最短路、DP、BFS 状态搜索、贪心”。信息学基础(Linux、编码、存储)是稳定的送分项。
</div>
</section>
<section id="principles">
<div class="sec-head"><div class="no">2</div><h2>选择题高频运用原理速查</h2><span class="en">PRINCIPLES FOR SINGLE-CHOICE</span></div>
<p style="color:var(--muted)">近十年单选最常“考原理”的 12 个点,每条给出原理、判据与真题例子。理解原理本身,比背题更有效。</p>
<div class="card">
<h3>2.1 运算符优先级与求值陷阱(几乎年年考)</h3>
<div class="formula small"><span class="name">C++ 运算符优先级(高→低,速记版)</span>
! → 算术(+ - * / %) → 移位(<< >>) → 关系(< <= > >=) → 相等(== !=) → 位与(&) → 异或(^) → 位或(|) → 逻辑与(&&) → 逻辑或(||) → 三目(?:) → 赋值(=)</div>
<ul>
<li><b>判据:</b>位运算优先级高于逻辑运算,低于关系运算;赋值优先级最低(除逗号)。</li>
<li><b>真题点:</b>2023 考位运算优先级(与逻辑运算混算),2025 提示可能混入三目/赋值;<code>a < b < c</code> 是链式比较(先算 a<b 得 0/1 再与 c 比),不是数学连比。</li>
<li><b>技巧:</b>拿不准就加括号还原运算顺序,或用特殊值(0/1)代入。</li>
</ul>
</div>
<div class="card">
<h3>2.2 位运算技巧</h3>
<div class="formula small"><span class="name">核心恒等式</span>
x & (x−1) 清除最低位的 1;x & −x = lowbit(x) 取出最低位的 1;a^a=0、0^a=a、异或可交换可结合;x<<k = x·2<sup>k</sup>,x>>k = ⌊x/2<sup>k</sup>⌋</div>
<ul>
<li><b>应用:</b>统计二进制中 1 的个数(反复 x&=x−1)、找唯一出现奇数次/缺失元素(全异或)、状态压缩(用 int 位表示集合)。</li>
<li><b>真题点:</b>2019 阅读程序考位运算函数对称性;2023 阅读程序考 x^=X<<6 扰动函数;2024 单选考位运算应用。</li>
</ul>
</div>
<div class="card">
<h3>2.3 排序算法:稳定性与复杂度</h3>
<div class="tbl-scroll"><table>
<thead><tr><th>算法</th><th>最好</th><th>平均</th><th>最坏</th><th>空间</th><th>稳定</th></tr></thead>
<tbody>
<tr><td>冒泡 / 插入</td><td>O(n)</td><td>O(n²)</td><td>O(n²)</td><td>O(1)</td><td>稳定</td></tr>
<tr><td>选择</td><td>O(n²)</td><td>O(n²)</td><td>O(n²)</td><td>O(1)</td><td>不稳定</td></tr>
<tr><td>快速排序</td><td>O(n log n)</td><td>O(n log n)</td><td><b>O(n²)</b>(已有序/基准选取差)</td><td>O(log n)~O(n)</td><td>不稳定</td></tr>
<tr><td>归并排序</td><td>O(n log n)</td><td>O(n log n)</td><td>O(n log n)</td><td>O(n)</td><td>稳定</td></tr>
<tr><td>堆排序</td><td>O(n log n)</td><td>O(n log n)</td><td>O(n log n)</td><td>O(1)</td><td>不稳定</td></tr>
<tr><td>基数排序</td><td colspan="3">O(d(n+k))</td><td>O(n+k)</td><td>稳定</td></tr>
</tbody>
</table></div>
<ul>
<li><b>判据:</b>“跳跃交换”的排序(快排、堆、选择)不稳;“相邻交换/合并”的排序(冒泡、插入、归并、基数)稳定。</li>
<li><b>真题点:</b>2019 稳定排序判定、2022/2021 排序稳定性、2023/2024 快排最坏情况(对已有序数组快排退化为 O(n²))、2024 阅读考快排递归层数。</li>
</ul>
</div>
<div class="card">
<h3>2.4 二叉树性质与遍历(高频)</h3>
<div class="formula small"><span class="name">常用性质</span>
深度 h 的二叉树最多 2<sup>h</sup>−1 个结点;第 i 层最多 2<sup>i−1</sup> 个结点;叶子数 n<sub>0</sub> = 度为 2 结点数 n<sub>2</sub> + 1;满二叉树第 k 层 2<sup>k−1</sup> 个结点;完全二叉树中结点 i 的父为 ⌊i/2⌋、左子 2i、右子 2i+1</div>
<ul>
<li><b>遍历判据:</b>前序(根左右)、中序(左根右)、后序(左右根)。<b>中序 + 前序(或后序)可唯一确定二叉树</b>;只有前序+后序不能唯一确定。</li>
<li><b>由后序推前序(BST):</b>后序末位是根,BST 中序=排序后的序列,据此分左右子树递归。2025 真题:后序 2,5,4,8,12,10,6 → 前序 6,4,2,5,10,8,12。</li>
<li><b>真题点:</b>2021 二叉树遍历序列、2022 完全二叉树编号、2023 哈夫曼树、2025 线段树/BST。</li>
</ul>
</div>
<div class="card">
<h3>2.5 图论基础判据</h3>
<div class="formula small"><span class="name">边数公式</span>
无向完全图 n(n−1)/2;有向完全图 n(n−1);连通无向图至少 n−1 条边;树:n 个点 n−1 条边;二分图(无奇环)最大边 ⌊n²/4⌋;连通平面图欧拉公式 V−E+F=2</div>
<ul>
<li><b>欧拉图:</b>存在欧拉回路 ⇔ 连通且所有点度数为偶;存在欧拉路径 ⇔ 连通且恰有 0 或 2 个奇度点。</li>
<li><b>强连通:</b>有向图中任意两点互相可达;2022 考强连通图定义、2020 考二分图最大边、2019 考非连通图边数、2024 考欧拉图性质、2025 考 MST/拓扑/LCA。</li>
</ul>
</div>
<div class="card">
<h3>2.6 进制转换与补码</h3>
<ul>
<li><b>转换:</b>十进制→r 进制用“除 r 取余”(整数)、“乘 r 取整”(小数);二进制↔十六进制按 4 位一组对应。</li>
<li><b>补码:</b>正数补码=原码;负数补码=反码+1。8 位补码表示范围 −128 ~ 127;<code>-1</code> 的 8 位补码是 11111111。补码使减法变加法,是现代计算机整数表示标准。</li>
<li><b>真题点:</b>2019 进制转换(16→10)、2020 进制转换比较、2021 二进制加法、2022 二进制逻辑运算。</li>
</ul>
</div>
<div class="card">
<h3>2.7 哈希表冲突处理</h3>
<ul>
<li><b>除留余数法:</b>h(key)=key mod m。<b>线性探查:</b>冲突后依次向后找空位(可循环)。</li>
<li><b>真题点:</b>2025:大小为 13、h(key)=key mod 13,依次插入 18,26,35,9,68,74,74 最终落在索引 11(9→10→11);2024/2022 考哈希冲突时间复杂度、2020 哈希函数设计。</li>
</ul>
</div>
<div class="card">
<h3>2.8 哈夫曼编码</h3>
<ul>
<li><b>构造:</b>每次取权值最小的两棵树合并,权值和为新结点;n 个叶子 ⇒ 共 2n−1 个结点。</li>
<li><b>带权路径长度 WPL</b> = Σ(叶权×叶深度),越小越优;哈夫曼编码是<b>前缀码</b>(任一编码不是另一编码的前缀)。</li>
<li><b>真题点:</b>2021 哈夫曼应用、2023 哈夫曼树构造。</li>
</ul>
</div>
<div class="card">
<h3>2.9 复杂度分析与主定理</h3>
<div class="formula small"><span class="name">主定理(分治递推 T(n)=aT(n/b)+f(n))</span>
记 c = log<sub>b</sub>a:若 f(n)=O(n<sup>c−ε</sup>) → T(n)=Θ(n<sup>c</sup>);若 f(n)=Θ(n<sup>c</sup>) → T(n)=Θ(n<sup>c</sup>log n);若 f(n)=Ω(n<sup>c+ε</sup>) 且 af(n/b)≤k·f(n)(k<1)→ T(n)=Θ(f(n))</div>
<ul>
<li><b>真题点:</b>2025:T(n)=2T(n/2)+n² → c=log₂2=1,f(n)=n²=Ω(n<sup>1+ε</sup>),得 O(n²)。2024/2023 考时间复杂度对比。</li>
<li><b>常见复杂度排序:</b>O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)。</li>
</ul>
</div>
<div class="card">
<h3>2.10 Linux 命令与编译过程(稳定送分)</h3>
<ul>
<li><b>常用命令:</b>ls(列目录)、cd(切换)、pwd(当前路径)、mkdir(建目录)、cp/mv/rm、cat、g++ 编译(-o 输出名、-O2 优化、-std=c++14/17)、time 计时。</li>
<li><b>编译四阶段:</b>预处理(-E) → 编译(-S 得汇编) → 汇编(-c 得目标文件) → 链接(得可执行文件)。</li>
<li><b>真题点:</b>2019/2021/2022/2023/2024 几乎每年一道 Linux 命令或编译过程题。</li>
</ul>
</div>
<div class="card">
<h3>2.11 计算机基础:编码、存储、系统</h3>
<ul>
<li><b>单位:</b>1KB=2¹⁰B=1024B,1MB=1024KB,1GB=1024MB;视频/图像存储量按 分辨率×位深×帧率×时长 估算(2020 考过)。</li>
<li><b>ASCII:</b>'0'=48,'A'=65,'a'=97(小写=大写+32)。</li>
<li><b>系统:</b>进程与线程区别、死锁四条件(互斥/占有等待/不可剥夺/循环等待)、栈溢出(递归无出口,2024 单选原题)。</li>
</ul>
</div>
<div class="card">
<h3>2.12 栈、队列与表达式</h3>
<ul>
<li><b>栈 LIFO、队列 FIFO;</b>递归用系统栈;BFS 用队列、DFS 用栈/递归。</li>
<li><b>出栈序列数</b> = 卡特兰数 Cat(n);n 个元素不同出栈序列共 Cat(n) 种(2020 后缀表达式、2022 栈操作序列、2024 栈溢出/队列 FIFO)。</li>
<li><b>表达式:</b>中缀转后缀(逆波兰)用栈;后缀表达式求值:遇数入栈、遇运算符弹两数计算再压回。</li>
</ul>
</div>
</section>
<section id="math">
<div class="sec-head"><div class="no">3</div><h2>常考数学公式讲解</h2><span class="en">MATH FORMULAS & TRICKS</span></div>
<p style="color:var(--muted)">数学基础虽然只占约 6% 分值,但“排列组合 + 计数”几乎是每年单选必考 1–2 题;容斥、错排、卡特兰、数论是拉开差距的地方。</p>
<div class="card">
<h3>3.1 排列与组合</h3>
<div class="formula"><span class="name">排列 P(n,k) 与组合 C(n,k)</span>
P(n,k) = n!/(n−k)! C(n,k) = n!/(k!·(n−k)!) = C(n, n−k)<br>
递推:C(n,k) = C(n−1,k) + C(n−1,k−1)(杨辉三角)</div>
<ul>
<li><b>圆排列:</b>n 个不同元素围成一圈,排列数 (n−1)!;项链(可翻转)再除以 2。</li>
<li><b>捆绑法:</b>必须相邻的元素先捆成一个整体再排;<b>插空法:</b>不相邻元素先排其余元素、再往空隙插入。</li>
<li><b>隔板法:</b>n 个相同球分给 k 个不同盒:每盒至少 1 个 → C(n−1, k−1);允许空盒 → C(n+k−1, k−1)。</li>
<li><b>真题点:</b>2025:5 红 5 蓝不相邻 → 先排红球形成 6 空,C(6,5)=6;2024 颁奖方式、2022 组队、2021 苹果分配、2020 组合计数、2019 四位数组合计数。</li>
</ul>
</div>
<div class="card">
<h3>3.2 二项式定理</h3>
<div class="formula"><span class="name">(a+b)<sup>n</sup> = Σ<sub>k=0..n</sub> C(n,k)·a<sup>n−k</sup>·b<sup>k</sup></span>
第 k+1 项系数 C(n,k);系数和为 2<sup>n</sup>;奇数项系数和 = 偶数项系数和 = 2<sup>n−1</sup>(n≥1)</div>
<p>常与“多项式展开某一次项系数”结合考查,本质是组合计数。</p>
</div>
<div class="card">
<h3>3.3 错排(Derangement)</h3>
<div class="formula"><span class="name">D(n) = (n−1)·(D(n−1)+D(n−2)),D(1)=0,D(2)=1</span>
D(3)=2,D(4)=9,D(5)=44;另一形式 D(n) = n!·Σ<sub>k=0..n</sub> (−1)<sup>k</sup>/k!</div>
<ul>
<li><b>含义:</b>n 个元素的全排列中,没有任何一个元素留在原位(如 n 封信装错 n 个信封)的排列数。</li>
<li><b>推导思路(容斥):</b>总数 n! 减去至少 1 个在位的,用容斥原理展开即得上式。</li>
<li><b>真题点:</b>NOIP 提高组初赛多次考错排递推求值,记住 D(1)~D(5) 直接得分。</li>
</ul>
</div>
<div class="card">
<h3>3.4 卡特兰数(Catalan)——初赛最爱考的数列</h3>
<div class="formula"><span class="name">Cat(n) = C(2n, n)/(n+1) = C(2n, n) − C(2n, n−1)</span>
递推:Cat(n) = Σ<sub>i=0..n−1</sub> Cat(i)·Cat(n−1−i),Cat(0)=1</div>
<ul>
<li><b>数值:</b>1, 1, 2, 5, 14, 42, 132, 429…(n=0 起)。</li>
<li><b>等价场景(看到即想到卡特兰):</b>n 对括号的合法匹配数、n 个元素出栈序列数、n 个结点二叉树的形态数、凸 n+2 边形三角剖分数、n×n 网格不越过对角线的路径数、n 个矩阵连乘加括号方案数。</li>
<li><b>真题点:</b>2018(NOIP)考 n 个结点满二叉树形态;2023 圆环排列相关;注意区分“n 个结点二叉树形态”=Cat(n) 与“n 个结点满二叉树”=Cat(n−1)。</li>
</ul>
</div>
<div class="card">
<h3>3.5 经典递推</h3>
<div class="formula"><span class="name">斐波那契 F(n)=F(n−1)+F(n−2)</span>
F(0)=0,F(1)=1 → 0,1,1,2,3,5,8,13,21…<br>
<span class="name">汉诺塔 H(n)=2H(n−1)+1 = 2<sup>n</sup>−1</span><br>
<span class="name">平面分割</span> n 条直线最多把平面分成 1+n(n+1)/2 个区域</div>
<ul>
<li><b>复杂度坑:</b>朴素递归算 F(n) 是 O(2ⁿ)(重叠子问题,2025 单选原题);动态规划/迭代为 O(n)。</li>
<li><b>真题点:</b>2020 阶梯热量递推、2021 斐波那契复杂度、2024 递推函数计算、2025 递归 vs DP。</li>
</ul>
</div>
<div class="card">
<h3>3.6 容斥原理</h3>
<div class="formula"><span class="name">|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|</span></div>
<ul>
<li><b>真题点(2025 原题):</b>1~1000 中不能被 2、3、5 任意一个整除的数:能被 2/3/5 整除的分别 500/333/200 个,两两交集 166/100/66,三交集 33 → 至少被一个整除 = 500+333+200−166−100−66+33 = 734,答案 1000−734 = <b>266</b>。</li>
<li>另可用于错排公式推导、错位排列计数。</li>
</ul>
</div>
<div class="card">
<h3>3.7 概率与期望</h3>
<div class="formula"><span class="name">古典概型 P(A)=|A|/|Ω|;期望 E(X)=Σ x·P(X=x)</span>
期望线性性:E(X+Y)=E(X)+E(Y)(对任意随机变量成立,不用独立)</div>
<ul>
<li><b>真题点:</b>2023 考概率期望计算(如抽球、掷骰子类);近年倾向与组合计数结合。</li>
<li><b>技巧:</b>求“至少/恰好”先想补事件;期望题先列所有取值和概率再求和。</li>
</ul>
</div>
<div class="card">
<h3>3.8 数论:模运算、逆元、快速幂</h3>
<div class="formula"><span class="name">模运算</span>
(a+b) mod m、a·b mod m 保持封闭;(a·b) mod m = ((a mod m)·(b mod m)) mod m<br>
<span class="name">乘法逆元</span> a·a<sup>−1</sup> ≡ 1 (mod m),当 gcd(a,m)=1 时存在<br>
<span class="name">费马小定理</span> p 为素数且 p∤a:a<sup>p−1</sup> ≡ 1 (mod p),故 a<sup>−1</sup> ≡ a<sup>p−2</sup> (mod p)</div>
<ul>
<li><b>真题点:</b>2020 同余方程、2024 模数逆元算法(逆元可由快速幂/扩展欧几里得求)。</li>
</ul>
</div>
<div class="card">
<h3>3.9 素数与 gcd/lcm</h3>
<div class="formula"><span class="name">质数判断 O(√n)</span> 试除到 √n 即可;埃氏筛 O(n log log n)、欧拉筛 O(n)<br>
<span class="name">gcd</span> gcd(a,b)=gcd(b, a mod b)(辗转相除,O(log n));lcm(a,b)·gcd(a,b)=a·b</div>
<ul>
<li><b>真题点:</b>2023 阅读程序考埃氏筛优化;素数/质因数分解常出现在阅读程序背景。</li>
</ul>
</div>
<div class="card">
<h3>3.10 图论公式汇总</h3>
<div class="tbl-scroll"><table>
<thead><tr><th>对象</th><th>公式 / 结论</th><th>考过年份</th></tr></thead>
<tbody>
<tr><td>连通平面图</td><td>欧拉公式 V − E + F = 2</td><td>2024(欧拉图性质)</td></tr>
<tr><td>无向完全图 / 有向完全图</td><td>n(n−1)/2 / n(n−1) 条边</td><td>2022(2-正规图边数)</td></tr>
<tr><td>连通无向图 / 树</td><td>至少 n−1 条边;树恰好 n−1</td><td>2019(非连通图边数)</td></tr>
<tr><td>二分图(n 个点)</td><td>无奇环;最大边数 ⌊n²/4⌋</td><td>2020(二分图最大边)</td></tr>
<tr><td>欧拉回路 / 路径</td><td>回路:连通且全偶度;路径:恰 0 或 2 个奇度点</td><td>2024</td></tr>
<tr><td>强连通图</td><td>有向图中任意两点互相可达</td><td>2022</td></tr>
<tr><td>DAG</td><td>至少存在一个入度为 0 的顶点;拓扑排序方案数与结构有关</td><td>2025(拓扑排序计数)</td></tr>
</tbody>
</table></div>
</div>
<div class="card">
<h3>3.11 常见算法复杂度表(背熟)</h3>
<div class="tbl-scroll"><table>
<thead><tr><th>算法</th><th>时间复杂度</th><th>算法</th><th>时间复杂度</th></tr></thead>
<tbody>
<tr><td>二分查找</td><td>O(log n)</td><td>Dijkstra(朴素/堆优化)</td><td>O(V²) / O((V+E)log V)</td></tr>
<tr><td>快速幂</td><td>O(log n)</td><td>Floyd</td><td>O(V³)</td></tr>
<tr><td>gcd 辗转相除</td><td>O(log n)</td><td>Bellman-Ford</td><td>O(VE)</td></tr>
<tr><td>埃氏筛 / 欧拉筛</td><td>O(n log log n) / O(n)</td><td>Kruskal / Prim</td><td>O(E log E) / O(V²)</td></tr>
<tr><td>DFS/BFS</td><td>O(V+E)</td><td>区间 DP</td><td>O(n³)</td></tr>
<tr><td>并查集(路径压缩+按秩合并)</td><td>O(α(n)) 近似常数</td><td>线段树 单点改/区间查</td><td>O(log n)</td></tr>
<tr><td>KMP</td><td>O(n+m)</td><td>状态压缩 DP(n 元素子集)</td><td>O(n·2ⁿ)</td></tr>
</tbody>
</table></div>
</div>
<div class="card">
<h3>3.12 信息量与存储计算</h3>
<ul>
<li><b>信息量:</b>等概率事件的信息量 I = log₂(1/p) 比特;信息熵 = Σ p·log₂(1/p)。2022 考过信息熵起源。</li>
<li><b>存储估算:</b>未压缩图像 ≈ 宽×高×位深/8 字节;视频 ≈ 单帧大小×帧率×时长。2020 考视频存储计算。</li>
</ul>
</div>
</section>
<section id="code">
<div class="sec-head"><div class="no">4</div><h2>常考代码讲解与示例</h2><span class="en">CODE PATTERNS WITH EXAMPLES</span></div>
<p style="color:var(--muted)">初赛的阅读程序/完善程序本质上是在考“常见算法模板 + 边界细节”。下面 16 个模板覆盖近十年 90% 以上真题代码,每个模板给出功能讲解、示例代码与真题出处。</p>
<div class="card">
<h3>4.1 二分查找(含 lower_bound)</h3>
<div class="kp">
<b>讲解:</b>单调序列上每次砍半区间。两种写法必须配套记牢:<code>l<=r</code> 配 <code>l=mid+1 / r=mid-1</code>(闭区间查找);<code>l<r</code> 配 <code>l=mid+1 / r=mid</code>(左闭右开求下界)。混淆 mid 更新会死循环——这是完善程序最爱挖的坑。
</div>
<pre><span class="cap">二分查找(闭区间写法)</span><button class="copy-btn">复制</button><code>// 升序数组 a[1..n] 中查找 x,返回下标,找不到返回 -1
int binarySearch(int a[], int n, int x) {
int l = 1, r = n;
while (l <= r) {
int mid = l + (r - l) / 2; // 防溢出写法
if (a[mid] == x) return mid;
else if (a[mid] < x) l = mid + 1;
else r = mid - 1;
}
return -1;
}
// lower_bound:第一个 >= x 的位置(左闭右开写法)
int lowerBound(int a[], int n, int x) {
int l = 1, r = n + 1;
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] >= x) r = mid; // 收缩右界
else l = mid + 1;
}
return l;
}</code></pre>
<p class="caption">真题:2023 完善程序(有序等差数列找缺失项,二分边界收敛)、2024 完善程序(序列合并 upper_bound 实现)、2024 单选(二分查找条件)、2021 阅读程序。</p>
</div>
<div class="card">
<h3>4.2 快速排序(划分 partition)</h3>
<div class="kp">
<b>讲解:</b>每次选一个基准,把小于基准的放左边、大于的放右边,递归两侧。Lomuto 划分以最右元素为基准;基准选得差(如已有序数组)退化为 O(n²)。阅读程序常考“递归层数”“最坏输入”。
</div>
<pre><span class="cap">快速排序(Lomuto 划分)</span><button class="copy-btn">复制</button><code>int partition(int a[], int l, int r) {
int x = a[r]; // 基准取最右元素
int i = l - 1;
for (int j = l; j < r; ++j)
if (a[j] < x) swap(a[++i], a[j]);
swap(a[i + 1], a[r]); // 基准归位
return i + 1; // 基准最终下标
}
void quickSort(int a[], int l, int r) {
if (l >= r) return;
int p = partition(a, l, r);
quickSort(a, l, p - 1);
quickSort(a, p + 1, r);
}</code></pre>
<p class="caption">真题:2023 单选(快排最坏情况=已有序数组 O(n²))、2024 阅读程序(快排递归层数与边界)、2020 阅读程序(快速选择算法 randomize partition)。</p>
</div>
<div class="card">
<h3>4.3 归并排序与逆序对</h3>
<div class="kp">
<b>讲解:</b>分治:拆两半→各自排好→线性合并。合并时若右半元素先于左半出列,则它与左半剩余元素构成逆序对,计数 <code>mid-i+1</code>。稳定、O(n log n)、需 O(n) 辅助空间。
</div>
<pre><span class="cap">归并排序 + 逆序对计数</span><button class="copy-btn">复制</button><code>long long inv = 0; // 逆序对总数
void mergeSort(int a[], int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
mergeSort(a, l, mid);
mergeSort(a, mid + 1, r);
int i = l, j = mid + 1, k = 0;
int tmp[r - l + 1];
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else { tmp[k++] = a[j++]; inv += mid - i + 1; }
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int t = 0; t < k; ++t) a[l + t] = tmp[t];
}</code></pre>
<p class="caption">真题:2022 完善程序(两个有序序列归并求第 k 小,双指针)、2021 阅读程序(分治结构分析)。</p>
</div>
<div class="card">
<h3>4.4 栈:后缀表达式求值 / 括号匹配</h3>
<div class="kp">
<b>讲解:</b>后缀表达式(逆波兰)求值:数字入栈,遇运算符弹出两个操作数、计算后压回。括号匹配:左括号入栈,右括号与栈顶配对。2020 单选直接考后缀表达式。
</div>
<pre><span class="cap">后缀表达式求值(一位数字)</span><button class="copy-btn">复制</button><code>#include <stack>
using namespace std;
int evalPostfix(const string& s) {
stack<int> st;
for (char c : s) {
if (c >= '0' && c <= '9') st.push(c - '0');
else {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
if (c == '+') st.push(a + b);
else if (c == '-') st.push(a - b);
else if (c == '*') st.push(a * b);
else st.push(a / b);
}
}
return st.top();
}</code></pre>
<p class="caption">真题:2020(后缀表达式)、2022(栈操作序列,判断哪些出栈序列合法)、2024(栈溢出原理)。</p>
</div>
<div class="card">
<h3>4.5 二叉树遍历与重建</h3>
<div class="kp">
<b>讲解:</b>前序=根左右、中序=左根右、后序=左右根。已知中序 +(前序或后序)可以唯一重建二叉树:后序最后一个(或前序第一个)是根,在中序中定位根后,左右两侧分别是左右子树,递归处理。2025 真题就是“BST 后序推前序”。
</div>
<pre><span class="cap">由后序 + 中序重建并输出前序</span><button class="copy-btn">复制</button><code>int in[MAXN], post[MAXN];
// 后序区间 [pl,pr],中序区间 [il,ir]
void rebuild(int pl, int pr, int il, int ir) {
if (pl > pr) return;
int root = post[pr]; // 后序最后一个是根
printf("%d ", root);
int p = il;
while (in[p] != root) ++p; // 在中序中定位根
int lsize = p - il; // 左子树大小
rebuild(pl, pl + lsize - 1, il, p - 1); // 左子树
rebuild(pl + lsize, pr - 1, p + 1, ir); // 右子树
}</code></pre>
<p class="caption">真题:2025(BST 后序推前序)、2021(二叉树遍历序列)、2018(NOIP)等。遍历递归/非递归实现也是阅读程序常见背景。</p>
</div>
<div class="card">
<h3>4.6 DFS 回溯(全排列模板,2025 原题)</h3>
<div class="kp">
<b>讲解:</b>DFS 枚举每个位置可选数字,<code>flag[]</code> 标记已用,递归前标记、递归后<b>必须回溯取消标记</b>。删掉回溯语句会让大部分排列无法生成(2025 阅读判断题原题)。剪枝条件写在递归入口处。
</div>
<pre><span class="cap">1..n 全排列(含剪枝示例)</span><button class="copy-btn">复制</button><code>int n, ans = 0;
int p[27]; bool flag[27];
void dfs(int k) {
if (k == n + 1) { ++ans; return; } // 生成一个排列
for (int i = 1; i <= n; ++i) {
if (flag[i]) continue;
if (k > 1 && i == p[k - 1] + 1) continue; // 剪枝:相邻不连续
p[k] = i;
flag[i] = true;
dfs(k + 1);
flag[i] = false; // 回溯,关键!
}
}</code></pre>
<p class="caption">真题:2025 阅读程序原题(统计相邻两项不递增 1 的排列数,n=3 输出 3,n=4 输出 11)。DFS 回溯还用于八皇后、迷宫、连通块。</p>
</div>
<div class="card">
<h3>4.7 BFS 最短路(无权图 / 迷宫)</h3>
<div class="kp">
<b>讲解:</b>用队列逐层扩展,首次到达即最短距离(无权图)。<code>dist[][]</code> 初始 -1 兼作访问标记。BFS 常与状态压缩结合(把“容器水量”等状态编码成整数)。
</div>
<pre><span class="cap">迷宫最短路(四方向)</span><button class="copy-btn">复制</button><code>#include <queue>
using namespace std;
typedef pair<int,int> pii;
int dist[105][105]; // -1 表示未访问
int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
int bfs(int sx, int sy, int n, int m) {
memset(dist, -1, sizeof(dist));
queue<pii> q;
q.push(make_pair(sx, sy)); dist[sx][sy] = 0;
while (!q.empty()) {
pii u = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
int nx = u.first + dx[k], ny = u.second + dy[k];
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
if (dist[nx][ny] != -1) continue; // 已访问
dist[nx][ny] = dist[u.first][u.second] + 1;
q.push(make_pair(nx, ny));
}
}
return dist[n][m]; // 终点距离
}</code></pre>
<p class="caption">真题:2020(BFS 数据结构)、2021 完善程序(魔法数字 BFS 状态转移)、2022 完善程序(容器分水 BFS 状态搜索)。</p>
</div>
<div class="card">
<h3>4.8 Dijkstra 最短路(堆优化)</h3>
<div class="kp">
<b>讲解:</b>维护“已确定最短路的点集”,每次取当前距离最小的未确定点松弛其邻边。堆优化用优先队列存 (dist, 点),<code>if (d != dist[u]) continue</code> 是懒惰删除。2024 完善程序考“次短路=双维度优先队列”;2023 考“第 k 小路径=Dijkstra+状态压缩”。
</div>
<pre><span class="cap">Dijkstra(邻接表 + 堆优化)</span><button class="copy-btn">复制</button><code>#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> pii; // (距离, 顶点)
const int INF = 0x3f3f3f3f;
vector<pii> e[MAXN]; // e[u] = {(v, w), ...}
int dist[MAXN];
void dijkstra(int s, int n) {
for (int i = 1; i <= n; ++i) dist[i] = INF;
dist[s] = 0;
priority_queue<pii, vector<pii>, greater<pii> > pq;
pq.push(make_pair(0, s));
while (!pq.empty()) {
pii top = pq.top(); pq.pop();
int d = top.first, u = top.second;
if (d != dist[u]) continue; // 懒惰删除过期项
for (size_t i = 0; i < e[u].size(); ++i) {
int v = e[u][i].first, w = e[u][i].second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push(make_pair(dist[v], v));
}
}
}
}</code></pre>
<p class="caption">真题:2023/2024/2025 完善程序(Dijkstra 及其变体——双状态/第 k 小/分层图)、2021(最短路径计算)。</p>
</div>
<div class="card">
<h3>4.9 Floyd 全源最短路</h3>
<div class="kp">
<b>讲解:</b>三重循环,k 为中间点,<code>d[i][j] = min(d[i][j], d[i][k]+d[k][j])</code>,O(n³)。初赛常考其代码结构(哪层循环在外)与适用条件(无负环)。
</div>
<pre><span class="cap">Floyd-Warshall</span><button class="copy-btn">复制</button><code>for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (d[i][k] + d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];</code></pre>
</div>
<div class="card">
<h3>4.10 最小生成树:Kruskal / Prim</h3>
<div class="kp">
<b>讲解:</b>Kruskal:边按权值排序,用并查集从小到大选边,不成环就加入。Prim:从一个点出发每次选“连接已选集合的最短边”。2025 单选:8 顶点、边权=|编号差| 的完全图,MST 取相邻顶点边,总权重 1+…+7=7。
</div>
<pre><span class="cap">Kruskal(并查集)</span><button class="copy-btn">复制</button><code>struct Edge { int u, v, w; } eg[MAXM];
bool cmp(const Edge& a, const Edge& b) { return a.w < b.w; }
int fa[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } // 路径压缩
// main 中:
sort(eg + 1, eg + m + 1, cmp);
int ans = 0, cnt = 0;
for (int i = 1; i <= m; ++i) {
int fu = find(eg[i].u), fv = find(eg[i].v);
if (fu != fv) { fa[fu] = fv; ans += eg[i].w; if (++cnt == n - 1) break; }
}</code></pre>
<p class="caption">真题:2025(MST 总权重)、并查集 2019 阅读程序(集合合并计数)。</p>
</div>
<div class="card">
<h3>4.11 拓扑排序(Kahn 算法)</h3>
<div class="kp">
<b>讲解:</b>统计入度,入度为 0 的入队;出队时将其后继入度减 1,减到 0 再入队。队列输出顺序即一个拓扑序。若最终排序数 < n 说明有环。2025 考“DAG 拓扑排序方案数取决于结构”,2023 考拓扑排序删边。
</div>
<pre><span class="cap">拓扑排序(Kahn)</span><button class="copy-btn">复制</button><code>#include <queue>
using namespace std;
queue<int> q;
int indeg[MAXN];
vector<int> e[MAXN], topo;
void topoSort(int n) {
for (int i = 1; i <= n; ++i)
if (indeg[i] == 0) q.push(i);
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (size_t i = 0; i < e[u].size(); ++i) {
int v = e[u][i];
if (--indeg[v] == 0) q.push(v);
}
}
}</code></pre>
<p class="caption">真题:2025(DAG 拓扑计数)、2023(拓扑排序删边)、2019 完善程序(技能学习拓扑依赖)。</p>
</div>
<div class="card">
<h3>4.12 动态规划四大高频模板</h3>
<div class="kp">
<b>讲解:</b>DP 三要素:状态、转移、边界。初赛最爱考:01 背包(<b>逆序</b>滚动手写)、完全背包(正序)、LIS、LCS、区间 DP(石子合并 O(n³))、状态压缩 DP(位掩码)。
</div>
<pre><span class="cap">01 背包(容量 V,逆序枚举容量)</span><button class="copy-btn">复制</button><code>int w[MAXN], v[MAXN], dp[MAXV];
for (int i = 1; i <= n; ++i)
for (int j = V; j >= w[i]; --j) // 逆序:保证每件物品至多取一次
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
// 完全背包只需把容量循环改为正序:for (int j = w[i]; j <= V; ++j)</code></pre>
<pre><span class="cap">LIS 最长上升子序列(O(n²))与 LCS(O(nm))</span><button class="copy-btn">复制</button><code>// LIS
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j)
if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
}
// LCS:a[1..n], b[1..m]
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i] == b[j]) f[i][j] = f[i-1][j-1] + 1;
else f[i][j] = max(f[i-1][j], f[i][j-1]);</code></pre>
<pre><span class="cap">区间 DP:石子合并(最小代价)</span><button class="copy-btn">复制</button><code>for (int len = 2; len <= n; ++len) // 枚举区间长度
for (int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
f[i][j] = INF;
for (int k = i; k < j; ++k) // 枚举分割点
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + sum[j] - sum[i-1]);
}</code></pre>
<p class="caption">真题:2025(0-1 背包求最大价值:容量 20、物品 (7,15)(5,12)(4,9)(3,7)(6,13) → 选 7+4+3+6=20 得 44)、2024(状压 DP 阅读)、2021(区间最值 DP)、2020(取石子/分数背包)、2019(数字三角形)。</p>
</div>
<div class="card">
<h3>4.13 快速幂</h3>
<div class="kp">
<b>讲解:</b>把指数 b 看成二进制,逐位平方底数、按位累乘。O(log b)。是求模逆元(a<sup>p−2</sup>)的基础。
</div>
<pre><span class="cap">a^b mod m</span><button class="copy-btn">复制</button><code>long long powmod(long long a, long long b, long long m) {
long long r = 1 % m;
a %= m;
while (b) {
if (b & 1) r = r * a % m;
a = a * a % m;
b >>= 1;
}
return r;
}</code></pre>
</div>
<div class="card">
<h3>4.14 素数筛:埃氏筛与欧拉筛</h3>
<div class="kp">
<b>讲解:</b>埃氏筛从 2 开始把每个素数的倍数标记为合数,O(n log log n);欧拉筛每个合数只被其最小质因子筛一次,O(n),关键在 <code>if (i % prime[j] == 0) break;</code>。2023 阅读程序直接考埃氏筛优化。
</div>
<pre><span class="cap">埃氏筛</span><button class="copy-btn">复制</button><code>bool isComp[MAXN];
for (int i = 2; i <= n; ++i)
if (!isComp[i])
for (long long j = 1LL * i * i; j <= n; j += i) // 从 i*i 开始
isComp[j] = true;</code></pre>
<pre><span class="cap">欧拉筛(线性筛)</span><button class="copy-btn">复制</button><code>int prime[MAXN], pcnt = 0;
bool isComp[MAXN];
for (int i = 2; i <= n; ++i) {
if (!isComp[i]) prime[++pcnt] = i;
for (int j = 1; j <= pcnt && 1LL * i * prime[j] <= n; ++j) {
isComp[i * prime[j]] = true;
if (i % prime[j] == 0) break; // 保证每个合数只被最小质因子筛到
}
}</code></pre>
</div>
<div class="card">
<h3>4.15 gcd 与扩展欧几里得</h3>
<div class="kp">
<b>讲解:</b>辗转相除 O(log n)。扩展欧几里得在求 gcd 的同时解出 ax+by=gcd(a,b) 的一组整数解,是求模逆元、解同余方程的基础(2020 同余方程、2024 模逆元)。
</div>
<pre><span class="cap">gcd / exgcd</span><button class="copy-btn">复制</button><code>int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// 返回 gcd(a,b),并求出一组 x,y 使 ax + by = gcd(a,b)
int exgcd(int a, int b, int& x, int& y) {
if (b == 0) { x = 1; y = 0; return a; }
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}</code></pre>
</div>
<div class="card">
<h3>4.16 KMP 与 next 数组</h3>
<div class="kp">
<b>讲解:</b>next[i] 表示模式串 P[0..i] 的最长公共前后缀长度。失配时主串不回退,模式串跳到 next 位置继续比,整体 O(n+m)。2025 单选原题:P="abacaba" 的 next 数组(下标从 0 起)为 {0,0,1,0,1,2,3}。
</div>
<pre><span class="cap">KMP next 数组与匹配</span><button class="copy-btn">复制</button><code>int nxt[MAXN];
void getNext(const string& p) {
int m = (int)p.size();
nxt[0] = 0;
for (int i = 1, j = 0; i < m; ++i) {
while (j > 0 && p[i] != p[j]) j = nxt[j - 1];
if (p[i] == p[j]) ++j;
nxt[i] = j;
}
}
int kmp(const string& s, const string& p) { // 返回首次匹配位置
int n = (int)s.size(), m = (int)p.size();
for (int i = 0, j = 0; i < n; ++i) {
while (j > 0 && s[i] != p[j]) j = nxt[j - 1];
if (s[i] == p[j]) ++j;
if (j == m) return i - m + 1;
}
return -1;
}</code></pre>
<p class="caption">真题:2025(KMP next 数组)、2022(Boyer-Moore 变体阅读)、2021(字符串操作代价)。</p>
</div>
<div class="card">
<h3>4.17 位运算代码技巧</h3>
<div class="kp">
<b>讲解:</b>三个高频片段:lowbit、popcount、子集枚举。状压 DP 与“找出出现奇数次元素”都依赖它们。
</div>
<pre><span class="cap">lowbit / 统计 1 的个数 / 枚举子集</span><button class="copy-btn">复制</button><code>int lowbit(int x) { return x & -x; } // 取最低位 1 的值
int popcount(int x) { // 二进制中 1 的个数
int c = 0;
while (x) { x &= x - 1; ++c; }
return c;
}
// 枚举集合 mask 的所有非空子集 s
for (int s = mask; s; s = (s - 1) & mask) {
// 处理子集 s
}</code></pre>
</div>
<div class="card">
<h3>4.18 高精度加法</h3>
<div class="kp">
<b>讲解:</b>数字按低位在前存入 vector<int>,逐位相加并处理进位。阅读程序常以“大数相加/阶乘”为背景。
</div>
<pre><span class="cap">高精度加法(低位在前)</span><button class="copy-btn">复制</button><code>#include <vector>
using namespace std;
vector<int> add(const vector<int>& a, const vector<int>& b) {
vector<int> c;
int t = 0;
int n = max(a.size(), b.size());
for (int i = 0; i < n || t; ++i) {
if (i < (int)a.size()) t += a[i];
if (i < (int)b.size()) t += b[i];
c.push_back(t % 10);
t /= 10;
}
return c;
}</code></pre>
</div>
<div class="card">
<h3>4.19 STL 速查(阅读程序常客)</h3>
<div class="tbl-scroll"><table>
<thead><tr><th>容器/函数</th><th>要点</th><th>复杂度</th></tr></thead>
<tbody>
<tr><td>sort(begin,end)</td><td>随机访问迭代器,默认升序,可传比较器</td><td>O(n log n)</td></tr>
<tr><td>lower_bound / upper_bound</td><td>有序区间二分,返回迭代器</td><td>O(log n)</td></tr>
<tr><td>priority_queue<T></td><td>默认大根堆;<code>greater<T></code> 变最小堆</td><td>push/pop O(log n)</td></tr>
<tr><td>stack / queue / deque</td><td>LIFO / FIFO / 双端</td><td>O(1)</td></tr>
<tr><td>map / set(红黑树)</td><td>按键有序;unordered_map/set 为哈希表</td><td>O(log n) / 平均 O(1)</td></tr>
<tr><td>vector</td><td>动态数组,支持随机访问</td><td>push_back 均摊 O(1)</td></tr>
<tr><td>bitset</td><td>位集,NOI 2025 大纲新增,加速 0/1 DP</td><td>位运算按机器字长</td></tr>
</tbody>
</table></div>
<p class="caption">2025 大纲新增 bitset 与更多 STL,初赛可能以阅读程序形式考其行为与复杂度。</p>
</div>
</section>
<section id="years">
<div class="sec-head"><div class="no">5</div><h2>备考建议与真题索引</h2><span class="en">PREP PLAN & REAL-EXAM INDEX</span></div>
<div class="card">
<h3 style="margin-top:0">三轮复习节奏(最后 4 周)</h3>
<div class="two">
<div class="kp">
<b>第 1 周·系统过知识点:</b>按本文档三章(原理 → 公式 → 代码)逐条过,公式当天默写一遍(排列组合、错排、卡特兰、复杂度表),代码模板亲手敲一遍并跑通。
</div>
<div class="kp">
<b>第 2–3 周·限时刷真题:</b>每天一套 2019–2025 真题(单选 ≤30 分钟、阅读 40 分钟、完善 50 分钟),错题按“题型+知识点”记入错题本;陌生代码逐行翻译注释。
</div>
<div class="kp">
<b>第 4 周·查漏补缺:</b>集中背诵错题结论与高频考点(Linux 命令、排序稳定性、DP 转移、位运算优先级);重做错题;考前 3 天只看速记笔记。
</div>
<div class="kp warn">
<b>易错提醒:</b>二分边界混搭(while(l<r) 却写 l=mid)会死循环;交换两数忘存临时变量;回溯忘撤销 flag;完全二叉树 ≠ 满二叉树;卡特兰“n 个结点二叉树”与“n 个结点满二叉树”差一个下标。
</div>
</div>
</div>
<div class="card">
<h3 style="margin-top:0">真题获取渠道(可信度高)</h3>
<ul>
<li><b>NOI 官网</b>(noi.cn):官方通知、CSP 报名与第一轮认证说明、历年试题发布入口。</li>
<li><b>CCF 中国计算机学会</b>(ccf.org.cn / ccsp.ccf.org.cn):CSP 认证官方站点、模拟题与大纲。</li>
<li><b>NOI 大纲 2025 修订版</b>:官方知识点范围(含新增 bitset 等),备考范围以此为准。</li>
<li><b>洛谷</b>(luogu.com.cn):历年真题题单与讨论(如“CSP-S1-2024题目”专栏),社区解析丰富。</li>
<li><b>OI Wiki</b>:算法与数据结构系统讲解,适合补知识短板。</li>
</ul>
</div>
<div class="card">
<h3 style="margin-top:0">2019–2025 真题主题一览(年份 → 主要主题)</h3>
<div class="tbl-scroll"><table class="years">
<thead><tr><th>年份</th><th>主题标签</th></tr></thead>
<tbody>
<tr><td>2025</td><td><span class="tag-chip">排列组合</span><span class="tag-chip">KMP</span><span class="tag-chip">线段树</span><span class="tag-chip">Trie</span><span class="tag-chip">拓扑排序</span><span class="tag-chip">哈希</span><span class="tag-chip">MST</span><span class="tag-chip">BST</span><span class="tag-chip">背包DP</span><span class="tag-chip">LCA</span><span class="tag-chip">主定理</span><span class="tag-chip">堆</span><span class="tag-chip">容斥</span><span class="tag-chip">DFS回溯</span><span class="tag-chip">双蛋问题</span></td></tr>
<tr><td>2024</td><td><span class="tag-chip">Linux</span><span class="tag-chip">复杂度</span><span class="tag-chip">栈溢出</span><span class="tag-chip">排列组合</span><span class="tag-chip">欧拉图</span><span class="tag-chip">二分</span><span class="tag-chip">模逆元</span><span class="tag-chip">哈希</span><span class="tag-chip">位运算</span><span class="tag-chip">状压DP</span><span class="tag-chip">快排</span><span class="tag-chip">次短路</span><span class="tag-chip">树哈希</span></td></tr>
<tr><td>2023</td><td><span class="tag-chip">Linux</span><span class="tag-chip">排列组合</span><span class="tag-chip">哈夫曼</span><span class="tag-chip">图染色</span><span class="tag-chip">LCS</span><span class="tag-chip">概率期望</span><span class="tag-chip">位运算</span><span class="tag-chip">快排最坏</span><span class="tag-chip">树重心</span><span class="tag-chip">拓扑</span><span class="tag-chip">埃氏筛</span><span class="tag-chip">二分答案</span><span class="tag-chip">Dijkstra</span></td></tr>
<tr><td>2022</td><td><span class="tag-chip">Linux</span><span class="tag-chip">逻辑运算</span><span class="tag-chip">栈</span><span class="tag-chip">排序稳定性</span><span class="tag-chip">哈希</span><span class="tag-chip">贪心</span><span class="tag-chip">完全二叉树</span><span class="tag-chip">强连通</span><span class="tag-chip">组合</span><span class="tag-chip">基数排序</span><span class="tag-chip">Base64</span><span class="tag-chip">归并</span><span class="tag-chip">BFS</span></td></tr>
<tr><td>2021</td><td><span class="tag-chip">Linux</span><span class="tag-chip">递归</span><span class="tag-chip">排序稳定性</span><span class="tag-chip">哈夫曼</span><span class="tag-chip">二叉树遍历</span><span class="tag-chip">斐波那契</span><span class="tag-chip">组合</span><span class="tag-chip">最短路</span><span class="tag-chip">区间DP</span><span class="tag-chip">BFS</span><span class="tag-chip">RMQ</span></td></tr>
<tr><td>2020</td><td><span class="tag-chip">进制转换</span><span class="tag-chip">操作系统</span><span class="tag-chip">存储计算</span><span class="tag-chip">栈</span><span class="tag-chip">哈希</span><span class="tag-chip">贪心</span><span class="tag-chip">DFS</span><span class="tag-chip">二分图</span><span class="tag-chip">同余</span><span class="tag-chip">后缀表达式</span><span class="tag-chip">背包</span><span class="tag-chip">DP</span></td></tr>
<tr><td>2019</td><td><span class="tag-chip">Linux</span><span class="tag-chip">逻辑运算</span><span class="tag-chip">编译过程</span><span class="tag-chip">DP</span><span class="tag-chip">组合</span><span class="tag-chip">稳定排序</span><span class="tag-chip">图论</span><span class="tag-chip">进制转换</span><span class="tag-chip">位运算</span><span class="tag-chip">并查集</span><span class="tag-chip">拓扑</span></td></tr>
</tbody>
</table></div>
</div>
</section>
<section id="refs">
<div class="sec-head"><div class="no">6</div><h2>参考资料</h2><span class="en">REFERENCES</span></div>
<div class="card refs">
<ol>
<li>小码王:《必看!CSP-S提高组近5年考点汇总(2019–2024)》,2025-09 发布,xiaomawang.cn</li>
<li>StelaYuri:《CSP-S 2025 初赛解析》,博客园,2025-09,cnblogs.com/stelayuri/p/19103108</li>
<li>new-code / StelaYuri:《CSP-S 2024 提高组初赛试题及答案解析》,博客园,2024-09</li>
<li>严老师编程:《CSP/NOIP历年初赛考点分析(近十年)》,掘金,2022-03,juejin.cn/post/7077354450259542052</li>
<li>NOI 官网:《全国青少年信息学奥林匹克系列竞赛大纲(2025年修订版)》,noi.cn</li>
<li>XMOJ:《CSP-J/S 初赛宝典——NOI 2025 大纲知识体系》,xmoj.top/csp-js</li>
<li>PassCSP:《CSP-J/S 知识点逐个击破》(对照 NOI 2025 大纲),passcsp.cn</li>
<li>洛谷专栏:《CSP-S1-2024题目》《组合数学知识点入门》,luogu.com.cn</li>
<li>CSDN/腾讯云等历年 CSP-S 初赛真题解析(2019–2025 各年)</li>
</ol>
<p style="margin-top:10px">数据与例题均来自上述公开资料交叉核对;图表中的占比与频次为按公开解析的近似统计,具体以每年官方试题为准。</p>
</div>
</section>
</div>
<footer><div class="wrap">
<div>近10年 CSP-S(含 NOIP 提高组)初赛常考内容整理 · 复习讲义</div>
<div>依据 NOI 大纲 2025 修订版 与 2019–2025 公开真题解析整理</div>
</div></footer>
<script src="https://cdn.jsdelivr.net/npm/echarts@5.5.0/dist/echarts.min.js"></script>
<script>
// ===== 图表1:十年考点模块占比(提高组 vs 普及组)=====
var chart1 = echarts.init(document.getElementById('chart1'));
chart1.setOption({
backgroundColor:'transparent',
tooltip:{trigger:'axis',triggerOn:'click',renderMode:'richText',confine:true},
legend:{data:['普及组','提高组'],top:0},
grid:{left:10,right:20,top:40,bottom:10,containLabel:true},
xAxis:{type:'category',data:['编程基础','算法基础','数据结构','信息学基础','数学基础'],
axisLabel:{fontSize:12}},
yAxis:{type:'value',name:'分值占比(%)',max:60,axisLabel:{fontSize:11}},
series:[
{name:'普及组',type:'bar',barWidth:'34%',data:[44.92,22.33,10.92,14.33,7.50],
itemStyle:{color:'#9cc9d1'},label:{show:true,position:'top',fontSize:11,color:'#5b6472'}},
{name:'提高组',type:'bar',barWidth:'34%',data:[36.88,28.13,17.38,11.25,6.38],
itemStyle:{color:'#0f7b8c'},label:{show:true,position:'top',fontSize:11,color:'#0f7b8c'}}
]
});
// ===== 图表2:2019–2025 主题出现年份数 =====
var chart2 = echarts.init(document.getElementById('chart2'));
var topics = ['排序与复杂度分析','图论(最短路/拓扑/欧拉/生成树)','排列组合与计数','动态规划',
'位运算与逻辑运算','树与二叉树','Linux与计算机基础','栈与队列','哈希表','字符串算法(KMP等)',
'数论(同余/逆元/素数)','进制与编码','概率与容斥'];
var years = [7,7,6,6,5,5,5,3,3,3,3,2,2];
chart2.setOption({
backgroundColor:'transparent',
tooltip:{trigger:'axis',triggerOn:'click',renderMode:'richText',confine:true},
grid:{left:10,right:40,top:10,bottom:10,containLabel:true},
xAxis:{type:'value',name:'出现年份数(共7年)',max:8,axisLabel:{fontSize:11}},
yAxis:{type:'category',data:topics,axisLabel:{fontSize:12}},
series:[{type:'bar',data:years,barWidth:'55%',
itemStyle:{color:function(p){return p.value>=6?'#e08a2e':'#0f7b8c';}},
label:{show:true,position:'right',fontSize:11,color:'#1f2733'}}]
});
window.addEventListener('resize',function(){chart1.resize();chart2.resize();});
// ===== 复制按钮 =====
document.querySelectorAll('.copy-btn').forEach(function(btn){
btn.addEventListener('click',function(){
var pre = btn.parentNode;
var code = pre.querySelector('code');
var txt = code.innerText.replace(/\n$/,'');
if (navigator.clipboard && navigator.clipboard.writeText) {
navigator.clipboard.writeText(txt).then(function(){btn.textContent='已复制';setTimeout(function(){btn.textContent='复制';},1200);});
}
});
});
</script>
</div>
</body>
</html>
<!-- (注:内容由AI生成) -->