CSP-J 专题：按考点大纲分模块讲解 + 第一轮真题

本专题依据 CSP-J 第一轮笔试的考察范围（CCF NOI 大纲「入门级」+ 近年 CSP-J1 试卷覆盖的考点），将核心知识重组为 11 个考点模块 + 真题总览。每个模块拆分为具体知识点：先给出讲解细节与易错点，再附可编译的 C++17 示例，最后挂接 2019 - 2026 年对应考点的真题（单选、阅读程序、完善程序）。真题区块支持按年份筛选，参考答案、解析与考点标签统一列在每套题末尾。

使用建议：按模块顺序逐个突破（01→11），理解每个知识点的命题角度；完成模块真题后，到文末「真题总览」做整套限时模拟；错题回看对应模块讲解。

模块一 · 计算机基础知识

1.1 进制转换与位权

是什么 / 为什么考：进制是计算机存储与计算的底层语言——机器内部一切数据最终都以二进制存储，而二进制写起来又长又难读，于是人们用八进制、十六进制做「缩写」。CSP-J1 几乎每年必考进制转换（2025 单选第 13 题、2026 单选第 2 题），是稳定送分点。

详细原理：

• 任意 R 进制数按「位权展开」即可转十进制：从右往左第 i 位（i 从 0 起）的权值是 R^i，数值 = Σ 数字×R^i。
• 例如 1011₂ = 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8+0+2+1 = 11。
• 十进制转 R 进制用「除 R 取余、逆序排列」：以 13 转二进制为例——13÷2=6 余 1，6÷2=3 余 0，3÷2=1 余 1，1÷2=0 余 1，把余数从下往上读得 1101₂。
• 二⇄八进制按 3 位一组、二⇄十六进制按 4 位一组（8421 法）快速换算：如 1101 0100₂ 分两组，1101=13=D、0100=4，得 D4₁₆。

考法总结：

• 真题 2025-13 考「720₁₀ + 270₈ 用十六进制表示」，套路是先统一成十进制（或二进制）再求和、再转目标进制；
• 2026-2 考「2F5₁₆ 转八进制」，推荐路径 十六→二→八：每位十六进制拆 4 位二进制，再每 3 位并 1 位八进制。
• 单选常考，也可能混入阅读/完善程序（如 2026 完善程序第 34~37 题的 mn 进制转 n 进制）。

易错点：

1. 除 R 取余必须「逆序」读余数，顺序读必错；
2. 十六进制 A~F 表示 10~15，F 是 15 不是 16；
3. 八进制没有数字 8、二进制没有数字 2；
4. 十进制 0 转任意进制要特判输出 "0"。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
// 十进制转 n 进制（n <= 16），输出字符串
string toBase(long long x, int n) {
    if (x == 0) return "0";
    string s = "";
    while (x > 0) {
        int r = x % n;
        char c = (r < 10) ? char('0' + r) : char('A' + r - 10);
        s = c + s;
        x /= n;
    }
    return s;
}
int main() {
    cout << toBase(270, 8) << endl;   // 十进制 270 = 八进制 416
    cout << toBase(388, 16) << endl;  // 十进制 388 = 十六进制 184
    cout << toBase(13, 2) << endl;    // 十进制 13 = 二进制 1101
    return 0;
}

延伸阅读与参考：OI Wiki《进制》讲透位权展开与 R 进制互转；洛谷题单「入门与面试」进制相关题目；《信息学奥信一本通（C++版）》第一章进制与编码；noi.hnai.net 2020-2024 年真题均有进制计算题（如 2020 单选第 9 题、2022 单选第 13 题、2023 单选第 2/9 题、2024 单选第 2 题）。

1.2 信息单位：bit、Byte、KB/MB/GB/TB 换算

是什么 / 为什么考：硬件常识题在 CSP-J1 中偶尔出现，主要是存储单位换算（KB/MB/GB 的 1024 进制）与基本硬件角色判断。属于「背了就有分」的概念题。

详细原理：

考法总结：

1. 命题角度主要有：
2. 单位换算（如 1 MB = 1024 KB = 1048576 B）；
3. 与 2^n 计算结合（8 位二进制 256 个值）。真题直接考得不多，但单位换算与 2^n 是进制题、容量题的基础。

易错点：

1. 换算用 1024 而非 1000；
2. bit 与 Byte 差 8 倍，1 KB = 8 Kbit；

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    // 存储单位换算：1 KB = 1024 B
    long long kb = 1LL * 1024;                 // 1 KB 的字节数
    long long mb = kb * 1024;                  // 1 MB 的字节数
    cout << kb << ' ' << mb << endl;           // 1024 1048576
    // 8 位二进制能表示 2^8 = 256 个不同值（0~255）
    cout << (1 << 8) << endl;                  // 256
    return 0;
}

1.3 原码、反码、补码（整数表示与范围）

是什么 / 为什么考：计算机内存有限，整数用固定位数存储，能表示的范围由位数决定。2025 单选第 1 题与 2026 单选第 1 题都直接考范围估算与类型选择，属于必考的基础概念。

详细原理：

• n 位二进制可表示 2^n 个不同值。
• 32 位有符号 int 用最高位作符号位，范围 [-2³¹, 2³¹-1] = -2147483648 ~ 2147483647；
• 32 位无符号整数范围 [0, 2³²-1] = 0 ~ 4294967295 ≈ 4.29×10⁹，所以 2025-1 选「4×10⁹」。
• 负数以补码存储（取反加一）：-1 的 32 位补码是 32 个 1。
• 溢出是「静默回绕」：2147483647+1 会变成 -2147483648，不报任何错误。
• 64 位 long long 范围约 ±9.2×10¹⁸（19 位十进制数），2026-1 的 10¹⁸+1 只有 long long 能精确存下（float/double 有精度损失）。

• 边界：unsigned int 溢出回绕成巨大正数；
• 1 << 31 对 int 是负的。

考法总结：

• 2025-1（32 位无符号最大值 ≈4×10⁹）与 2026-1（10¹⁸+1 需要 long long）说明命题角度是「给一个数或算式，判断用哪种类型存得下、会不会溢出」。
• 估算技巧：10⁹ 级别用 int，10¹⁸ 级别用 long long；
• 两个 int 相乘优先考虑提升 long long。

易错点：

1. 溢出不报错，静默回绕成负数/小值；
2. int 与 long long 混算自动提升为 long long（避免一半溢出）；
3. unsigned 溢出回绕成巨大正数；
4. 1 << 31 等于 -2147483648，需写 1LL << 31 才安全。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    cout << (int)2147483647 << endl;          // int 最大值
    cout << (long long)2147483647 * 2 << endl;// 用 long long 防溢出
    cout << (int)-1 << endl;                  // 补码全 1 的 -1
    int x = 1 << 30;                          // 2^30 不溢出
    cout << x << ' ' << (1 << 31) << endl;    // 1073741824，1<<31 溢出为负
    return 0;
}

延伸阅读与参考：OI Wiki《变量》与《二进制》解释补码与范围；《信息学奥信一本通（C++版）》第二章数据类型；noi.hnai.net 2024 单选第 1 题（32 位 int 范围）、2025 单选第 1 题（无符号整型最大值）直接考察。

1.4 计算机组成与冯诺依曼体系

硬件角色：

• 程序运行流程：输入设备 → 内存 → CPU → 输出设备。
• 8 位二进制能表示 2⁸ = 256 个不同值（0~255）。

1. 内存 RAM 断电丢数据，外存不丢；
2. 程序必须先载入内存才能被 CPU 执行。

延伸阅读与参考：参考《信息学奥信一本通（C++版）》第一章计算机基础知识（冯·诺依曼结构、存储单位 1024 进制）；洛谷「计算机基础知识」题单；noi.hnai.net 2023 单选第 13 题（存储容量比较）、2024 单选第 5 题（KB/MB 换算）、2020 单选第 4 题（位图容量）。

1.5 操作系统、文件与网络基础（IP、域名）

是什么 / 为什么考：操作系统、文件系统与网络基础属于 CSP-J 的「计算机常识」考点：操作系统管资源，路径分绝对/相对，IP 与域名靠 DNS 关联，常以单选判断形式出现。

详细原理：

• 操作系统（OS）是管理硬件与软件资源的系统软件：进程管理、内存管理、文件管理、设备管理；常见 OS：Windows、Linux、macOS、Android、iOS；
• 文件系统：文件按目录组织，路径分绝对路径（从根目录开始，如 C:\cpp\a.cpp）与相对路径（相对当前目录）；扩展名表示类型（.exe 可执行、.txt 文本、.cpp 源码）；
• 网络基础：IP 地址是网络中的「门牌号」（IPv4 如 192.168.1.1，32 位；IPv6 128 位）；域名（如 www.noi.cn）是 IP 的「好记名字」，DNS 负责把域名解析成 IP；
• 常见协议：HTTP/HTTPS（网页，HTTPS 多一层加密）、FTP（文件传输）、TCP/IP（传输控制协议/网际协议）。

考法总结：

1. 操作系统与硬件、应用软件的关系判断；
2. 绝对/相对路径、文件扩展名识别；
3. IP 地址、域名与 DNS 的作用。

易错点：

1. 操作系统是系统软件，不是硬件也不是应用软件；
2. 域名不是 IP，需要 DNS 解析才能通信；
3. HTTP 与 HTTPS 区别在加密传输（SSL/TLS）。

示例（模拟初赛单选题）：

1. 下列说法正确的是（　）。
   A．操作系统属于应用软件　B．域名就是 IP 地址
   C．HTTPS 比 HTTP 多一层加密传输　D．相对路径以盘符开头
   答案：C。HTTPS 在 HTTP 之上增加了 SSL/TLS 加密层。
2. 访问 www.noi.cn 时，浏览器先通过（　）把域名解析成 IP 地址。
   A．DNS　B．FTP　C．DHCP　D．SMTP
   答案：A。DNS（域名系统）负责域名到 IP 的解析。

延伸阅读与参考：OI Wiki《杂项》计算机基础；《信息学奥信一本通（C++版）》第一章计算机基础知识；相关真题见下方真题总览。

1.6 信息安全：病毒、木马、版权与知识产权

是什么 / 为什么考：信息安全与知识产权是 CSP-J 的「道德法规」考点：病毒/木马特性、防火墙作用、版权与个人信息保护，常以 1-2 道单选出现。

详细原理：

• 计算机病毒：能自我复制、破坏系统/数据的恶意代码，必须依附宿主程序运行；木马：伪装成正常程序、暗中开后门窃取信息，一般不会自我复制传播（与病毒的主要区别）；
• 防火墙：过滤进出网络的数据包，防止外部非法访问；杀毒软件：查杀病毒与木马；
• 版权与知识产权：软件受《著作权法》保护，盗版软件侵权；自由软件（可自由使用修改传播）不等于免费软件；
• 个人信息保护：不泄露密码、不点击不明链接、及时更新系统补丁。

考法总结：

1. 病毒与木马的区别判断；
2. 防火墙的作用（防外部非法访问）；
3. 版权法对软件的保护与盗版判断。

易错点：

1. 病毒通常不直接破坏硬件，主要破坏软件/数据；
2. 木马的主要目的是窃取信息而非自我复制传播；
3. 免费软件不一定开源，开源软件也要遵守许可证。

示例（模拟初赛单选题）：

1. 与计算机病毒相比，木马的主要特点是（　）。
   A．能自我复制并主动传播　B．伪装成正常程序暗中窃取信息
   C．只破坏硬件设备　D．只能通过电子邮件传播
   答案：B。木马重在伪装与开后门，一般不自我复制传播。
2. 未经许可复制并传播他人开发的商业软件，属于（　）行为。
   A．合理使用　B．侵犯知识产权　C．正当防卫　D．网络互助
   答案：B。软件受《著作权法》等知识产权法规保护。

延伸阅读与参考：《信息学奥信一本通（C++版）》第一章信息安全常识；中国计算机学会 NOI 竞赛规则（诚信与版权条款）；相关真题见下方真题总览。

1.7 字符编码与 ASCII

是什么 / 为什么考：字符在计算机里本质是整数，字符与整数之间的桥梁就是编码表。CSP-J 阅读程序题里经常出现字符运算（'0'+3、c-'0'、大小写转换），是高频小考点。

详细原理：

• 常用 ASCII 锚点：'A'=65、'a'=97、'0'=48，同一字母大小写相差 32（97-65=32）。
• 由此：大写转小写 +32，小写转大写 -32；
• 数字字符转数字 '3'-'0'=3；
• 数字转字符 char('0'+3)='3'。
• 字符参与算术时自动提升为 int。

• 边界：'0'~'9' 连续占 48~57，'A'~'Z' 占 65~90，'a'~'z' 占 97~122；
• 记住 48/65/97 三个锚点几乎能推出所有常见字符运算。

考法总结：

• 多出现在阅读程序题中：算 (int)('A')、判断 isdigit/isalpha、字符与数字互转；
• 也常与字符串处理结合（如 RLE 解码里的 s[i]-'0'）。
• 看到「字符 + 数字」的表达式，第一步就是换成 ASCII 整数再算。

易错点：

1. '0' 的 ASCII 是 48，不是 0；
2. 数字字符转数字必须 c-'0'，直接 (int)c 得到的是 48+；
3. 大写转小写是 +32，不是 +26；
4. 字符比较（如 '9' < 'a'）也按 ASCII 值比较。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    char c1 = 'A', c2 = 'a', c3 = '0';
    cout << (int)c1 << ' ' << (int)c2 << ' ' << (int)c3 << endl; // 65 97 48
    cout << char(c2 - 32) << endl;  // 'a' - 32 = 'A'
    cout << char(c3 + 3) << endl;   // '0' + 3 = '3'
    cout << (c3 - '0') << endl;     // 字符转数字：3
    return 0;
}

延伸阅读与参考：OI Wiki《字符类型》列全 ASCII 表与字符运算；《信息学奥信一本通（C++版）》字符与字符串章节；noi.hnai.net 2024 单选第 8 题（char 算术运算）、历年阅读程序中的 c-'0' / 大小写转换均基于 48/65/97 锚点。

