<!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 &amp; 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&lt;&lt;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>
      ! → 算术(+ - * / %) → 移位(&lt;&lt; &gt;&gt;) → 关系(&lt; &lt;= &gt; &gt;=) → 相等(== !=) → 位与(&amp;) → 异或(^) → 位或(|) → 逻辑与(&amp;&amp;) → 逻辑或(||) → 三目(?:) → 赋值(=)</div>
    <ul>
      <li><b>判据:</b>位运算优先级高于逻辑运算,低于关系运算;赋值优先级最低(除逗号)。</li>
      <li><b>真题点:</b>2023 考位运算优先级(与逻辑运算混算),2025 提示可能混入三目/赋值;<code>a &lt; b &lt; c</code> 是链式比较(先算 a&lt;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 &amp; (x−1) 清除最低位的 1;x &amp; −x = lowbit(x) 取出最低位的 1;a^a=0、0^a=a、异或可交换可结合;x&lt;&lt;k = x·2<sup>k</sup>,x&gt;&gt;k = ⌊x/2<sup>k</sup>⌋</div>
    <ul>
      <li><b>应用:</b>统计二进制中 1 的个数(反复 x&amp;=x−1)、找唯一出现奇数次/缺失元素(全异或)、状态压缩(用 int 位表示集合)。</li>
      <li><b>真题点:</b>2019 阅读程序考位运算函数对称性;2023 阅读程序考 x^=X&lt;&lt;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&lt;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) &lt; O(log n) &lt; O(√n) &lt; O(n) &lt; O(n log n) &lt; O(n²) &lt; O(n³) &lt; O(2ⁿ) &lt; 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 &amp; 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&lt;=r</code> 配 <code>l=mid+1 / r=mid-1</code>(闭区间查找);<code>l&lt;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 &lt;= r) {
        int mid = l + (r - l) / 2;   // 防溢出写法
        if (a[mid] == x) return mid;
        else if (a[mid] &lt; x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

// lower_bound:第一个 &gt;= x 的位置(左闭右开写法)
int lowerBound(int a[], int n, int x) {
    int l = 1, r = n + 1;
    while (l &lt; r) {
        int mid = (l + r) / 2;
        if (a[mid] &gt;= 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 &lt; r; ++j)
        if (a[j] &lt; 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 &gt;= 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 &gt;= 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 &lt;= mid &amp;&amp; j &lt;= r) {
        if (a[i] &lt;= a[j]) tmp[k++] = a[i++];
        else { tmp[k++] = a[j++]; inv += mid - i + 1; }
    }
    while (i &lt;= mid) tmp[k++] = a[i++];
    while (j &lt;= r)   tmp[k++] = a[j++];
    for (int t = 0; t &lt; 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 &lt;stack&gt;
using namespace std;
int evalPostfix(const string&amp; s) {
    stack&lt;int&gt; st;
    for (char c : s) {
        if (c &gt;= '0' &amp;&amp; c &lt;= '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 &gt; 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 &lt;= n; ++i) {
        if (flag[i]) continue;
        if (k &gt; 1 &amp;&amp; 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 &lt;queue&gt;
using namespace std;
typedef pair&lt;int,int&gt; 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&lt;pii&gt; 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 &lt; 4; ++k) {
            int nx = u.first + dx[k], ny = u.second + dy[k];
            if (nx &lt; 1 || nx &gt; n || ny &lt; 1 || ny &gt; 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 &lt;queue&gt;
#include &lt;vector&gt;
using namespace std;
typedef pair&lt;int,int&gt; pii;      // (距离, 顶点)
const int INF = 0x3f3f3f3f;
vector&lt;pii&gt; e[MAXN];            // e[u] = {(v, w), ...}
int dist[MAXN];
void dijkstra(int s, int n) {
    for (int i = 1; i &lt;= n; ++i) dist[i] = INF;
    dist[s] = 0;
    priority_queue&lt;pii, vector&lt;pii&gt;, greater&lt;pii&gt; &gt; 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 &lt; e[u].size(); ++i) {
            int v = e[u][i].first, w = e[u][i].second;
            if (dist[u] + w &lt; 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 &lt;= n; ++k)
    for (int i = 1; i &lt;= n; ++i)
        for (int j = 1; j &lt;= n; ++j)
            if (d[i][k] + d[k][j] &lt; 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&amp; a, const Edge&amp; b) { return a.w &lt; 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 &lt;= 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 再入队。队列输出顺序即一个拓扑序。若最终排序数 &lt; n 说明有环。2025 考“DAG 拓扑排序方案数取决于结构”,2023 考拓扑排序删边。
    </div>
<pre><span class="cap">拓扑排序(Kahn)</span><button class="copy-btn">复制</button><code>#include &lt;queue&gt;
using namespace std;
queue&lt;int&gt; q;
int indeg[MAXN];
vector&lt;int&gt; e[MAXN], topo;
void topoSort(int n) {
    for (int i = 1; i &lt;= 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 &lt; 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 &lt;= n; ++i)
    for (int j = V; j &gt;= w[i]; --j)        // 逆序:保证每件物品至多取一次
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
// 完全背包只需把容量循环改为正序:for (int j = w[i]; j &lt;= 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 &lt;= n; ++i) {
    dp[i] = 1;
    for (int j = 1; j &lt; i; ++j)
        if (a[j] &lt; a[i]) dp[i] = max(dp[i], dp[j] + 1);
}
// LCS:a[1..n], b[1..m]
for (int i = 1; i &lt;= n; ++i)
    for (int j = 1; j &lt;= 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 &lt;= n; ++len)              // 枚举区间长度
    for (int i = 1; i + len - 1 &lt;= n; ++i) {
        int j = i + len - 1;
        f[i][j] = INF;
        for (int k = i; k &lt; 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 &amp; 1) r = r * a % m;
        a = a * a % m;
        b &gt;&gt;= 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 &lt;= n; ++i)
    if (!isComp[i])
        for (long long j = 1LL * i * i; j &lt;= 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 &lt;= n; ++i) {
    if (!isComp[i]) prime[++pcnt] = i;
    for (int j = 1; j &lt;= pcnt &amp;&amp; 1LL * i * prime[j] &lt;= 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&amp; x, int&amp; 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&amp; p) {
    int m = (int)p.size();
    nxt[0] = 0;
    for (int i = 1, j = 0; i &lt; m; ++i) {
        while (j &gt; 0 &amp;&amp; p[i] != p[j]) j = nxt[j - 1];
        if (p[i] == p[j]) ++j;
        nxt[i] = j;
    }
}
int kmp(const string&amp; s, const string&amp; p) {   // 返回首次匹配位置
    int n = (int)s.size(), m = (int)p.size();
    for (int i = 0, j = 0; i &lt; n; ++i) {
        while (j &gt; 0 &amp;&amp; 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 &amp; -x; }       // 取最低位 1 的值

int popcount(int x) {                      // 二进制中 1 的个数
    int c = 0;
    while (x) { x &amp;= x - 1; ++c; }
    return c;
}

// 枚举集合 mask 的所有非空子集 s
for (int s = mask; s; s = (s - 1) &amp; mask) {
    // 处理子集 s
}</code></pre>
  </div>

  <div class="card">
    <h3>4.18 高精度加法</h3>
    <div class="kp">
      <b>讲解:</b>数字按低位在前存入 vector&lt;int&gt;,逐位相加并处理进位。阅读程序常以“大数相加/阶乘”为背景。
    </div>
<pre><span class="cap">高精度加法(低位在前)</span><button class="copy-btn">复制</button><code>#include &lt;vector&gt;
using namespace std;
vector&lt;int&gt; add(const vector&lt;int&gt;&amp; a, const vector&lt;int&gt;&amp; b) {
    vector&lt;int&gt; c;
    int t = 0;
    int n = max(a.size(), b.size());
    for (int i = 0; i &lt; n || t; ++i) {
        if (i &lt; (int)a.size()) t += a[i];
        if (i &lt; (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&lt;T&gt;</td><td>默认大根堆;<code>greater&lt;T&gt;</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 &amp; 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&lt;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生成) -->