1.8 逻辑运算与真值表

• 逻辑运算 && || ! 处理布尔值，有短路求值；
• 德摩根律：!(A&&B) = !A || !B。

易错点：

1. 位 & 与逻辑 && 不能混（12&7=4，12&&7=1）；

1. 2025-7 考布尔代数化简选「不等价」表达式（用真值表或提取公因子验证）；

模块二 · C++ 程序基础语法

2.1 变量类型：int/long long/char/bool/double 与取值范围

是什么 / 为什么考：类型是 C++ 程序的地基：每个变量有类型，类型决定它能存什么、占多大空间。2026 单选第 1 题的「精确存储 10¹⁸+1」就是类型选择考点。

详细原理：

• 常用类型：int（32 位整数，约 ±2.1×10⁹）、long long（64 位整数，约 ±9.2×10¹⁸）、char（1 字节字符，本质是小整数）、bool（布尔 true/false）、double（8 字节浮点，有精度损失）。
• 强制类型转换：static_cast<int>(d) 或 (int)d，浮点转 int 直接截断小数部分（3.9 → 3，不是四舍五入）。
• 混合运算：int 与 long long 混算自动提升为 long long；
• int/int 结果仍是 int（7/2=3）。

考法总结：

• 单选常考「哪个类型能精确存下某数」：整数→整型，要精确→不能选浮点（float/double 有精度损失）；
• 阅读程序考输出类型：int 截断、char 输出字符、float 输出小数。
• 看到 10^n 数量级先判断：<2.1×10⁹ 用 int，否则 long long。

易错点：

1. int/int 得 int，5/2=2 不是 2.5；
2. double 转 int 是截断不是四舍五入；
3. char 变量用 cout 输出的是字符不是数字；
4. 局部变量未初始化时值不确定（全局变量自动清零）。

2.2 输入输出：cin/cout 与 printf/scanf

• 输入 cin >> x 按空白分隔读取，输出 cout << x。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int a; long long b; char c;
    cin >> a >> b >> c;            // 输入：10 10000000000 A
    double d = 3.9;
    cout << a + b << endl;         // 整型提升为 long long
    cout << (int)d << ' ' << static_cast<int>(d) << endl; // 3 3 截断小数
    cout << (a / 4) << endl;       // 10/4 = 2（int/int 得 int）
    return 0;
}

延伸阅读与参考：OI Wiki《输入输出》讲 cin/cout 与 scanf/printf 区别；《信息学奥信一本通（C++版）》第二章；noi.hnai.net 2024 单选第 6/7 题（基本数据类型、循环语句）属此基础。

2.3 运算符：算术、关系、逻辑、自增自减、三目

易错点：

1. 同一表达式中对同一变量多次自增是未定义行为，笔试按常见编译器行为理解；
2. 移位优先级低于加减；
3. &&/|| 短路：左边已定结果时不执行右边（0 && (1/0) 不会除零报错）；
4. 赋值优先级最低：a=b=3 从右往左结合。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int x = 10;
    cout << x++ << ' ' << x << endl;  // 先取原值 10，再自增 -> 10 11
    cout << ++x << ' ' << x << endl;  // 先自增再取新值 -> 12 12
    // 优先级：1<<(2+3) = 1<<5 = 32
    cout << (1 << 2 + 3) << endl;     // 32
    cout << (3 + 4 * 2) << endl;      // 11
    return 0;
}

2.4 运算符优先级与表达式求值

是什么 / 为什么考：表达式求值是阅读程序题的「第一关」，优先级与结合性错了整题就废。CSP-J 阅读/完善程序几乎每套都有表达式输出题。

详细原理：

• C++ 优先级（从高到低）速记：括号 () → 单目（! ~ ++ -- 负号）→ 乘除取模（* / %）→ 加减（+ -）→ 移位（<< >>）→ 关系（< <= > >=）→ 相等（== !=）→ 位与 & → 异或 ^ → 位或 | → 逻辑与 && → 逻辑或 || → 三目 ?: → 赋值 =。
• 关键陷阱：移位优先级低于加减，所以 1 << 2 + 3 = 1 << (2+3) = 1<<5 = 32。
• 自增自减：x++ 先取原值再自增，++x 先自增再取新值。

考法总结：

1. 常见角度：
2. 给表达式求值（混入 ++、移位、位运算）；
3. 判断 a++ 与 ++a 的先后；
4. 优先级陷阱（1<<2+3、a<b==c）。做法：拿不准就在草稿纸上加括号逐层化简。

延伸阅读与参考：OI Wiki《运算符》有完整优先级表；《信息学奥信一本通（C++版）》第三章运算符；noi.hnai.net 2025 单选（x & (x-1)）、2026 单选涉及表达式求值顺序，先记优先级再算值。

2.5 整数除法与取模

是什么 / 为什么考：C++ 的整数除法「向 0 截断」、取模符号「随被除数」，与数学里的除法不同，是新手最容易踩的坑，也是 CSP-J 真题明确考点（2026 单选第 3 题）。

详细原理：

• int 除法结果向 0 截断：7/2=3，-7/2=-3（注意不是 -4，-4 是向下取整）。
• 取模 a%b 的符号与被除数 a 一致（C++11 标准）：-7%2=-1，7%-2=1。
• 判断整除：a%b==0（与符号无关）。
• 恒等式：(a/b)*b + a%b == a（商×除数+余数=被除数）。

• 边界：除数为 0 直接运行时错误。

考法总结：

• 真题 2026-3 直接考「a/b*b + a%b 的值」（答案是还原 a）；
• 阅读程序中常见 i%2 判奇偶、n%10 取末位。
• 负数除法与取模符号是高频陷阱，看到负数就画数轴想「向 0 截断」。

易错点：

1. -7/2 是 -3 不是 -4（向 0 截断而非向下取整）；
2. 取模符号随被除数：-7%2=-1；
3. 除数为 0 报错；
4. 用恒等式 a/b*b+a%b==a 可验算除法/取模。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    cout << (7 / 2) << ' ' << (-7 / 2) << endl;   // 3 -3（向 0 截断）
    cout << (-7 % 2) << ' ' << (7 % -2) << endl;  // -1 1（符号随被除数）
    cout << (7 % 2) << endl;                      // 1
    return 0;
}

延伸阅读与参考：OI Wiki《数论》与《运算符》说明取模语义；《信息学奥信一本通（C++版）》第三章；noi.hnai.net 2020 单选第 13 题（干支纪年取余）、2023 单选第 2 题（八进制加法）体现余数应用。

2.6 位运算

是什么 / 为什么考：位运算是 CSP-J 高频考点：2025-2 考 x&(x-1)、2025-7 考布尔代数化简，几乎每年单选都有一道。位运算也是后续算法（状态压缩、快速幂）的基础。

详细原理：

• 常用技巧：x&1 判奇偶；
• x&(x-1) 把最低位的 1 清 0——推演 2025-2：255 = 11111111₂，255-1 = 11111110₂，按位与得 11111110₂ = 254；
• a^a=0、a^0=a（异或自反，可找唯一出现奇数次的数）；
• 1<<k = 2^k。

考法总结：

1. 2025-2 考 x&(x-1) 具体值；
2. 阅读程序常考 (x>>k)&1 取第 k 位、异或交换两数。
3. 看到位运算先转二进制逐位推，别心算。

1. ~x = -x-1；
2. 1<<31 对 int 溢出为负数，用 1LL<<k；
3. 移位超过位数（int 移 ≥32 位）是未定义行为。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int x = 12;                    // 1100b
    cout << (x & 1) << endl;       // 奇偶判断：0
    cout << (x & (x - 1)) << endl; // 清除最低位 1：8（1000b）
    cout << (1 << 4) << endl;      // 2^4 = 16
    cout << (x ^ x) << endl;       // 异或自反：0
    cout << (~x) << endl;          // -13（~12 = -13）
    return 0;
}

延伸阅读与参考：OI Wiki《位运算》系统讲解 & | ^ ~ << >> 与 lowbit 技巧；《信息学奥信一本通（C++版）》位运算章节；noi.hnai.net 2019 单选第 2 题（逐位与）、2021 阅读第 16-21 题（lowbit 统计 1）、2024 单选第 4 题（格雷码）。

2.7 分支：if、if-else、switch

是什么 / 为什么考：分支与循环是所有程序的「骨架」，阅读程序题的本质就是「跟着代码走一遍流程」，循环边界是最常挖的坑。

详细原理：

• if/else if/else 从上往下匹配第一个为真的分支；
• switch 按值跳转，每个 case 末尾要 break（忘记 break 会「穿透」继续执行后续 case）。

延伸阅读与参考：OI Wiki《语言基础》if/switch/for/while 语法；《信息学奥信一本通（C++版）》第四章流程控制；noi.hnai.net 2019 单选第 4 题（循环次数）、2024 单选第 7 题（循环语句识别）。

2.8 循环：for、while、do-while 与执行次数计算

• for(初始化; 条件; 更新) 先判断条件再执行循环体；
• while 先判断后执行；
• do-while 至少执行一次。
• break 跳出整个循环；
• continue 跳过本次剩余语句进入下一轮（for 里会先执行更新表达式再判断）。

考法总结：

1. 阅读程序题要求手推循环输出，常见陷阱：
2. 边界 <n 还是 <=n；
3. 循环体内修改循环变量（如 i+=2 跳变）；
4. continue 跳过部分；
5. 双重循环的计数（内层总执行次数 = 外层 × 内层）。完善程序题常考「补全循环条件」。

易错点：

1. continue 在 for 中会先执行更新表达式再判断；
2. 边界差一导致多算/少算一次；
3. do-while 至少执行一次（条件在最后判断）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    // 1..10 累加：注意循环边界 <= n
    int sum = 0;
    for (int i = 1; i <= 10; i++) sum += i;
    cout << sum << endl;                     // 55
    // 输出 1..10 中的奇数（continue 跳过偶数）
    for (int i = 1; i <= 10; i++) {
        if (i % 2 == 0) continue;
        cout << i << ' ';
    }
    cout << endl;                            // 1 3 5 7 9
    return 0;
}

2.9 数组：一维、二维与高精度（下标从 0 开始）

是什么 / 为什么考：数组是最基础的数据容器，几乎所有程序题都离不开。CSP-J 阅读程序里数组是主角（下标、越界、未初始化都是考点）。

详细原理：

• 数组是连续内存里的同类型元素序列，下标从 0 开始：int a[5] 合法下标是 a[0]~a[4]。
• 二维数组 int b[n][m] 按「行优先」存储：b[i][j] 的地址 = 首地址 + (i×m+j)×sizeof(int)。
• 全局数组自动清零；
• 局部数组不初始化则值不确定（垃圾值）。
• 越界访问不会报错（C++ 不检查），但会读到相邻内存，结果不可预测。

考法总结：

1. 阅读程序常考：
2. 循环遍历累加/找最值；
3. 下标计算（行优先 i*m+j）；
4. 越界陷阱（边界差一）；
5. 二维数组按行/按列遍历的区别。完善程序常补全遍历条件。

易错点：

1. 声明 int a[5] 后不能访问 a[5]（合法下标 0~4）；
2. 越界不报错但结果不可预测；
3. 局部数组不初始化是垃圾值、全局数组是 0；
4. 二维数组作为函数参数时第二维大小通常必须显式指定。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int a[5] = {3, 7, 2, 9, 4};
    int mx = a[0], mn = a[0], sum = 0;
    for (int i = 0; i < 5; i++) {         // 注意下标 0..4
        if (a[i] > mx) mx = a[i];
        if (a[i] < mn) mn = a[i];
        sum += a[i];
    }
    cout << mx << ' ' << mn << ' ' << sum << endl;    // 9 2 25
    int b[2][3] = {{1, 2, 3}, {4, 5, 6}}; // 二维：2 行 3 列
    cout << b[1][2] << endl;              // 6
    return 0;
}

延伸阅读与参考：OI Wiki《数组》讲下标、越界与多维数组；《信息学奥信一本通（C++版）》第五章数组；noi.hnai.net 2019 阅读第 22-27 题（双序列配对）、2022 阅读第 16-21 题（按位重排）涉及数组模拟。

是什么 / 为什么考：当数字超过 long long（约 9.2×10¹⁸）就得「手算」——用数组模拟竖式。2026 年完善程序直接考高精度加法（2026-22~25），是 CSP-J 必会基本功。

详细原理：

• 思路 = 把大数逐位拆开存进数组（低位在前方便进位），模拟竖式相加：sum = a[i]+b[i]+carry；
• c[i] = sum%10；
• carry = sum/10。
• 字符串读入后先逆序存储（个位存下标 0）。

• 边界：最高位可能多出一个进位（循环条件 i<n || carry）。

考法总结：

1. 2026-22~25 考高精度加法的判断题+选择题：低位在前存储、进位处理、结果长度。考点集中在：
2. 逆序存储；
3. 进位 carry 的传递；
4. 最高位进位导致结果多一位；
5. 字符串转数组的写法。完善程序常让补全「进位」语句。

易错点：

1. 存储方向不一致（低位在前 vs 高位在前）会全错；
2. 最高位进位不能丢（如 999+1=1000）；
3. 结果长度 = max(la,lb) 或 +1；
4. 字符串转数字要 s[i]-'0'。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 高精度加法：vector 低位在前，返回结果（同样低位在前）
vector<int> addBig(const vector<int> &a, const vector<int> &b) {
    vector<int> c;
    int carry = 0, n = max(a.size(), b.size());
    for (int i = 0; i < n || carry; i++) {
        int sum = carry;
        if (i < (int)a.size()) sum += a[i];
        if (i < (int)b.size()) sum += b[i];
        c.push_back(sum % 10);
        carry = sum / 10;
    }
    return c;
}
int main() {
    // 1234 + 9876 = 11110，均低位在前存储
    vector<int> a = {4, 3, 2, 1}, b = {6, 7, 8, 9};
    vector<int> c = addBig(a, b);
    for (int i = (int)c.size() - 1; i >= 0; i--) cout << c[i];
    cout << endl;                         // 11110
    return 0;
}

延伸阅读与参考：OI Wiki《高精度》完整讲解大数加减乘除与压位；《信息学奥信一本通（C++版）》高精度章节；noi.hnai.net 2023 单选第 7 题（高精度运算概念）直接考察。

2.10 字符串：string 常用操作与字符处理

是什么 / 为什么考：string 是 C++ 字符串的「正规军」，2025 单选第 9 题直考 string 基本性质，字符串处理也是阅读/完善程序的常客。

详细原理：

• string 是可变长度字符串类，常用操作：+ 拼接（string+string、string+char 均可，2025-9 正确选项即与此相关）、[] 下标访问、length()/size()（两者完全等价，返回 size_t 无符号数）、substr(pos,len) 取子串、find(ch/str) 查找（找不到返回 string::npos，是巨大的 size_t 值）。
• 与 C 风格字符数组不同：string 不以 '' 结尾（C++11 起内部含 '' 但不计入 length）。
• 关键陷阱：s.size()-1 在空串时等于巨大无符号数（18446744073709551615），用于循环条件会出大问题。

考法总结：

• 2025-9 考概念判断题（length/size 等价、+ 可拼接 char、不以 '' 结尾）；
• 阅读程序考 substr/find/下标遍历；
• 完善程序考字符串处理逻辑。
• 看到 string 操作先想返回类型：size() 是 size_t，find 失败是 npos。

易错点：

1. s.size() 是无符号数，空串时 size()-1 巨大；
2. substr 越界会抛异常；
3. find 失败返回 npos（通常 18446744073709551615）不是 -1；
4. length() 与 size() 完全等价，均不含结尾 ''。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s = "CSP-J2026";
    cout << s.length() << ' ' << s.size() << endl;    // 9 9
    cout << s.substr(4, 4) << endl;       // "J202"
    cout << (int)s.find('J') << endl;     // 4
    string t = s + " OK";
    cout << t << endl;                    // CSP-J2026 OK
    // size_t 陷阱：空串 size()-1 是巨大无符号数
    string e = "";
    cout << (e.size() - 1) << endl;       // 18446744073709551615
    return 0;
}

延伸阅读与参考：OI Wiki《字符串》覆盖 string 常用成员与 STL 字符串；《信息学奥信一本通（C++版）》第六章字符串；noi.hnai.net 2021 阅读第 22-27 题（Base64 解码）、2023 阅读第 21-26 题（LCS 字符串）大量使用。

是什么 / 为什么考：RLE（行程长度编码）是 2025 年阅读程序大题（2025-34~37），属于「编码/解码」类经典题，考察字符串逐字符解析与多位数字累积。

详细原理：

• RLE 压缩规则：连续 N 个相同字符 → 「字符+数字N」（如 AAAAA → A5；
• "A12" 表示 12 个 A）。
• 解码（还原）逻辑：从左到右，先读数字 cnt（可能多位！用 cnt = cnt*10 + (c-'0') 累积），再读一个字符 ch，输出 cnt 个 ch。

• 字符分类函数：isdigit(c)（数字）、isalpha(c)（字母）、toupper/tolower（大小写）。
• 边界：原串不含数字字符时，读到的数字一定是「个数」；
• 单个字符也要带个数（如 1C 表示 1 个 C）。

考法总结：

1. 2025-34~37 围绕 RLE 解码出判断题+选择题（输出结果、算法思想）；这类「编码-解码」题型考察：
2. 逐字符解析的循环结构；
3. 多位数字累积；
4. 输出拼接。阅读程序看到「数字+字符」组合，立即想到累积计数。

易错点：

1. 多位数字必须循环累积（cnt*10+...），不能只取一位；
2. 解码顺序：先数字后字符（压缩是字符+数字，解码反过来）；
3. 用 isdigit 判断数字字符；
4. 读完数字后注意字符串下标越界。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <string>
using namespace std;
string rleDecode(const string &s) {
    string res = "";
    int i = 0;
    while (i < (int)s.size()) {
        int cnt = 0;
        while (i < (int)s.size() && isdigit(s[i])) // 多位数字累积
            cnt = cnt * 10 + (s[i++] - '0');
        char ch = s[i++];
        for (int k = 0; k < cnt; k++) res += ch;
    }
    return res;
}
int main() {
    cout << rleDecode("3A2B1C") << endl;  // AAABBC
    cout << rleDecode("12A1B") << endl;   // AAAAAAAAAAAAB（12 个 A）
    return 0;
}

延伸阅读与参考：OI Wiki《字符串》与《字符类型》；《信息学奥信一本通（C++版）》字符串处理章节；noi.hnai.net 2025/2026 阅读程序中的 RLE 解码、2021 阅读第 22-27 题（Base64）为同类逐字符处理题。

2.11 函数：定义、调用、作用域与引用传参

是什么 / 为什么考：函数是代码复用与模块化的基本单位；CSP-J 阅读程序题里几乎每个程序都有函数，「值传递 vs 引用传递」更是 2025 单选第 10 题的直考考点。

详细原理：

• 函数由「返回类型 + 函数名 + 参数表 + 函数体」组成，先声明（或定义）后使用。
• C++ 默认按值传递：形参是实参的「复印件」，函数内修改形参不影响实参——所以按值传参的 swap 交换不了外部变量。
• 引用传递（int &x）时形参与实参共享同一块内存，函数内修改会「带出来」影响实参。
• 作用域：函数内定义的局部变量生命周期到函数返回为止；
• 全局变量全程存在；
• 同名时局部变量遮蔽（shadowing）全局变量。

考法总结：

• 真题 2025-10 直考「引用传递 vs 值传递」；
• 阅读程序常见：主函数调用函数后输出变量值——先分清每个参数是值还是引用。
• 看函数头参数里有没有 &，带 & 的修改会「带出来」。

易错点：

1. 值传递改不了实参；
2. 函数返回后局部变量销毁（不能返回局部数组/局部变量的地址）；
3. 未写 return 时返回值不确定；
4. 全局变量与局部变量同名时局部优先。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int f(int x) { x = x + 10; return x; }   // 值传递：修改形参不影响实参
int g(int &y) { y = y + 10; return y; }   // 引用传递：修改实参
int main() {
    int a = 1;
    cout << f(a) << ' ' << a << endl;     // 11 1（a 未被修改）
    cout << g(a) << ' ' << a << endl;     // 11 11（a 被修改）
    return 0;
}

延伸阅读与参考：OI Wiki《函数》讲参数传递、作用域与重载；《信息学奥信一本通（C++版）》第七章函数；noi.hnai.net 2023 单选第 3 题（结构体成员访问）、2024 阅读第 27-32 题（自定义函数递归）。

是什么 / 为什么考：引用是「别名」，2025 单选第 10 题直考「引用传递 vs 值传递」；引用也是写高效函数的基石（避免大对象拷贝）。

详细原理：

• int &r = a 之后，r 就是 a 的另一个名字：改 r 就是改 a。
• 引用必须初始化、且不能改绑。
• 函数参数用引用（void f(int &x)）时，形参与实参共享同一块内存，函数内修改会「带出来」影响实参；
• 用值传递则不影响。

考法总结：

• 2025-10 考「哪个函数能真正修改实参」（找参数带 & 的）；
• 阅读程序常考：函数内部修改参数后，主函数输出实参值——先看形参有没有 &。
• 常与指针传参对比考查。

易错点：

1. 引用必须初始化（int &r; 是错的）；
2. 引用不能改绑（int &r=a; r=b; 是把 b 赋给 a，不是让 r 绑到 b）；
3. 值传递修改不影响实参；
4. 返回局部变量的引用是悬空引用（局部变量已销毁）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
void change(int x, int y) { x = x + 10; y = y + 10; }  // 值传递
void swapRef(int &x, int &y) { int t = x; x = y; y = t; } // 引用传递
int main() {
    int a = 1, b = 2;
    change(a, b);
    cout << a << ' ' << b << endl;        // 1 2（未变）
    swapRef(a, b);
    cout << a << ' ' << b << endl;        // 2 1（已交换）
    int &r = a;                           // 引用必须初始化
    r = 100;
    cout << a << endl;                    // 100
    return 0;
}

延伸阅读与参考：OI Wiki《引用》讲引用作为别名与传参；《信息学奥信一本通（C++版）》函数章节；noi.hnai.net 2023 单选第 3 题（结构体传参与成员修改）考察引用/指针修改语义。

2.12 递归函数：终止条件、递推关系与复杂度优化

是什么 / 为什么考：递归是 CSP-J 算法题的重头戏，2025 单选第 3 题直接考「递归求值」，阅读/完善程序里也频繁出现。理解递归 = 理解「自己调用自己 + 何时停」。

详细原理：

• 递归三要素：① 递推关系——把大问题分解为规模更小的同型问题；
• ② 终止条件（base case）——不再调用、直接返回；
• ③ 收敛性——每次调用规模减小，最终到达 base case。
• 手推递归的可靠方法：从 base case 出发「列表往回代值」。
• 以 calc(n)=calc(n-1)+calc(n-2)+1（n≥3，calc(1)=1, calc(2)=2）为例：calc(3)=calc(2)+calc(1)+1=2+1+1=4；
• calc(4)=calc(3)+calc(2)+1=4+2+1=7；
• calc(5)=calc(4)+calc(3)+1=7+4+1=12——可见「列表往回代值」比盯着递归式空想要可靠得多。
• 递归调用过程可用「递归树」表示：每个结点是一次调用，叶子是 base case，答案由叶子向上汇总。

考法总结：

• 2025-3 考「给定函数求 calc(5)」——标准做法是从 calc(1)、calc(2) 开始逐个列表推；
• 完善程序常考补全递归分支或边界条件。
• 看到递归题先找 base case 和递推式，再列表推。

易错点：

1. 忘记/写错终止条件 → 无限递归栈溢出；
2. 边界条件差一（n<2 还是 n<=2）；
3. 双分支递归的调用次数按「树」计数，别只数一遍；
4. 返回值类型与中间结果溢出。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int calc(int n) {                         // calc(n) = calc(n-1)+calc(n-2)+1
    if (n <= 2) return n;                 // calc(1)=1? 见下
    return calc(n - 1) + calc(n - 2) + 1;
}
// 修正边界：令 calc(1)=1, calc(2)=2
// calc(3)=2+1+1=4, calc(4)=4+2+1=7, calc(5)=7+4+1=12
int main() {
    for (int i = 1; i <= 5; i++) cout << calc(i) << ' '; // 1 2 4 7 12
    cout << endl;
    return 0;
}

延伸阅读与参考：OI Wiki《递归》讲解分治式递归模板；《信息学奥信一本通（C++版）》第七章递归；noi.hnai.net 2020 单选第 6 题（递归求数组最大值）、2021 单选第 13 题（递归求值）、2024 完善第 38-42 题（汉诺塔）。

是什么 / 为什么考：朴素递归可能「指数爆炸」，这是性能分析考点，也引出记忆化/递推优化思想。CSP-J 阅读程序常问「调用了几次 / 复杂度是多少」。

详细原理：

• fib(n)=fib(n-1)+fib(n-2) 的朴素递归调用次数 T(n)=T(n-1)+T(n-2)+1，接近 2^n——fib(1)、fib(2) 被重复计算无数次。
• 例：递归求 fib(6) 的调用次数约 15 次（可画递归树数结点）。
• 改成循环递推：f[0]=f[1]=1，for i=3..n: f[i]=f[i-1]+f[i-2]，复杂度 O(n)，每个值只算一次。

考法总结：

• 阅读程序常考「该递归调用了几次 / 时间复杂度的量级」：有大量重复计算的递归是指数级，加记忆化或改递推是线性；
• 也考「fib(50) 用 int 存不存得下」（会溢出，需 long long/取模/高精度）。

易错点：

1. fib(1)=fib(2)=1（fib(0)=0 视定义）；
2. 递归版 fib(n) 的调用次数不是 n，是指数级；
3. 递归深度过大栈溢出；
4. 递推优化后仍要防 int 溢出（fib(47) 已超 int 范围）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
long long fibRec(int n) {                 // 朴素递归：调用次数指数级
    if (n <= 2) return 1;
    return fibRec(n - 1) + fibRec(n - 2);
}
long long fibLoop(int n) {                // 循环递推：O(n)
    long long a = 1, b = 1, c;
    if (n <= 2) return 1;
    for (int i = 3; i <= n; i++) { c = a + b; a = b; b = c; }
    return b;
}
int main() {
    cout << fibRec(6) << ' ' << fibLoop(6) << endl;   // 8 8
    cout << fibLoop(50) << endl;                       // 12586269025
    return 0;
}

延伸阅读与参考：OI Wiki《递归》与《动态规划基础》对比递归与递推复杂度；《信息学奥信一本通（C++版）》递归与递推章节；noi.hnai.net 2022 阅读第 22-27 题（递推求最值）考察递归转递推思想。

2.13 指针简单概念：取址、解引用与数组

是什么 / 为什么考：指针是 C++ 的「地址操作」，2026 单选第 11 题直考指针运算；指针与数组的关系是必考点。

详细原理：

• int *p = &a 让 p 存 a 的地址；
• *p 解引用得到 a 的值。
• 指针加减按「指向类型的大小」步进：int* p + 1 地址加 4 字节（跳过整个 int，不是 1 字节）。
• 数组名退化为指向首元素的指针：a[i] ≡ *(a+i)。

• 最终数组 {1,14,5,13,9}。

考法总结：

• 2026-11 考指针加减与下标混用：先画数组格子、标出 p 指向谁，再逐条语句执行。
• 阅读程序常考：指针偏移、*p++ 的先后、数组名不可赋值。

易错点：

1. 指针 +1 是跳一个元素（int 是 4 字节），不是 1 字节；
2. *p++ = 先取 *p 的值、再让 p 后移；
3. 数组名是常量指针，不能 a++ 或 a=p；
4. 空指针/野指针解引用会崩溃。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int arr[5] = {1, 3, 5, 7, 9};
    int *p = arr;                         // 数组名退化为指针
    cout << *p << ' ' << *(p + 2) << endl; // 1 5（p+2 跳 2 个 int）
    cout << arr[3] << ' ' << *(arr + 3) << endl; // 7 7 等价
    cout << sizeof(arr) << ' ' << sizeof(p) << endl; // 20 8（64 位系统）
    return 0;
}

延伸阅读与参考：OI Wiki《指针》讲取址、解引用、指针与数组关系；《信息学奥信一本通（C++版）》指针章节；noi.hnai.net 2022 单选第 3 题（指针赋值语义）、2019 阅读（二叉搜索树指针构建）涉及。

2.14 结构体 struct

是什么 / 为什么考：结构体（struct）把多个不同类型的变量打包成一个自定义类型，是组织复杂数据（学号+姓名+成绩、坐标 x+y 等）的基础，完善程序题常考。

详细原理：

• 定义：struct Student { int id; string name; double score; };——注意结尾分号不能丢；
• 使用：Student s; 用 . 访问成员（s.id = 1;），也可初始化 Student s = {1, "Tom", 95.5};；
• 结构体数组：Student a[100];，常配合 sort 按某成员排序（写比较函数 cmp）；
• 与 class 区别：struct 默认成员 public，class 默认 private（CSP-J 只考 struct 语法）。

考法总结：

1. struct 定义语法（结尾分号）；
2. 成员访问用 .（指针用 ->）；
3. 结构体数组按成员排序。

易错点：

1. 定义后忘打分号；
2. 成员名与类型名混淆；
3. 读入结构体数组元素时逐字段读，不能整体 cin。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
struct Student {
    int id;
    string name;
    int score;
};
bool cmp(const Student& a, const Student& b) {
    return a.score > b.score;   // 按成绩降序
}
int main() {
    Student a[3] = {{1, "Tom", 88}, {2, "Jerry", 95}, {3, "Bob", 78}};
    sort(a, a + 3, cmp);
    for (int i = 0; i < 3; i++)
        cout << a[i].name << ' ' << a[i].score << endl;
    // Jerry 95 / Tom 88 / Bob 78
    return 0;
}

延伸阅读与参考：OI Wiki《类》结构体部分；《信息学奥信一本通（C++版）》结构体章节；相关真题见下方真题总览。

模块三 · 数据结构基础

3.1 线性表与数组

是什么 / 为什么考：线性表是数据结构的入门概念：数据排成一条「线」，每个元素有前驱和后继。数组是线性表的顺序存储实现，CSP-J 常考「数组是连续内存」这一底层特性。

详细原理：

• 线性表：n 个元素的有限序列，有唯一的首元素和尾元素，除首尾外每个元素恰有一个前驱和一个后继；
• 顺序存储（数组）：元素存于连续内存，下标从 0 开始，a[i] 的地址 = 首地址 + i×sizeof(元素)，支持 O(1) 随机访问；
• 链式存储（链表）：元素间用指针相连，插入/删除 O(1) 但查找 O(n)（详见链表知识点）；
• 二维数组按「行优先」连续存储：b[i][j] 地址 = 首地址 + (i×列数+j)×sizeof(int)。

考法总结：

1. 数组与链表的访问/插入复杂度对比；
2. 下标计算（行优先 i*m+j）；
3. 线性表特性判断题（唯一前驱/后继）。

易错点：

1. 数组随机访问 O(1)，链表随机访问 O(n)；
2. 下标从 0 开始，int a[5] 合法下标 0~4；
3. 数组大小固定，插入/删除中间元素要移动 O(n)。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int a[5] = {10, 20, 30, 40, 50};
    // 随机访问 O(1)：直接按下标取
    cout << a[2] << endl;                       // 30
    // 数组地址连续：每个元素相隔 sizeof(int)=4 字节
    cout << (long long)(&a[1] - &a[0]) << endl; // 1（下标差 1）
    // 行优先：b[1][2] 是第 1*3+2 = 5 个元素（从 0 数）
    int b[2][3] = {{1,2,3},{4,5,6}};
    cout << b[1][2] << endl;                   // 6
    return 0;
}

延伸阅读与参考：OI Wiki《数组》与《数据结构》线性表；《信息学奥信一本通（C++版）》数据结构章节。

3.2 栈：后进先出（LIFO）

是什么 / 为什么考：栈是「后进先出」的容器，2026 单选第 4 题直考出栈序列合法性、2025 单选第 15 题考栈+队列手工模拟，是数据结构大题的常客。

详细原理：

• 栈只在一端（栈顶）操作：push 入栈、pop 出栈、top 看栈顶。
• 后进先出（LIFO）：最后进去的最先出来。
• 判断出栈序列是否合法用「模拟法」：按 1..n 依次尝试入栈，每入一个就尽量匹配出栈序列头部，能匹配就弹出；
• 若某时刻栈顶不匹配且元素已全部入过，则非法。

考法总结：

• 2026-4 考「哪个出栈序列不可能出现」（排除法：看小数字是否被压在大数字下面）；
• 2025-15 考栈+队列按规则模拟。
• 应用场景题：括号匹配、表达式求值、函数调用栈、浏览器后退。

易错点：

1. 弹栈前要判空；
2. 出栈序列合法性要「从头到尾模拟」，不能只看首尾；
3. 进栈过程允许随时出栈，不是全部入完才出；
4. 用 vector 模拟时栈顶是 back()。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <vector>
using namespace std;
bool validPop(const vector<int> &seq) {   // 判断出栈序列是否合法
    vector<int> st;
    int cur = 1;
    for (int x : seq) {
        while (cur <= (int)seq.size() && (st.empty() || st.back() != x))
            st.push_back(cur++);          // 持续入栈直到栈顶匹配
        if (st.empty() || st.back() != x) return false;
        st.pop_back();
    }
    return true;
}
int main() {
    cout << validPop({4, 3, 2, 1}) << endl; // 1 合法
    cout << validPop({3, 1, 4, 2}) << endl; // 0 非法
    cout << validPop({1, 2, 3, 4}) << endl; // 1 合法
    return 0;
}

延伸阅读与参考：OI Wiki《栈》讲单调栈与常见应用；《信息学奥信一本通（C++版）》数据结构章节；noi.hnai.net 2020 单选第 11 题（后进先出）、2021 单选第 5/9 题（出栈序列、中缀转后缀）、2024 单选第 13 题（入出栈序列）。

3.3 队列：先进先出（FIFO）

是什么 / 为什么考：队列是「先进先出」的容器，是 BFS 的载体（2026 单选第 8 题直考 BFS 队列模拟）；CSP-J 数据结构基础必考。

详细原理：

• 队尾入队（push）、队头出队（pop），先进先出（FIFO）。
• 数组模拟：int q[N], head=0, tail=0;；
• 入队 q[tail++]=x；
• 出队返回 q[head++]；
• 队空条件 head==tail；
• 循环队列判满（留一个空位）(tail+1)%N==head。

• BFS 中：起点入队，每次弹出队首 u，把 u 的未访问邻居入队并标记；
• 出队顺序即「按层展开」的顺序。

考法总结：

1. 2026-8 考 BFS 在网格上的出队顺序（判断谁先访问）；2025-15 考栈+队列混合模拟。常见角度：
2. 入队/出队顺序；
3. head/tail 下标变化；
4. 循环队列判空/判满。

易错点：

1. 队空 head==tail、循环队列队满 (tail+1)%N==head；
2. 出队只是 head 后移，数据还在数组里；
3. BFS 入队时必须马上标记已访问，否则会重复入队；
4. 数组队列容量有限，tail 会一直增大（大数组或循环队列）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
// 数组模拟队列：head 出队、tail 入队
int q[100005], head = 0, tail = 0;
void push(int x) { q[tail++] = x; }
int pop() { return q[head++]; }
int main() {
    push(1); push(2); push(3);
    cout << pop() << ' ' << pop() << endl; // 1 2（先进先出）
    cout << head << ' ' << tail << endl;   // 2 3
    return 0;
}

延伸阅读与参考：OI Wiki《队列》讲普通队列与优先队列应用；《信息学奥信一本通（C++版）》数据结构章节；noi.hnai.net 2022 单选第 5/10 题（栈队列混合、数据结构辨析）考察。

3.4 链表

是什么 / 为什么考：链表是「改指针」的数据结构，与数组形成对比；CSP-J 常考「哪种操作选数组/链表」及插入删除的指针操作顺序。

详细原理：

• 链表结点含数据域 + 指针域（指向下一个结点）。
• 插入结点到 cur 后面：先让新结点指向后继（newNode->next = cur->next），再让前驱指向新结点（cur->next = newNode）——顺序不能反，否则会「丢链」（先把 cur->next 改了，就找不到原后继了）。
• 删除结点：跳过它，让前驱直接指向后继（prev->next = del->next）。
• 复杂度对比：链表插入/删除 O(1)（已知位置）、随机访问 O(n)（要遍历）；
• 数组插入/删除 O(n)（要搬移）、随机访问 O(1)。

考法总结：

1. 常见角度：
2. 插入/删除的指针操作顺序判断；
3. 数组 vs 链表的复杂度对比；
4. 链表遍历输出。阅读/完善程序中的链表题要「画箭头」辅助，别纯脑内模拟。

易错点：

1. 插入时先连新结点再断旧链（顺序颠倒丢后继）；
2. 删除必须改前驱的 next；
3. 链表随机访问是 O(n) 不是 O(1)；
4. 遍历结束条件 p != nullptr（最后一个结点 next 为空）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
struct Node { int val; Node *next; };
int main() {
    Node n3 = {3, nullptr};
    Node n2 = {2, &n3};
    Node n1 = {1, &n2};                    // 1 -> 2 -> 3
    // 在头结点前插入 0（头插）
    Node n0 = {0, &n1};
    for (Node *p = &n0; p != nullptr; p = p->next)
        cout << p->val << ' ';             // 0 1 2 3
    cout << endl;
    // 删除 n1（跳过）：n0.next 直接指向 n2
    n0.next = n2.next;
    for (Node *p = &n0; p != nullptr; p = p->next)
        cout << p->val << ' ';             // 0 2 3
    cout << endl;
    return 0;
}

延伸阅读与参考：OI Wiki《链表》讲单向/双向链表与数组对比；《信息学奥信一本通（C++版）》数据结构章节；noi.hnai.net 2019 单选第 6 题（随机访问）、2020 单选第 7 题（随机访问）、2022 单选第 4/11 题（链表性质与插入）、2023 单选第 4 题（链表遍历）。

3.5 二叉树、完全二叉树与遍历

是什么 / 为什么考：二叉树是树结构的基础，完全二叉树性质与三种遍历是 CSP-J 高频考点（2025 单选第 14 题、2026 单选第 5 题直考叶子数）。

详细原理：

• 二叉树每个结点最多 2 个孩子（左、右）。
• 满二叉树：所有层都满；
• 完全二叉树：除最后一层外全满，且最后一层结点靠左连续排列。
• 完全二叉树性质（用数组 1-based 存储时）：结点 i 的孩子是 2i、2i+1，父是 i/2；
• n 个结点的完全二叉树叶子数 = ⌈n/2⌉（n=1000 → 500，2025-14；
• n=100 → 50，2026-5）；
• 深度 = ⌊log₂n⌋+1。
• 三种遍历：前序（根左右）、中序（左根右）、后序（左右根）。

考法总结：

• 2025-14/2026-5 考完全二叉树叶子数（套 ⌈n/2⌉）；
• 选择题常考「给定前序中序求后序」（先找根，再按中序分左右递归）。
• 阅读程序考递归遍历输出顺序。

易错点：

1. 叶子数公式 ⌈n/2⌉ 与 ⌊n/2⌋ 别混（奇数 n 时用向上取整）；
2. 前序第一个/后序最后一个一定是根；
3. 只有前序+后序不能唯一确定树；
4. 完全二叉树 ≠ 满二叉树。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
struct Node { int val; Node *left, *right; };
void pre(Node *r)  { if (!r) return; cout << r->val << ' '; pre(r->left);  pre(r->right); }
void in(Node *r)   { if (!r) return; in(r->left);  cout << r->val << ' '; in(r->right); }
void post(Node *r) { if (!r) return; post(r->left); post(r->right); cout << r->val << ' '; }
int main() {
    //     1
    //    / \
    //   2   3
    //  / \
    // 4   5
    Node n4 = {4, nullptr, nullptr}, n5 = {5, nullptr, nullptr};
    Node n2 = {2, &n4, &n5}, n3 = {3, nullptr, nullptr};
    Node n1 = {1, &n2, &n3};
    pre(&n1);  cout << endl;   // 1 2 4 5 3
    in(&n1);   cout << endl;   // 4 2 5 1 3
    post(&n1); cout << endl;   // 4 5 2 3 1
    // 完全二叉树 100 个结点：叶子数 = ceil(100/2) = 50
    cout << (100 + 1) / 2 << endl;         // 50
    return 0;
}

延伸阅读与参考：OI Wiki《树基础》讲遍历、完全二叉树与数组存储；《信息学奥信一本通（C++版）》树章节；noi.hnai.net 2019 单选第 8/14 题、2020 单选第 12 题、2021 单选第 8 题、2023 单选第 5/11 题、2024 单选第 12 题均为高频考点。

3.6 哈夫曼树

是什么 / 为什么考：哈夫曼树（最优二叉树）是贪心+树结合的经典应用，2025 单选第 4 题直考 WPL 计算，属于必考计算题。

详细原理：

• 构造法（贪心）：把 n 个权值看作 n 个叶子结点，每次选权值最小的两个合并成新结点（权值=两者之和），重复 n-1 次直到只剩一棵树。
• WPL（带权路径长度）= 所有叶子「权值×深度」之和 = 每次合并的权值之和（两种算法结果相同）。

• 哈夫曼树没有度为 1 的结点；
• 编码时左 0 右 1，权值大的离根近（编码短）。

考法总结：

1. 2025-4 直考 WPL=合并和；常见变体：
2. 给定权值求哈夫曼编码长度/编码方案；
3. 判断某编码集合是否为前缀码。做题技巧：每次挑最小两个合并并记下合并和，最后全加起来。

易错点：

1. 合并次数固定 n-1；
2. WPL 用「合并和」最快，用「权值×深度」要画对深度；
3. 相同权值时合并顺序可能不唯一，但 WPL 唯一；
4. 哈夫曼树没有度为 1 的结点。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    // 哈夫曼：权 {2,3,5,7}，每次合并最小两个
    priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
    pq.push(2); pq.push(3); pq.push(5); pq.push(7);
    int wpl = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        wpl += a + b;                      // WPL = 合并和
        pq.push(a + b);
    }
    cout << wpl << endl;                   // 5 + 10 + 17 = 32
    return 0;
}

延伸阅读与参考：OI Wiki《哈夫曼树》讲构造与 WPL 计算；《信息学奥信一本通（C++版）》树章节；noi.hnai.net 2021 单选第 11 题、2023 单选第 10 题直接考 WPL；2025 单选第 4 题亦考。

3.7 堆与优先队列

是什么 / 为什么考：堆是「能快速取最值」的完全二叉树，priority_queue 是 STL 现成堆；CSP-J 阅读程序里常出现。

详细原理：

• 堆满足堆序：大根堆父≥子（堆顶最大），小根堆父≤子（堆顶最小）。
• 用数组存储（下标 1 开始），结点 i 的孩子是 2i、2i+1。
• 操作复杂度：插入/删除堆顶 O(log n)，建堆 O(n)，取堆顶 O(1)。
• C++ priority_queue<int> 默认大根堆（top 最大）；
• 小根堆写 priority_queue<int, vector<int>, greater<int>>。

• 用途：哈夫曼合并（每次取最小两个）、取前 k 大/小、堆排序。

考法总结：

1. 常见角度：
2. 判断 priority_queue 默认是大根堆还是小根堆；
3. 连续 pop 后的输出顺序；
4. 堆与排序结合（堆排序升序用大根堆）。完善程序考堆的 up/down 调整操作补全。

易错点：

1. priority_queue<int> 默认大根堆，top 是最大值；
2. 小根堆要写 greater<int> 或存负数；
3. 堆排序升序用大根堆（把最大换到末尾）；
4. 数组模拟堆时下标从 1 开始，2i/2i+1 别越界。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> mx;                // 默认大根堆
    priority_queue<int, vector<int>, greater<int>> mn; // 小根堆
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6})
        { mx.push(x); mn.push(x); }
    cout << mx.top() << ' ' << mn.top() << endl; // 9 1
    // 取最小的 k=3 个：连续 pop 小根堆
    for (int i = 0; i < 3; i++) { cout << mn.top() << ' '; mn.pop(); }
    cout << endl;                          // 1 1 2
    return 0;
}

延伸阅读与参考：OI Wiki《二叉堆》讲堆性质与优先队列；《信息学奥信一本通（C++版）》数据结构章节；noi.hnai.net 2022 单选第 9 题（有向连通图邻接矩阵）与堆排序结合记忆；真题中堆多与排序/贪心结合出现。

3.8 图：基本概念与度数

是什么 / 为什么考：图论基础概念必考，2025 单选第 5 题考有向图度数性质、2026 单选第 15 题考握手定理，属于「背结论 + 简单推演」题。

详细原理：

• 图 = 顶点集 + 边集。
• 无向边无方向；
• 有向边有方向（起点→终点）。
• 度数：无向图顶点度数 = 关联边数；
• 有向图分入度（指向它的边数）与出度（它指出的边数）。
• 握手定理：无向图所有顶点度数之和 = 2×边数（每条边贡献 2 个度）；
• 有向图 入度总和 = 出度总和 = 边数（每条边贡献 1 入 1 出）。

• 完全图：n 个顶点两两相连，边数 = n(n-1)/2。

考法总结：

1. 2025-5（有向图入度=出度=边数）、2026-15（握手定理求边数）都是直接套公式；常见角度：
2. 度数总和求边数；
3. 判断图类型；
4. 完全图边数。看到「度数」题先列总度，再除以 2（无向）。

易错点：

1. 有向图度数分入/出，不能合起来除 2；
2. 无向图度数和 = 2E，求 E 要除以 2；
3. 自环对度数贡献 2；
4. 完全图边数 n(n-1)/2，别写成 n²。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    // 无向图：4 顶点 5 条边（0-1,0-2,1-2,1-3,2-3）
    int deg[4] = {};
    deg[0]++; deg[1]++;                  // 边 0-1
    deg[0]++; deg[2]++;                  // 边 0-2
    deg[1]++; deg[2]++;                  // 边 1-2
    deg[1]++; deg[3]++;                  // 边 1-3
    deg[2]++; deg[3]++;                  // 边 2-3
    int sum = 0;
    for (int i = 0; i < 4; i++) { cout << "deg(" << i << ")=" << deg[i] << ' '; sum += deg[i]; }
    cout << endl << "sum=" << sum << " 2E=" << 2 * 5 << endl; // sum=10 2E=10（握手定理）
    return 0;
}

延伸阅读与参考：OI Wiki《图论》讲图定义、度数、连通性与邻接矩阵；《信息学奥信一本通（C++版）》图论章节；noi.hnai.net 2020 单选第 8 题（连通图最少边数）、2022 单选第 9 题（邻接矩阵）、2023 单选第 12 题（DAG）、2024 单选第 11 题（度数之和）高频。

3.9 哈希与集合 set

是什么 / 为什么考：哈希（散列）把「键」通过哈希函数映射到数组下标，实现平均 O(1) 的查找；set 是 C++ 的集合容器，自动去重且有序，是哈希/平衡树思想的直接应用。

详细原理：

• 哈希思想：hash(key) = key % 容量 一类函数算出下标直接定位；冲突（不同键同下标）用链地址法（每个槽挂链表）或开放寻址法解决；
• set：元素唯一、自动升序；insert 插入、count(x) 判断是否存在（0/1）、size() 元素个数、erase 删除；底层常用红黑树，操作 O(log n)；
• 应用：去重（全塞进 set 后取 size）、快速判断元素是否存在、自动排序。

考法总结：

1. 哈希冲突的常见处理方式；
2. set 的 insert/count 用法与去重计数；
3. set 与 multiset（可重复）、unordered_set（哈希实现，无序）的区别。

易错点：

1. 不同键可能哈希冲突，不能保证一一对应；
2. set 自动去重排序，重复 insert 不增加元素；
3. count 只返回 0 或 1（存在性判断），不是出现次数。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <set>
using namespace std;
int main() {
    int a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    set<int> s;
    for (int i = 0; i < 10; i++) s.insert(a[i]);
    cout << s.size() << endl;                // 7 个不同数字
    cout << s.count(5) << ' ' << s.count(7) << endl;  // 1 0
    s.erase(5);
    cout << s.count(5) << endl;             // 0
    return 0;
}

延伸阅读与参考：OI Wiki《哈希表》与《STL 容器》set；《信息学奥信一本通（C++版）》STL 章节；相关真题见下方真题总览。

模块四 · 基础算法

4.1 暴力枚举

是什么 / 为什么考：枚举（暴力）是「最朴素也最可靠」的解法，配合剪枝可救性能；2026 单选第 10 题考「枚举/完全背包思想凑硬币」。

详细原理：

• 枚举 = 遍历所有候选答案逐一检验。
• 先估算复杂度：候选数 × 每次检验成本，超过限制（如 10⁸ 量级）就要剪枝或换算法。
• 经典：判素数（枚举 2..√n）、双循环两两组合（O(n²)）、枚举子集（2ⁿ）。
• 剪枝：在循环/递归中跳过「不可能产生答案/更优解」的分支。

考法总结：

1. 2026-10 考硬币组合最少枚数（枚举+最优性）；常见角度：
2. 暴力枚举的复杂度估算；
3. 剪枝条件；
4. 枚举范围边界。完善程序常考「枚举范围」（如 i*i<=n）。

易错点：

1. 不估算复杂度直接暴力会超时；
2. 枚举边界（<=n 还是 <n）写错；
3. 剪枝要剪「不可能更优」的分支，剪错会漏解；
4. 枚举子集是 2ⁿ，别当成 n²。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}
int main() {
    int cnt = 0;
    for (int x = 1; x <= 100; x++)
        if (isPrime(x)) cnt++;
    cout << cnt << endl;                 // 100 以内素数 25 个
    // 枚举 + 剪枝：找到第一个 x^2 > 1000 的 x 即停
    for (int x = 1; x <= 50; x++) {
        if (x * x > 1000) { cout << x << endl; break; } // 32
    }
    return 0;
}

延伸阅读与参考：OI Wiki《搜索》与《算法基础》讲枚举优化与剪枝；《信息学奥信一本通（C++版）》枚举章节；noi.hnai.net 2019 单选第 12/13 题（抽屉、计数枚举）、2020 单选第 14 题（隔板法）体现计数枚举思路。

4.2 模拟

是什么 / 为什么考：模拟题不考复杂算法，只考「照题意一步步实现」——阅读/完善程序中的模拟题最常见，要求细心处理循环与边界。

详细原理：

• 模拟三步：读懂规则 → 设计状态变量 → 用循环/分支逐帧推进；
• 常见模拟：报数/约瑟夫问题、日期与星期推进、网格坐标移动（上下左右）、按规则统计；
• 关键：把题目条件翻译成 if/循环，注意 1-based 与 0-based 换算、取模循环。

考法总结：

1. 报数/约瑟夫问题出列顺序；
2. 日期与星期计算（闰年判断）；
3. 网格/坐标移动后的位置。

易错点：

1. 循环边界与取模（n 个人下标 0..n-1）；
2. 状态变量未在每轮重置；
3. 题目条件漏读（如「包含两端」「遇到边界转向」）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    // 约瑟夫问题：n=7 人围圈，从 1 报数，报到 3 出列，模拟出列前 3 人
    int n = 7, m = 3;
    int a[7] = {1, 2, 3, 4, 5, 6, 7};
    int idx = 0, cnt = 0, out = 0;
    while (out < 3) {
        if (a[idx] != 0) {
            cnt++;
            if (cnt == m) {
                cout << a[idx] << ' ';   // 3 6 2
                a[idx] = 0;
                cnt = 0;
                out++;
            }
        }
        idx = (idx + 1) % n;          // 围圈取模
    }
    cout << endl;
    return 0;
}

延伸阅读与参考：OI Wiki《模拟》与《枚举》；《信息学奥信一本通（C++版）》算法基础章节；相关真题见下方真题总览。

4.3 冒泡、选择、插入排序

是什么 / 为什么考：三种 O(n²) 基础排序是 CSP-J 必考概念，2025 单选第 12 题直考「冒泡排序交换次数=逆序对」，几乎每年都有排序题。

详细原理：

• 冒泡排序：相邻两两比较，逆序就交换，每趟把当前最大值「冒」到末尾；
• 共 n-1 趟，第 i 趟比较 n-1-i 次；
• 总交换次数 = 数组中逆序对数量。

• 最好情况（已有序）一趟检测无交换即可提前结束 → O(n)。
• 选择排序：每趟选剩余最小值与当前位置交换，交换最多 n-1 次、比较次数固定 n(n-1)/2 → O(n²)。
• 插入排序：把新元素插入已排序前缀的合适位置，接近有序时接近 O(n)。
• 稳定性：冒泡、插入稳定（相等元素相对顺序不变），选择不稳定。

考法总结：

1. 2025-12 考冒泡交换次数（=逆序对数）；常见角度：
2. 某排序算法的过程/趟数；
3. 稳定性判断；
4. 比较次数/交换次数。做排序题先明确「哪个算法」再数「交换/比较」。

易错点：

1. 冒泡趟数 n-1、内层比较次数递减；
2. 选择排序交换少（≤n-1）但比较不少；
3. 稳定排序：相等元素相对顺序不变；
4. 冒泡交换次数 = 逆序对总数。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int a[5] = {5, 2, 8, 1, 6};
    // 冒泡排序（升序），统计交换次数 = 逆序对
    int swapCnt = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4 - i; j++)
            if (a[j] > a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapCnt++; }
    for (int x : a) cout << x << ' ';    // 1 2 5 6 8
    cout << endl << "swaps=" << swapCnt << endl; // 逆序对 = 6
    return 0;
}

延伸阅读与参考：OI Wiki《算法基础》冒泡/选择/插入排序页；《信息学奥信一本通（C++版）》排序章节；noi.hnai.net 2020 单选第 5 题（冒泡比较次数）、2022 单选第 12 题（排序稳定性）、2019 完善第 39-43 题（双关键字计数排序）。

4.4 归并排序与逆序对

是什么 / 为什么考：归并排序是「分治排序」代表，O(n log n) 稳定排序，还能顺带数逆序对；CSP-J 阅读/完善程序常考。

详细原理：

• 分治三步：① 分解：把序列从中间对半拆；
• ② 解决：递归排序两半；
• ③ 合并：双指针把两个有序段合并成一个有序段（谁小谁先取，用临时数组）。
• 复杂度稳定 O(n log n)，稳定排序。
• 数逆序对：合并时取右段元素 a[j] 时，左段剩余元素 a[i..m] 都比它大，逆序对数 += (m-i+1)。

考法总结：

1. 常见角度：
2. 归并过程/临时数组的使用；
3. 逆序对计数语句位置（取右段时累加）；
4. 复杂度 O(n log n)。完善程序常让补全合并循环或逆序对累加行。做逆序对题记住：只有「右段先出」才产生逆序对。

易错点：

1. 合并后必须把临时数组复制回原数组；
2. 逆序对累加在取右段时 += 左段剩余个数；
3. 递归边界 l>=r；
4. 逆序对总数可能超 int，用 long long。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <vector>
using namespace std;
long long inv = 0;
vector<int> tmp;
void mergeSort(vector<int> &a, int l, int r) {
    if (l >= r) return;
    int m = (l + r) / 2;
    mergeSort(a, l, m);
    mergeSort(a, m + 1, r);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else { inv += (m - i + 1); tmp[k++] = a[j++]; } // 逆序对计数
    }
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int t = l; t <= r; t++) a[t] = tmp[t];
}
int main() {
    vector<int> a = {5, 2, 8, 1, 6};
    tmp.resize(a.size());
    mergeSort(a, 0, (int)a.size() - 1);
    for (int x : a) cout << x << ' ';    // 1 2 5 6 8
    cout << endl << "inv=" << inv << endl; // 逆序对 = 6
    return 0;
}

延伸阅读与参考：OI Wiki《归并排序》含逆序对统计方法；《信息学奥信一本通（C++版）》排序章节；noi.hnai.net 历年完善程序常考归并合并过程，逆序对题见洛谷 P1908 类型训练题。

4.5 快速排序与 sort 函数

是什么 / 为什么考：快排是平均 O(n log n) 的排序，二分查找是「有序数组找值」的最优方法（2026 单选第 12 题直考比较次数），都是算法基石。

详细原理：

• 快速排序：选基准 pivot，一趟划分把 <pivot 放左、>pivot 放右，再递归排序两边。
• 平均 O(n log n)，最坏 O(n²)（如已有序且每次选端点做基准，可用随机/三数取中优化）。

1. 快排划分过程/基准选择；

1. 快排最坏 O(n²)（有序数据 + 端点基准）；

延伸阅读与参考：OI Wiki《快速排序》与《二分》；《信息学奥信一本通（C++版）》查找章节；noi.hnai.net 2019 单选第 5 题（折半查找次数）、2024 单选第 9 题（二分最多比较）、2022 阅读第 28-34 题（二分求平方根）、2023 完善第 33-37 题（二分缺失数）。

4.6 顺序查找与二分查找边界

• 二分查找：要求数组有序，每次与中点 mid=(l+r)/2 比较，相等返回；
• 小则 r=mid-1，大则 l=mid+1。
• 最坏比较次数 = ⌊log₂n⌋+1。

• 找不到时 l 落在「插入位置」。
• 二分变体：lower_bound 找第一个 ≥x 的位置。

考法总结：

1. 2026-12 考二分最坏比较次数（用 log₂ 估算 +1）；常见角度：
2. 二分边界更新（l=mid+1 vs r=mid-1）；
3. lower_bound/upper_bound 语义。做二分题先确定闭区间 [l,r] 写法再推演。

易错点：

1. 二分 mid 用 l+(r-l)/2 防溢出；
2. l<=r 与 l<r 两套写法的边界更新不同；
3. 二分前提是数组有序。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int bsearch(int a[], int n, int key) {   // 在有序数组 a[0..n-1] 中二分
    int l = 0, r = n - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;         // 防溢出写法
        if (a[m] == key) return m;
        if (a[m] < key) l = m + 1;
        else r = m - 1;
    }
    return -1;
}
int main() {
    int a[10] = {1, 3, 5, 7, 9, 11, 15, 18, 22, 30};
    cout << bsearch(a, 10, 15) << endl;  // 6
    cout << bsearch(a, 10, 4) << endl;   // -1
    return 0;
}

4.7 递归与分治

是什么 / 为什么考：分治「分解-解决-合并」三步走，归并/快排/二分/快速幂都是它的应用；CSP-J 阅读程序常考快速幂等。

详细原理：

• 分治三步骤：① 分解：把原问题拆成规模更小、结构相同的子问题；
• ② 解决：递归求解子问题（最小规模直接解）；
• ③ 合并：把子问题解合成原问题解。
• 快速幂：a^b 按二进制位处理——while(b){ if(b&1) r=r*a; a=a*a; b>>=1; }，复杂度 O(log b)。

考法总结：

1. 常见角度：
2. 快速幂代码推演/取模；
3. 归并/快排的分治结构；
4. 二分作为分治。完善程序常让补「合并」或「递归调用」语句。看到「折半/递归」先想分治。

易错点：

1. 子问题必须与原问题同型；
2. 合并步骤的复杂度决定整体（归并合并 O(n)）；
3. 快速幂取模时先 a%m，乘法注意溢出（用 long long）；
4. 分治边界（l>r / l>=r）写对。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
long long powmod(long long a, long long b, long long m) { // 快速幂分治
    long long r = 1 % m;
    a %= m;
    while (b > 0) {
        if (b & 1) r = r * a % m;        // 当前位为 1 则乘上
        a = a * a % m;
        b >>= 1;
    }
    return r;
}
int main() {
    cout << powmod(2, 10, 1000) << endl; // 1024 % 1000 = 24
    cout << powmod(3, 5, 100) << endl;   // 243 % 100 = 43
    return 0;
}

延伸阅读与参考：OI Wiki《分治》讲二分/归并/快速排序统一框架；《信息学奥信一本通（C++版）》分治章节；noi.hnai.net 2022 阅读第 28-34 题（平方根）、2023 完善第 33-37 题（缺失数）都是分治应用题。

4.8 贪心算法与中位数距离最小化

是什么 / 为什么考：贪心「每步选当前最优」期望全局最优，2025 完善程序第 22~25 题考「排序去重后的分段贪心」、2025 阅读程序第 39~42 题考多数派候选消除，是 CSP-J 完善程序高频思想。

详细原理：

• 贪心的正确性需要证明（通常用交换论证/归纳）或至少验证反例。
• 经典应用：区间调度（按结束时间排序，每次选最早结束的）、哈夫曼（每次合并最小两个）、Boyer-Moore 多数元素投票（候选 + 计数：相同 +1、不同 -1、减到 0 换候选；
• 前提是存在出现次数 > n/2 的多数）。
• 推演多数元素：{1,2,1,1,3,1}——cand=1,cnt=1；
• 遇 2 不同 → cnt=0（换 cand=2,cnt=1）；
• 遇 1 不同 → cnt=0（换 cand=1,cnt=1）；
• 遇 1 相同 → cnt=2；
• 遇 3 不同 → cnt=1；
• 遇 1 相同 → cnt=2 → 最终候选 1，再验证确实 > n/2。

考法总结：

• 2025-22~25 考排序后按某种规则分段贪心；
• 2025-39~42 考多数派候选消除（用 query 投票，每次淘汰一对）。
• 做题：先猜贪心策略，再验证是否最优（找反例）；
• 笔试重点在「理解算法过程、推演结果」。

易错点：

1. 贪心不一定正确，要验证；
2. 多数元素前提是存在 > n/2 的多数；
3. 投票法返回候选后还要再验证；
4. 排序是很多贪心的前提（先排序再贪）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <vector>
using namespace std;
int majority(const vector<int> &a) {     // Boyer-Moore 多数元素投票
    int cand = a[0], cnt = 1;
    for (int i = 1; i < (int)a.size(); i++) {
        if (cnt == 0) { cand = a[i]; cnt = 1; }
        else if (a[i] == cand) cnt++;
        else cnt--;
    }
    return cand;
}
int main() {
    vector<int> a = {1, 2, 1, 1, 3, 1};  // 1 出现 4 次 > 6/2
    cout << majority(a) << endl;         // 1
    return 0;
}

延伸阅读与参考：OI Wiki《贪心》讲贪心正确性证明方法；《信息学奥信一本通（C++版）》贪心章节；noi.hnai.net 2019 单选第 11 题（能耗最优）、2020 完善第 39-43 题（最小区间覆盖）、2021 单选第 15 题（过河问题）、2023 单选第 6 题（空闲时间段）。

是什么 / 为什么考：「到各点距离和最小选中位数」是贪心/排序的经典结论，2026 单选第 14 题直考，常以「选址问题」出现。

详细原理：

• 数轴上有 n 个点，选位置 P 使 Σ|P-xᵢ| 最小：P 取排序后的中位数。
• 理由（配对法）：排序后把点首尾配对，任意两个配对点之间的任何位置到两点的距离和 = 两点间距（常数）；
• 为了让所有配对都被覆盖，P 落在「最中间配对区间」即可——即中位数。
• 奇数个点取正中那个；
• 偶数个取中间两个之间的任意值（含端点）。

考法总结：

• 2026-14 直考「取中位数求最小距离和」；
• 变体：求「距离和最小」用中位数，求「平方和最小」用平均数。
• 做题流程：先排序 → 取中位数 → 求和。

易错点：

1. 必须先排序再取中位数；
2. 偶数个点时中间两个之间的任意值都最优；
3. 中位数下标 (n-1)/2（0-based）；
4. 距离用 abs，别漏绝对值。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int pts[5] = {10, 2, 7, 4, 1};       // 数轴上 5 个点
    sort(pts, pts + 5);                  // 1 2 4 7 10
    int mid = pts[5 / 2];                // 中位数 4（0-based 下标 2）
    int sum = 0;
    for (int x : pts) sum += abs(x - mid);
    cout << mid << ' ' << sum << endl;   // 4 14（3+2+0+3+6）
    return 0;
}

延伸阅读与参考：OI Wiki《算法基础》与贪心页讲「绝对差最小化选中位数」结论；《信息学奥信一本通（C++版）》贪心章节；noi.hnai.net 2022 完善第 39-43 题（矩形覆盖二分）体现有序性利用；此类题常考「排序后取中位」。

4.9 递推

是什么 / 为什么考：递推「由初值按关系逐步推」，2026 单选第 7 题直考上楼梯，递推也是 DP 的基础形态。

详细原理：

• 递推 = 初值 + 递推关系 + 顺序计算（自底向上）。
• 上楼梯：每次可上 1/2/3 级，f(n)=f(n-1)+f(n-2)+f(n-3)，初值 f(0)=1（地面）、f(1)=1、f(2)=2。

• 斐波那契：f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。
• 递推 vs 递归：递推自底向上循环算（无重复计算），递归自顶向下调用（可能重复）。

考法总结：

1. 2026-7 直考「上楼梯 1/2/3 步走法数」（f(8)=81）；常见角度：
2. 给定递推关系求某一项；
3. 递推初值（f(0) 常为 1）；
4. 大数取模/高精度。做递推题：先定初值，再从小 n 逐个推，别跳步。

易错点：

1. 初值给错全盘皆错（f(0)=1 别漏）；
2. 递推式下标越界（f(n-3) 需 n≥3）；
3. 结果增长快（f(40) 已超 int），用 long long 或取模；
4. 与「排列组合」走法题区分（能否回头/多步组合）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int n = 10;
    long long f[11] = {0};
    f[0] = 1; f[1] = 1; f[2] = 2;        // 初值
    for (int i = 3; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2] + f[i - 3]; // 每次 1/2/3 步
    for (int i = 0; i <= 10; i++) cout << f[i] << ' ';
    cout << endl;                        // 1 1 2 4 7 13 24 44 81 149 274
    return 0;
}

延伸阅读与参考：OI Wiki《动态规划基础》从递推讲起；《信息学奥信一本通（C++版）》递推章节；noi.hnai.net 2022 阅读第 22-27 题（递推求最值）、2020 单选第 13 题（干支周期）体现递推与周期。

4.10 前缀和与差分

是什么 / 为什么考：前缀和/差分是「区间操作」的利器：前缀和 O(1) 查区间和、差分 O(1) 区间加，2026 单选第 13 题直考前缀和性质。

详细原理：

• 前缀和：s[i]=s[i-1]+a[i]（下标从 1 开始），区间 [l,r] 的和 = s[r]-s[l-1]（O(1)）。

• 差分：d[i]=a[i]-a[i-1]，区间 [l,r] 全部 +x → d[l]+=x, d[r+1]-=x；
• 最后对 d 求前缀和还原 a。
• 差分是前缀和的「逆运算」。

考法总结：

1. 2026-13 考「给前缀和求原值」（a[i]=s[i]-s[i-1]）；常见角度：
2. 区间和查询（s[r]-s[l-1]）；
3. 差分区间加后还原数组；
4. 二维前缀和。完善程序常考差分标记位置（d[l]+=x, d[r+1]-=x）。

易错点：

1. 前缀和数组下标从 1 开始，避免 s[-1]；
2. 差分还原 = 对差分数组求前缀和；
3. 差分区间 [l,r] 加 x 是 d[l]+=x 且 d[r+1]-=x（注意 r+1 越界处理）；
4. 别把 s[i]=s[i-1]+a[i] 写成 s[i]=s[i-1]+s[i]。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int a[6] = {0, 3, 1, 7, 2, 5};       // 1-based：a[1..5]
    int s[6] = {0};
    for (int i = 1; i <= 5; i++) s[i] = s[i - 1] + a[i];
    // 区间 [2,4] 和 = 1+7+2 = 10
    cout << s[4] - s[1] << endl;         // 10
    // 差分：区间 [2,4] 全部 +10
    int d[7] = {0};
    for (int i = 1; i <= 5; i++) d[i] = a[i] - a[i - 1];
    d[2] += 10; d[5] -= 10;
    for (int i = 1; i <= 5; i++) { d[i] += d[i - 1]; cout << d[i] << ' '; }
    cout << endl;                        // 3 11 17 12 5
    return 0;
}

延伸阅读与参考：OI Wiki《前缀和与差分》讲一维二维前缀和；《信息学奥信一本通（C++版）》算法章节；noi.hnai.net 2023 完善第 33-37 题（连续数组缺失数）、历年阅读程序常与二分结合。

4.11 简单动态规划：一维 DP、LCS/LIS

是什么 / 为什么考：DP = 状态 + 转移 + 边界，是 CSP-J 算法压轴思想；阅读/完善程序常出现一维 DP（爬楼梯、斐波那契、最大子段和）。

详细原理：

• 写 DP 四步：① 定义状态：dp[i] 表示什么（如「到第 i 级台阶的走法数」）；
• ② 写转移：dp[i] 由哪些更小的状态推出（dp[i]=dp[i-1]+dp[i-2]）；
• ③ 定边界：最小状态的值（dp[0]=1, dp[1]=1）；
• ④ 定填表顺序：保证转移用到的状态已算好（从小到大）。
• 推演爬楼梯（每次 1/2 步）：dp[2]=dp[1]+dp[0]=2，dp[3]=3，dp[4]=5，dp[10]=89（即斐波那契）。
• DP vs 递归：DP 自底向上填表天然无重复计算；
• 递归+记忆化等价。

考法总结：

1. 常见角度：
2. 一维 DP 推演（爬楼梯/斐波那契）；
3. 状态定义判断；
4. 边界初值；
5. 最大子段和（dp[i]=max(a[i], dp[i-1]+a[i])）。完善程序常让补转移方程。

易错点：

1. 状态定义不清转移必错；
2. 边界初值错全盘错；
3. 填表顺序要保证依赖已算；
4. 一维 DP 滚动数组更新顺序（倒序/正序）影响正确性。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int n = 10;
    long long dp[11] = {0};
    dp[0] = 1; dp[1] = 1;                // 边界
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];   // 转移：到第 i 级 = 前一级 + 前两级
    cout << dp[10] << endl;              // 89（斐波那契）
    return 0;
}

延伸阅读与参考：OI Wiki《动态规划基础》讲状态/转移/初始化三要素；《信息学奥信一本通（C++版）》动态规划章节；noi.hnai.net 2020 阅读第 28-33 题（区间合并最大代价）、2024 阅读第 21-26 题（打家劫舍）直接考察。

是什么 / 为什么考：LCS/LIS 是经典二维/一维 DP 模型，2025 完善程序第 28~31 题直考 LCS，属于必会模型。

详细原理：

• LCS：dp[i][j] = a 前 i 个与 b 前 j 个的最长公共子序列长度。
• 若 a[i]==b[j]：dp[i][j]=dp[i-1][j-1]+1；
• 否则 dp[i][j]=max(dp[i-1][j], dp[i][j-1])；
• 边界 dp[0][*]=dp[*][0]=0。

• LIS：dp[i] = 以 a[i] 结尾的最长上升子序列长度，dp[i]=max(dp[j])+1（j<i 且 a[j]<a[i]），初值 dp[i]=1，O(n²)。

考法总结：

1. 2025-28~31 考 LCS 的程序判断与输出（dp 表推演）；常见角度：
2. 填 dp 表求长度；
3. 转移条件（相等+1 / 取 max）；
4. LCS/LIS 概念区分。做 LCS 题：画表格逐格填。

易错点：

1. LCS 用 i-1/j-1 下标防越界；
2. LIS 的 dp[i] 至少为 1（自己一个）；
3. 子序列 ≠ 子串；
4. LCS 不要求字符唯一。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int lcs(const string &a, const string &b) { // 最长公共子序列
    int n = a.size(), m = b.size();
    int dp[20][20] = {};
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    return dp[n][m];
}
int main() {
    cout << lcs("ABCBDAB", "BDCAB") << endl; // 4（BCAB / BDAB）
    return 0;
}

延伸阅读与参考：OI Wiki《LCS》有完整推导与代码；《信息学奥信一本通（C++版）》动态规划章节；noi.hnai.net 2023 阅读第 21-26 题（LCS 长度）逐题考察边界条件，务必吃透二维 DP 表。

4.12 01 背包与可行性 DP

是什么 / 为什么考：01 背包是「选/不选」决策的经典 DP，2026 完善程序第 39~42 题考「平衡分割」（可行性 DP），是 CSP-J 完善程序压轴常见。

详细原理：

• 01 背包：n 个物品、容量 W，每个只能选/不选一次。
• dp[w] = 容量 w 的最大价值；
• 转移 dp[w]=max(dp[w], dp[w-wi]+vi)，枚举物品时容量必须倒序遍历——倒序时 dp[w-wi] 还是上一轮（未选当前物品）的值，保证每个物品只用一次；
• 若正序遍历则变成完全背包（可重复选）。
• 可行性 DP（平衡分割）：dp[s] = 能否凑出和 s（bool），转移 dp[s] |= dp[s-wi]，同样倒序。

考法总结：

1. 2026-39~42 考「分段平衡分割」（与平均值、可行性相关）；常见角度：
2. 01 背包一维倒序的原因判断；
3. 转移方程补全；
4. 可行性 DP 的 bool 转移。做背包题先确认「01/完全/多重」，01 必倒序。

易错点：

1. 01 背包一维必须倒序遍历容量；
2. 完全背包正序遍历（可重复选）；
3. 初始化：求最大价值用 -inf（dp[0]=0），求可行性用 false（dp[0]=true）；
4. 容量从 W 到 wi 递减，别越界。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int W = 5;
    int w[3] = {2, 3, 4}, v[3] = {3, 4, 5};
    int dp[6] = {};                      // dp[w]：容量 w 最大价值
    for (int i = 0; i < 3; i++)          // 枚举物品
        for (int c = W; c >= w[i]; c--)  // 01 背包：倒序！
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    cout << dp[W] << endl;               // 7（选物品 0+1：3+4）
    // 可行性 DP：能否凑出和 s（平衡分割）
    bool ok[10] = {}; ok[0] = true;
    for (int i = 0; i < 3; i++)
        for (int s = 9; s >= w[i]; s--)
            ok[s] = ok[s] || ok[s - w[i]];
    cout << ok[2] << ' ' << ok[3] << ' ' << ok[4] << ' ' << ok[5] << ' ' << ok[7] << endl;
    // 1 1 1 1 1（2,3,4 可凑出 2/3/4/5/7）
    return 0;
}

延伸阅读与参考：OI Wiki《背包》讲 01/完全/多重背包与滚动数组；《信息学奥信一本通（C++版）》背包章节；noi.hnai.net 2024 阅读第 21-26 题（打家劫舍）为「隔项 DP」变体，2025/2026 完善程序含可行性 DP。

4.13 深度优先搜索（DFS）

是什么 / 为什么考：DFS 是「一条路走到黑再回头」的搜索，2026 完善程序第 28~31 题考「右截断素数 DFS」，递归+搜索是 CSP-J 算法核心。

详细原理：

• DFS 用递归（或显式栈）：从当前状态出发，尝试所有可走分支，走到底（到达目标/无法前进）再回溯到上一个分支点尝试别的路。
• 关键配套：访问标记（vis）防重复 + 回溯恢复现场（撤销标记）。
• 经典应用：全排列（每层选一个未用数字）、子集、迷宫、连通块。

• 剪枝：在递归入口先判断不合法/不可能更优就 return，可大幅减少搜索量。

考法总结：

1. 2026-28~31 考 DFS 生成右截断素数（每次扩展一位并判素数）；常见角度：
2. 递归函数补全（边界、循环、回溯）；
3. 搜索顺序/输出顺序；
4. 访问标记与撤销的位置。完善程序常让补「回溯语句」（恢复标记）。

易错点：

1. 回溯必须撤销标记，否则漏分支；
2. 标记要在「进入/入队时」设置，防止同层重复使用；
3. 递归深度 = 状态层数，太大栈溢出；
4. 剪枝条件写错会剪掉正确解。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int n = 3, path[10];
bool used[10];
void dfs(int k) {                        // 已确定前 k 个位置
    if (k == n) {                        // 得到一个排列
        for (int i = 0; i < n; i++) cout << path[i];
        cout << ' ';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;           // 剪枝：跳过已用数字
        used[i] = true;
        path[k] = i;
        dfs(k + 1);
        used[i] = false;                 // 回溯：恢复现场
    }
}
int main() {
    dfs(0);
    cout << endl;                        // 123 132 213 231 312 321
    return 0;
}

延伸阅读与参考：OI Wiki《DFS》讲回溯与剪枝框架；《信息学奥信一本通（C++版）》搜索章节；noi.hnai.net 2021 单选第 14 题（DFS 遍历次序）、2024 完善第 38-42 题（汉诺塔递归）为 DFS 思想基础。

4.14 广度优先搜索（BFS）

是什么 / 为什么考：BFS 是「逐层扩散」的搜索，2026 单选第 8 题直考网格 BFS 出队顺序，也是无权图最短路的标准算法。

详细原理：

• BFS 用队列：起点入队并标记；
• 循环：弹出队首 u，把 u 的所有未访问邻居入队并标记。
• 由于逐层扩展，第一次访问某点的层数 = 起点到它的最短步数（无权图）。
• 出队顺序即「按层」顺序。

• 关键：入队时就标记（不是出队时），否则同一结点可能被多次入队。

考法总结：

1. 2026-8 考 BFS 访问/出队顺序判断；常见角度：
2. 给定图/网格写访问序列；
3. BFS 层数=最短路；
4. 队列实现细节（入队即标记）。做 BFS 题：手画队列，每步标「入队/出队」。

易错点：

1. 必须「入队时标记」，出队时标记会重复入队；
2. 输出顺序是出队顺序；
3. 网格 BFS 注意边界（不越界）和障碍；
4. BFS 保证无权图最短路，DFS 不保证。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    // 图：0-1, 0-2, 1-3, 2-3（无向）
    vector<int> g[4];
    g[0] = {1, 2}; g[1] = {0, 3}; g[2] = {0, 3}; g[3] = {1, 2};
    bool vis[4] = {};
    queue<int> q;
    q.push(0); vis[0] = true;            // 入队即标记
    while (!q.empty()) {
        int u = q.front(); q.pop();
        cout << u << ' ';                // 出队顺序
        for (int v : g[u])
            if (!vis[v]) { vis[v] = true; q.push(v); }
    }
    cout << endl;                        // 0 1 2 3
    return 0;
}

延伸阅读与参考：OI Wiki《BFS》讲队列实现与最短路性质；《信息学奥信一本通（C++版）》搜索章节；noi.hnai.net 2022 完善第 40-44 题（图像泛洪填充 BFS）直接考察。

模块五 · 复杂度与算法分析

5.1 时间复杂度

是什么 / 为什么考：时间复杂度描述算法运行时间随数据规模 n 的增长趋势，用大 O 记号表示，是 CSP-J 必考的复杂度分析基础。

详细原理：

• 大 O 只保留最高阶项、忽略常数与低阶项：O(1) 常数、O(n) 线性、O(n²) 平方、O(log n) 对数、O(n log n)（排序/分治典型）；
• 代码对应：单循环 O(n)；双层嵌套循环 O(n²)；每次规模减半（二分/倍增）O(log n)；分治合并线性 O(n log n)；
• 计算技巧：嵌套循环次数相乘；for(j=i+1;j<n;j++) 累加为 n(n-1)/2，仍是 O(n²)。

考法总结：

1. 给代码判断时间复杂度；
2. 给 n 估算大致运算次数；
3. 比较各复杂度增长快慢。

易错点：

1. 忽略常数与低阶项（3n+100 是 O(n) 不是 O(3n)）；
2. log 的底数不影响大 O（log₂n 与 log₁₀n 同阶）；
3. 嵌套循环别漏外层；循环变量跳变（i+=2）仍是 O(n/2)=O(n)。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int n = 100;
    long long cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) cnt++;  // n(n-1)/2 次
    cout << cnt << endl;                          // 4950，量级 O(n^2)
    int t = 0;
    for (int k = n; k > 1; k /= 2) t++;          // 约 log2(n) 次
    cout << t << endl;                          // 6（log2(100) 向下取整）
    return 0;
}

延伸阅读与参考：OI Wiki《复杂度》；《信息学奥信一本通（C++版）》算法基础章节；相关真题见下方真题总览。

5.2 空间复杂度

是什么 / 为什么考：空间复杂度描述算法运行所需额外内存随 n 的增长趋势，同样用大 O 表示；CSP-J 常考数组大小与递归栈深度。

详细原理：

• 空间 = 输入存储 + 辅助空间（额外数组、递归栈等），通常只计辅助空间；
• 一维数组 O(n)、二维数组 O(n²)、常数个变量 O(1)；递归深度为 d 时栈空间 O(d)；
• 内存估算：int 占 4 字节，1e6 个 int ≈ 4 MB；long long 8 字节，1e6 个 ≈ 8 MB。

考法总结：

1. 判断算法空间复杂度；
2. 估算数组占用内存（字节数 = 元素数 × sizeof）；
3. 递归深度是否计入空间。

易错点：

1. 不计输入数组本身，只算辅助空间；
2. 递归每层都要栈空间，深度 1e6 会爆栈；
3. 1e7 的 int 数组约 40 MB，可能超出常见内存限制（256 MB 一般安全，但别滥用）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n = 100;
    vector<int> a(n);        // 辅助空间 O(n)
    int b[10][10];           // 固定大小，与 n 无关 -> O(1)
    for (int i = 0; i < n; i++) a[i] = i * 2;
    cout << a[n - 1] << endl;                 // 198
    cout << (int)(sizeof(b) / sizeof(int)) << endl; // 100
    return 0;
}

延伸阅读与参考：OI Wiki《复杂度》（含空间复杂度）；《信息学奥信一本通（C++版）》算法基础章节；相关真题见下方真题总览。

5.3 最好、最坏、平均复杂度

是什么 / 为什么考：同一算法在不同输入下表现不同：最好、最坏、平均复杂度分别刻画最优、最差与期望情况，CSP-J 最爱考「快排最坏 O(n²)」这类结论。

详细原理：

• 最好：最理想输入下的复杂度；最坏：最差输入下的复杂度；平均：所有输入按概率加权的期望（一般按等概率）；
• 典型例子：快排平均 O(n log n)、最坏 O(n²)（已有序 + 每次选端点做基准）；插入排序最好 O(n)（已有序）、最坏 O(n²)；二分查找最好 O(1)（一次命中）、最坏 O(log n)；
• 竞赛中一般以「最坏情况」衡量算法是否可用，防止被特殊数据卡掉。

考法总结：

1. 给算法说出最好/最坏复杂度；
2. 判断什么输入会触发最坏情况（快排遇有序数据）；
3. 与排序稳定性、空间复杂度搭配考。

易错点：

1. 快排最坏是 O(n²)，不是 O(n log n)；
2. 平均复杂度不是「最好 + 最坏再除以 2」；
3. 别把最好情况当成常态（插入排序不是总 O(n)）。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a[5] = {5, 4, 3, 2, 1};   // 逆序：快排最坏场景
    int b[5] = {1, 2, 3, 4, 5};   // 已有序：插入排序最好场景
    sort(a, a + 5);
    sort(b, b + 5);               // std::sort 有优化，均 O(n log n)
    cout << a[0] << ' ' << a[4] << ' ' << b[4] << endl; // 1 5 5
    return 0;
}

延伸阅读与参考：OI Wiki《复杂度》讲最好/最坏/平均；《信息学奥信一本通（C++版）》排序章节；相关真题见下方真题总览。

5.4 常见排序算法复杂度对比

是什么 / 为什么考：冒泡/选择/插入/归并/快排/堆排序的「平均复杂度、最坏复杂度、空间、稳定性」是 CSP-J 高频表格考点，需要整体记忆对比。

详细原理：

考法总结：

1. 给排序名选复杂度/稳定性；
2. 「哪些排序最坏也是 O(n log n)」——归并、堆；
3. 稳定性对排序结果的影响（相同元素先后顺序）。

易错点：

1. 选择排序不稳定（会跨越交换）；
2. 快排最坏 O(n²) 不是 O(n log n)；
3. 归并空间 O(n)（合并需辅助数组），堆排空间 O(1)。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a[6] = {5, 2, 8, 1, 9, 3};
    // 用 std::sort（快排变体）排序：平均 O(n log n)
    sort(a, a + 6);
    for (int i = 0; i < 6; i++) cout << a[i] << ' ';
    cout << endl;   // 1 2 3 5 8 9
    // 模拟冒泡排序一趟：最大元素沉底
    int b[5] = {4, 3, 2, 1, 5};
    for (int i = 0; i < 4; i++)
        if (b[i] > b[i + 1]) swap(b[i], b[i + 1]);
    cout << b[4] << endl;   // 5
    return 0;
}

延伸阅读与参考：OI Wiki《排序简介》含复杂度对比表；《信息学奥信一本通（C++版）》排序章节；相关真题见下方真题总览。

模块六 · 离散数学与初赛数学

6.1 排列组合与加法乘法原理

是什么 / 为什么考：组合数是计数基础，2025 单选第 6 题考组合补集、2025 单选第 11 题考网格路径计数，每年数学题必有组合。

详细原理：

• C(n,k)=n!/(k!(n-k)!)，含义：n 个里选 k 个（顺序无关）。
• 性质：C(n,k)=C(n,n-k)（对称）；
• C(n,k)=C(n-1,k-1)+C(n-1,k)（杨辉三角递推，按「选/不选第 n 个」分类）。
• 网格路径：从 (0,0) 到 (m,n) 只向右/向下走，共 C(m+n, m) 种（共走 m+n 步，其中选 m 步向右）。

考法总结：

1. 2025-6（补集）、2025-11（路径计数 C(m+n,m)）都是直考；常见角度：
2. 直接算 C(n,k)；
3. 补集思想（至少/都有）；
4. 网格路径。做计数题：先判断「顺序有无关系」（排列 vs 组合），再决定用哪个。

易错点：

1. C(n,k)=C(n,n-k)；
2. 递推边界 C(n,0)=C(n,n)=1；
3. 网格路径是组合（C(m+n,m)）不是排列；
4. 「至少一个」用补集：总 - 反面。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    int C[11][11] = {};
    for (int i = 0; i <= 10; i++) {
        C[i][0] = C[i][i] = 1;             // 边界
        for (int j = 1; j < i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // 杨辉三角递推
    }
    cout << C[5][2] << ' ' << C[10][3] << endl; // 10 120
    // 3x2 网格路径数 = C(3+2,3) = C(5,3) = 10
    cout << C[5][3] << endl;               // 10
    return 0;
}

延伸阅读与参考：OI Wiki《组合》讲组合数公式与递推；《信息学奥信一本通（C++版）》组合数学章节；noi.hnai.net 2019 单选第 7/12/13 题、2020 单选第 10/14/15 题、2021 单选第 10/12 题、2023 单选第 6/14 题、2024 单选第 3/14 题为组合计数高频区。

6.2 容斥原理

是什么 / 为什么考：容斥是「多条件计数」的去重工具，2026 单选第 6 题直考「3 或 5 的倍数累加」，CSP-J 数学必考。

详细原理：

• 两集合：|A∪B| = |A|+|B|-|A∩B|；
• 三集合：|A∪B∪C| = |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|。
• 口诀「加单减双加三重」：单集合加、两两交减、三重交加回。
• 应用：1..n 中 x 的倍数个数 = ⌊n/x⌋；
• A∩B 中的元素 = lcm(A,B) 的倍数。

考法总结：

1. 2026-6 直考容斥计数/累加；常见角度：
2. 求满足 A 或 B 的个数；
3. 容斥公式选择；
4. 交集 = lcm 的倍数。做容斥题：画韦恩图或列公式，先单后双减。

易错点：

1. 交集要减去（不是加上）；
2. 三集合的三重交集要加回；
3. A∩B 是 lcm 的倍数，不是乘积的倍数（gcd≠1 时两者不同）；
4. 倍数个数用整除 ⌊n/x⌋。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    // 1..60 中 2 或 3 的倍数个数
    int A = 60 / 2;                        // 30 个 2 的倍数
    int B = 60 / 3;                        // 20 个 3 的倍数
    int AB = 60 / 6;                       // 10 个 6(=lcm) 的倍数
    cout << A + B - AB << endl;            // 40（容斥）
    return 0;
}

延伸阅读与参考：OI Wiki《容斥原理》讲交集并集计数；《信息学奥信一本通（C++版）》组合数学章节；noi.hnai.net 2025/2026 单选中的「既…又…」计数题即容斥；历年「至少一个」类题可用补集转化。

6.3 质数、约数与 gcd/lcm

是什么 / 为什么考：素数是最基础数论概念，2026 完善程序第 28~31 题考「右截断素数 DFS」（判素 + 搜索结合），素数题年年有。

详细原理：

• 试除法：n 是素数当且仅当 2..√n 都不能整除它。
• 为什么到 √n：若 n=ab 且 a≤b，则必有 a≤√n，所以只需检查小因子。
• 实现写 i <= n/i（避免 i*i 溢出）。

• 筛法（埃氏）：从 2 开始把 2..n 的倍数逐个划掉，剩余即素数，复杂度 O(n log log n)。

考法总结：

1. 2026-28~31 考 DFS 生成「右截断素数」（每次乘 10 加一位再判素）；常见角度：
2. 试除法判素；
3. 100 以内素数个数；
4. 筛法思想。完善程序常考判素函数补全（边界 x<=1 返回 false）。

易错点：

1. 1 不是素数；
2. 判到 √n 即可（i<=n/i 防溢出）；
3. 2 是素数别漏；
4. 右截断素数题注意最高位/扩展位不能是 0。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++)       // i*i<=x 防溢出写法
        if (x % i == 0) return false;
    return true;
}
int main() {
    cout << isPrime(97) << ' ' << isPrime(91) << ' ' << isPrime(2) << ' ' << isPrime(1) << endl;
    // 1 0 1 0（97 素数；91=7x13 合数；2 素数；1 非素数）
    int cnt = 0;
    for (int i = 1; i <= 100; i++) if (isPrime(i)) cnt++;
    cout << cnt << endl;                   // 25
    return 0;
}

延伸阅读与参考：OI Wiki《素数》讲试除法、埃氏筛与线性筛；《信息学奥信一本通（C++版）》数论章节；noi.hnai.net 2019 单选第 9 题（最大素数）、2020 完善第 34-38 题（质因数分解）、2021 阅读第 28-33 题（线性筛）、2023 阅读第 27-32 题（约数和）、2024 阅读第 16-20 题（素数计数）为最密集考点。

是什么 / 为什么考：gcd 是数论地基，2025 阅读程序第 16~19 题考 gcd 程序、2026 单选第 9 题考 gcd 计数，属于必考。

详细原理：

• 辗转相除法（欧几里得）：gcd(a,b)=gcd(b,a%b)，直到余数为 0 时返回 a。
• 互质：gcd = 1。
• 计数套路：求满足 gcd(x,60)=6 的 x（1≤x≤100）个数——令 x=6k，则需 gcd(6k,60)=6×gcd(k,10)=6，即 gcd(k,10)=1，k 范围 1..⌊100/6⌋=16。

考法总结：

• 2025-16~19 考 gcd 程序行为（判断/输出）；
• 2026-9 考 gcd(x,60)=6 计数（先提公因子再互质计数）。
• 做 gcd 计数题：提取 gcd 后转化为「互质计数」，互质 = 不含公共质因子。

易错点：

1. gcd(x,60)=6 要求 6|x 且 gcd(x/6,10)=1；
2. 互质计数 = 剔除含公共质因子的数；
3. 枚举范围是 ⌊100/6⌋；
4. 辗转相除终止条件是 b==0 返回 a。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int gcd(int a, int b) {                    // 辗转相除
    while (b) { int t = a % b; a = b; b = t; }
    return a;
}
int main() {
    // 1..100 中 gcd(x,60)==6 的个数
    int cnt = 0;
    for (int x = 1; x <= 100; x++)
        if (gcd(x, 60) == 6) cnt++;
    cout << cnt << endl;                   // 6
    // 检验：x=6k 且 gcd(k,10)=1，k=1..16
    // 满足的 k：1,3,7,9,11,13 -> 6 个
    return 0;
}

延伸阅读与参考：OI Wiki《最大公约数》讲辗转相除法与扩展欧几里得；《信息学奥信一本通（C++版）》数论章节；noi.hnai.net 2019 单选第 10 题（辗转相除求 gcd）直接考察；gcd 与互质是分数化简、周期问题的基础。

6.4 模运算与同余

是什么 / 为什么考：取模运算与序列周期是 CSP-J 数学难点，2025 单选第 8 题直考「取模递推周期性」，属于「找规律」题。

详细原理：

• 模 m 运算：a mod m ∈ [0, m-1]。
• 性质：(a+b)%m = (a%m+b%m)%m；
• (a×b)%m = (a%m×b%m)%m。
• 周期性：递推序列取模后，每个状态是若干模值的组合、状态数有限，必然出现重复 → 从重复点起进入周期。

• 做法：先写出前 10~20 项找周期，再用 n 对周期取余定位。

考法总结：

1. 2025-8 直考「大下标取模序列求值」；常见角度：
2. 找周期（写出前若干项）；
3. 用 n % 周期 定位；
4. 取模性质计算。做周期题：先写项找周期，注意周期起点可能不在第 1 项。

易错点：

1. 周期要从序列开头找（可能有前置非周期段）；
2. 取模结果不为负（负数先 +m）；
3. 大指数用快速幂取模；
4. 别把「周期长度」与「周期内第几项」搞混。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    // 斐波那契取模 7：观察周期
    int a = 0, b = 1;
    cout << a << ' ' << b << ' ';
    for (int i = 2; i < 20; i++) {
        int c = (a + b) % 7;
        cout << c << ' ';
        a = b; b = c;
    }
    cout << endl;
    // 0 1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 ...
    // 第 17 项起重复 0 1，周期 = 16
    return 0;
}

延伸阅读与参考：OI Wiki《数论基础》讲同余与周期性；《信息学奥信一本通（C++版）》数论章节；noi.hnai.net 2020 单选第 13 题（干支纪年取余）是周期取模经典题；负整数取模、大数取模需记规则。

6.5 逻辑命题

是什么 / 为什么考：逻辑命题是离散数学基础：命题真假判断、联结词与真值表、逆否命题，CSP-J 结合布尔代数一起考。

详细原理：

• 命题：能判断真假的陈述句（「x>5」是谓词不是命题；「今天是周一」是命题）；
• 联结词：且 ∧、或 ∨、非 ¬、蕴含 →（p→q 只有 p 真 q 假时为假）、等价 ↔（同真同假为真）；
• 逆否命题与原命题等价：原命题 p→q，逆否命题 ¬q→¬p；逆命题 q→p、否命题 ¬p→¬q 不一定等价；
• 优先级：¬ 高于 ∧ 高于 ∨；p→q 等价于 ¬p∨q。

考法总结：

1. 判断句子是否为命题；
2. 蕴含式真假判断（真值表）；
3. 逆否命题等价、布尔表达式化简。

易错点：

1. p→q 在 p 为假时恒为真；
2. 逆命题/否命题与原命题不等价，只有逆否等价；
3. ¬、∧、∨ 优先级别搞混。

示例（C++17 可编译运行，输出与讲解呼应）：

#include <iostream>
using namespace std;
int main() {
    bool p = true, q = false;
    cout << (p && q) << (p || q) << (!p) << endl;   // 0 1 0
    // p->q 等价于 !p||q：p 真 q 假时为假
    cout << (!p || q) << endl;                       // 0
    // 真值表输出 p->q
    for (int a = 0; a <= 1; a++)
        for (int b = 0; b <= 1; b++)
            cout << a << b << ':' << (!a || b) << ' ';
    cout << endl;   // 00:1 01:1 10:0 11:1
    return 0;
}

延伸阅读与参考：OI Wiki《位运算》与《组合数学》逻辑基础；《信息学奥信一本通（C++版）》数学基础章节；相关真题见下方真题总览。

模块十二 · CSP-J 第一轮真题总览（2019 - 2026，共 343 题） 真题

以下为 2025 与 2026 年 CSP-J1 真题完整集合：单选（15 题/年）、阅读程序（18 题/年）、完善程序（10 题/年），每题包含题目、选项、参考答案、解析与考点标签；阅读/完善程序题答案统一列于每套程序之后。可用上方筛选器切换年份。