# CSP-J 第一轮（初赛）6天系统冲刺讲义

---

## DAY1：计算机基础、进制转换与编码

### 一、 核心知识点

#### 1. 计算机硬件基本构成
*   **五大部件**：运算器、控制器、存储器、输入设备、输出设备。
*   **CPU（中央处理器）**：由**运算器**和**控制器**组成。
*   **存储器**：
    *   **内存（RAM）**：随机存取存储器，读写速度快，**断电后数据丢失**。
    *   **外存（硬盘、U盘等）**：读写速度相对慢，断电后数据不丢失。

#### 2. 操作系统与网络基础
*   **操作系统（OS）**：系统软件，是用户和计算机硬件之间的接口（如 Windows, Linux, macOS）。
*   **计算机网络分类**：按覆盖范围分为**局域网（LAN）**、**城域网（MAN）**、**广域网（WAN）**。
*   **IP 地址与域名**：
    *   IPv4 地址由 **32 位**二进制数（4个字节）组成，常用点分十进制表示（如 `192.168.1.1`），每段范围为 `0~255`。
    *   **DNS（域名系统）**：负责将人类易读的域名（如 `www.noi.cn`）解析为计算机识别的 IP 地址。
*   **常见网络协议**：HTTP（80端口）、HTTPS（443端口）、FTP（21端口）、TCP/IP。

#### 3. 进制转换与存储单位
*   **进制标识**：C++ 中，八进制以 `0` 开头，十六进制以 `0x` 开头，二进制以 `0b` 开头。
*   **转换方法**：
    *   **R进制转十进制**：按权展开法。
    *   **十进制转R进制**：除 R 取余，逆序排列。
    *   **二、八、十六进制互转**：3位二进制对应1位八进制；4位二进制对应1位十六进制。
*   **存储单位**：
    $$1 \text{ Byte} = 8 \text{ bits}$$
    $$1 \text{ KB} = 1024 \text{ B}, \quad 1 \text{ MB} = 1024 \text{ KB}, \quad 1 \text{ GB} = 1024 \text{ MB}, \quad 1 \text{ TB} = 1024 \text{ GB}$$

#### 4. 原码、反码与补码
*   计算机内部一律采用**补码**存储整数。
*   **正数**：原码 = 反码 = 补码。
*   **负数**：
    *   原码：最高位为符号位（1表示负数），其余为数值位。
    *   反码：符号位不变，数值位按位取反。
    *   补码：反码 + 1。
*   **特值速记**：在 8 位有符号整型中，`-1` 的补码是 `11111111`（十六进制 `0xFF`）。

#### 5. 位运算与字符编码
*   **位运算符**：按位与 `&`、按位或 `|`、按位异或 `^`、按位取反 `~`、左移 `<<`、右移 `>>`。
*   **ASCII 码常用值**：
    *   `'\0'` $\to$ 0
    *   空格 `' '` $\to$ 32
    *   `'0'` $\to$ 48
    *   `'A'` $\to$ 65
    *   `'a'` $\to$ 97
    *   大小写字符差值：`'a' - 'A' = 32`。

---

### 二、 经典例题

**【例题1】** 计算机在执行程序时，必须将对应的指令和数据先加载到（ ）中，CPU 才能进行访问。
A. 键盘  
B. 寄存器  
C. 内存  
D. 硬盘

> **【解析】** C。外存（硬盘）中的程序和数据必须调入内存（RAM）后，才能被 CPU 读取并执行。寄存器属于 CPU 内部的高速暂存器，不是批量加载程序的地方。

**【例题2】** 将十进制数 $85.625$ 翻译为二进制数是（ ）。
A. $1010101.101$  
B. $1010101.011$  
C. $1011101.101$  
D. $1011101.11$

> **【解析】** A。
> 1. 整数部分：$85 = 64 + 16 + 4 + 1 = 2^6 + 2^4 + 2^2 + 2^0 \to (1010101)_2$。
> 2. 小数部分：乘2取整法。
>    $0.625 \times 2 = 1.25$（取整1）
>    $0.25 \times 2 = 0.5$（取整0）
>    $0.5 \times 2 = 1.0$（取整1，结束）
>    所以小数部分为 $(.101)_2$。合并后为 $1010101.101$。

---

### 三、 巩固练习

1. 一个 32 位有符号整数，在计算机中以补码形式表示为 `0xFFFFFFFA`，则它对应的十进制值是（ ）。
   A. $-5$ &emsp; B. $-6$ &emsp; C. $-10$ &emsp; D. $-7$

2. 设变量 $a = 5$，二进制表示为 8 位。执行表达式 `a = ~a;` 后，变量 $a$ 的十进制值是（ ）。
   A. $-5$ &emsp; B. $-6$ &emsp; C. $250$ &emsp; D. $5$

3. 假设某张高清照片的无损像素大小为 $2048 \times 1024$，每个像素使用 24 位真彩色（RGB，各占 8 位）表示。如果不进行任何压缩，保存该图片需要占用大约（ ）MB 的存储空间。
   A. $2$ &emsp; B. $6$ &emsp; C. $16$ &emsp; D. $48$

---

### 四、 答案与解析

1. **B**  
   十六进制 `0xFFFFFFFA` 最高位为 1（二进制 `1111...1010`），说明是一个负数补码。
   求原码方法（逆操作）：补码减 1 得到反码 `0xFFFFFFF9`，再按位取反（符号位不变）得到原码 `0x00000006`，结合符号位，对应十进制值为 $-6$。

2. **B**  
   在 C++ 中，`int` 类型的 `~` 是按位取反运算符。
   $5$ 的补码为 `00000101`。
   按位取反后变为 `11111010`。
   这是一个负数补码，将其转换为十进制：
   先减 1 得到反码 `11111001`，再取反（除符号位外）得到原码 `10000110`，其值为 $-6$。
   *(便捷公式：对整数 $x$ 取反的值为 $-(x+1)$)*。

3. **B**  
   总比特数 = $2048 \times 1024 \times 24 \text{ bits}$。
   转换为字节 = $\frac{2048 \times 1024 \times 24}{8} = 2048 \times 1024 \times 3 \text{ Bytes}$。
   转换为 KB = $\frac{2048 \times 1024 \times 3}{1024} = 2048 \times 3 = 6144 \text{ KB}$。
   转换为 MB = $\frac{6144}{1024} = 6 \text{ MB}$。

---

## DAY2：程序结构设计

### 一、 核心知识点

#### 1. C++ 基础要素
*   **标识符命名**：只能由字母、数字、下划线组成，**不能以数字开头**，且不能与关键字重名。区分大小写。
*   **基本数据类型占用空间（常见 32/64 位环境）**：
    *   `char` (1字节)
    *   `bool` (1字节)
    *   `int` (4字节，约 $\pm 2.1 \times 10^9$)
    *   `long long` (8字节，约 $\pm 9.2 \times 10^{18}$)
    *   `float` (4字节)
    *   `double` (8字节)

#### 2. 格式化输入输出
*   `scanf` / `printf` 比 `cin` / `cout` 具有更快的执行效率。
*   格式占位符：`%d` (int), `%lld` (long long), `%f` (float), `%lf` (double), `%c` (char)。
*   `printf("%.2lf", val)`：保留两位小数输出。

#### 3. 分支与循环结构
*   **条件选择**：`if-else` 链，以及 `switch-case`（`case` 后面必须为**整型或字符型常量**，注意 `break` 的穿透效应）。
*   **循环控制**：`for`、`while`、`do-while`（后者至少执行一次）。
*   **跳转语句**：`break`（终止并跳出当前循环），`continue`（跳过本轮循环余下语句，直接进入下一次循环判断/更新）。

#### 4. 结构化程序设计与流程图
*   **三大基本结构**：顺序结构、分支结构、循环结构。
*   **流程图符号**：
    *   **圆角矩形/椭圆**：起止框。
    *   **平行四边形**：输入/输出框。
    *   **矩形**：处理/执行框。
    *   **菱形**：判断/条件框（必有两个出口：Y/N）。

#### 5. 结构体（`struct`）
*   自定义数据类型，可打包多个不同类型的数据成员。
*   声明末尾**不能遗漏分号**。支持成员运算符 `.` 访问。

---

### 二、 经典例题

**【例题1】** 下列给出的 C++ 标识符中，合法的是（ ）。
A. `2_name`  
B. `_temp_val`  
C. `int`  
D. `a#b`

> **【解析】** B。A 选项以数字开头，不合法；C 选项 `int` 是保留关键字，不能作为标识符；D 选项包含非法字符 `#`。

**【例题2】** 阅读以下程序，写出其运行输出结果：
```cpp
#include <iostream>
using namespace std;
int main() {
    int sum = 0;
    for (int i = 1; i <= 10; i++) {
        if (i % 3 == 0) continue;
        if (i > 7) break;
        sum += i;
    }
    cout << sum << endl;
    return 0;
}
```

> **【解析】** 运行分析如下：
> *   $i=1$：不满足 `i%3==0` 和 `i>7`，`sum = 0 + 1 = 1`。
> *   $i=2$：不满足条件，`sum = 1 + 2 = 3`。
> *   $i=3$：满足 `i%3==0`，触发 `continue`，跳过后续，进入下一轮。
> *   $i=4$：不满足条件，`sum = 3 + 4 = 7`。
> *   $i=5$：不满足条件，`sum = 7 + 5 = 12`。
> *   $i=6$：满足 `i%3==0`，触发 `continue`。
> *   $i=7$：不满足条件，`sum = 12 + 7 = 19`。
> *   $i=8$：满足 `i>7`，触发 `break`，整个循环终止。
> 最终输出 `19`。

---

### 三、 巩固练习

1. 在流程图中，表示"对数据进行计算、赋值或执行具体操作"的图形是（ ）。
   A. 菱形 &emsp; B. 平行四边形 &emsp; C. 矩形 &emsp; D. 椭圆形

2. 下列关于 C++ 结构体（`struct`）的说法，错误的是（ ）。
   A. 结构体中各个成员的类型可以各不相同
   B. 结构体定义结束后必须以分号（`;`）结尾
   C. 定义结构体变量时，可以直接使用该结构体名作为类型名
   D. 结构体和联合体（`union`）完全相同，所有成员共用同一段物理内存

3. 阅读以下程序，写出运行输出结果：
```cpp
#include <iostream>
using namespace std;
int main() {
    int a = 2, b = 3;
    int ans = 0;
    switch (a + b) {
        case 4: ans += 1;
        case 5: ans += 2;
        case 6: ans += 3; break;
        default: ans += 4;
    }
    cout << ans << endl;
    return 0;
}
```

---

### 四、 答案与解析

1. **C**  
   矩形代表处理框，用来表示数据的计算、处理与赋值；菱形代表条件判断框；平行四边形代表输入/输出框；椭圆形/圆角矩形代表起止框。

2. **D**  
   结构体的每个成员在内存中拥有独立的存储空间；而联合体（`union`）的所有成员共享同一段内存空间，其大小由最大成员决定。两者并不等价。

3. **输出：`5`**  
   `a + b = 5`，程序跳转至 `case 5`。由于 `case 5` 后面没有写 `break`，程序会发生"穿透"，继续执行 `case 6`。
   执行 `case 5` 时，`ans += 2` $\to$ `ans` 变为 2。
   继续向下执行 `case 6`，`ans += 3` $\to$ `ans` 变为 5，随后遇到 `break`，跳出 `switch` 语句。最终输出 `5`。

---

## DAY3：数据结构

### 一、 核心知识点

#### 1. 线性结构
*   **一维与二维数组**：
    *   在内存中是**连续存放**的（二维数组按**行优先**顺序存放）。
    *   数组名代表首地址，下标从 `0` 开始。
*   **字符串**：
    *   **C风格字符数组**：以 `'\0'`（ASCII为0）为结束符。`strlen()` 测量不含 `'\0'` 的有效长度，而 `sizeof()` 统计分配的总空间（包含 `'\0'`）。
    *   **`std::string`**：提供 `size()`、`substr(pos, len)`、`find(str)` 等操作。
*   **栈（Stack）**：**后进先出（LIFO）**，仅在栈顶进行操作。
*   **队列（Queue）**：**先进先出（FIFO）**，队尾入队（`push`），队头出队（`pop`）。

#### 2. 二叉树的性质与遍历
*   **基本公式**：
    *   第 $i$ 层最多有 $2^{i-1}$ 个节点。
    *   深度为 $k$ 的二叉树最多有 $2^k - 1$ 个节点。
    *   **节点关系**：度为 0 的叶子节点数 $n_0$ 与度为 2 的分支节点数 $n_2$ 满足：
        $$n_0 = n_2 + 1$$
*   **遍历方式**：
    *   前序（先根）：`根 -> 左 -> 右`
    *   中序（中根）：`左 -> 根 -> 右`
    *   后序（后根）：`左 -> 右 -> 根`
    *   **规律**：中序序列配合前序（或后序）序列可唯一确定一棵二叉树。若仅知前序和后序，则无法唯一确定。

#### 3. 特殊树与图
*   **哈夫曼树（Huffman Tree）**：带权路径长度（WPL）最小的二叉树。每次合并权重最小的两个节点。生成的哈夫曼编码无前缀重合问题。
*   **二叉搜索树（BST）**：左子树上所有节点值均小于根节点，右子树上所有节点值均大于根节点。**中序遍历 BST 可以得到一个严格单调递增的序列**。
*   **图的表示**：
    *   **邻接矩阵**：`g[i][j]` 存储边权，适合稠密图，空间复杂度 $O(V^2)$。
    *   **邻接表**：链表数组，适合稀疏图，空间复杂度 $O(V + E)$。

---

### 二、 经典例题

**【例题1】** 某个表达式在栈中的操作顺序为：将元素 $a, b, c, d$ 依次入栈，期间伴随出栈操作。下列哪个序列不可能是该栈输出的序列？（ ）
A. $a, b, c, d$  
B. $d, c, b, a$  
C. $b, a, c, d$  
D. $d, a, b, c$

> **【解析】** D。由于栈是 LIFO（后进先出），若 $d$ 先出栈，说明 $a, b, c$ 都在栈中。此时栈内自底向上依次为 $[a, b, c]$，因此接下来的出栈顺序只能是 $c$，然后是 $b$，最后是 $a$。所以 $d$ 后面紧跟 $a$ 属于非法出栈序列。

**【例题2】** 已知某二叉树的前序遍历序列为 `ABDECF`，中序遍历序列为 `DBEACF`。求该二叉树的后序遍历序列。
```
        A
       / \
      B   C
     / \   \
    D   E   F
```

> **【解析】**
> 1. 根据前序 `ABDECF` 可知，根节点为 `A`。
> 2. 对照中序 `DBEACF`，以 `A` 为界限，左半部分 `DBE` 为左子树，右半部分 `CF` 为右子树。
> 3. 对左子树 `DBE` 递归分析：前序中 `B` 先出现，故 `B` 是左子树的根。中序中 `D` 在 `B` 左侧，`E` 在 `B` 右侧，所以 `D` 是 `B` 的左孩子，`E` 是 `B` 的右孩子。
> 4. 对右子树 `CF` 递归分析：前序中 `C` 先于 `F`，故 `C` 是右子树根。中序中 `C` 在 `F` 左侧，故 `F` 是 `C` 的右孩子。
> 5. 还原后进行后序遍历：`左 -> 右 -> 根` $\to$ `D -> E -> B -> F -> C -> A`。结果为 `DEBFCA`。

---

### 三、 巩固练习

1. 设一棵完全二叉树包含 $2026$ 个节点，则该树的叶子节点（度为0的节点）个数为（ ）。
   A. $1013$ &emsp; B. $1014$ &emsp; C. $1012$ &emsp; D. $1015$

2. 现有一组权值为 $\{2, 3, 5, 7, 8\}$ 的叶子节点，用它们构造一棵哈夫曼树，则该树的带权路径长度（WPL）为（ ）。
   A. $53$ &emsp; B. $55$ &emsp; C. $57$ &emsp; D. $59$

3. 字符数组 `char s[] = "Noi2026\0CSP";`，执行 `cout << strlen(s) << " " << sizeof(s);` 后的输出是（ ）。
   A. `7 12` &emsp; B. `7 11` &emsp; C. `11 12` &emsp; D. `7 8`

---

### 四、 答案与解析

1. **A**  
   设度为 0, 1, 2 的节点数分别为 $n_0, n_1, n_2$。
   有方程：$n_0 + n_1 + n_2 = 2026$。
   又因为 $n_0 = n_2 + 1$，代入消去 $n_2$ 得：
   $2n_0 - 1 + n_1 = 2026 \implies 2n_0 + n_1 = 2027$。
   由于该树是完全二叉树，其度为 1 的节点数 $n_1$ 只能是 $0$ 或 $1$。
   因为 $2n_0$ 必定为偶数，而 $2027$ 为奇数，故 $n_1$ 必须取 $1$。
   由此得：$2n_0 + 1 = 2027 \implies 2n_0 = 2026 \implies n_0 = 1013$。

2. **B**  
   按照哈夫曼树构造步骤（小根堆贪心合并）：
   *   初始集合：$\{2, 3, 5, 7, 8\}$
   *   第一轮：选择最小的 $2$ 和 $3$ 合并，生成新节点 $5$（其下挂 $2, 3$）。集合变为 $\{5, 5, 7, 8\}$。
   *   第二轮：合并最小的两个 $5$ 和 $5$，生成新节点 $10$（下挂两个 $5$，其中一个 $5$ 下挂 $2,3$）。集合变为 $\{7, 8, 10\}$。
   *   第三轮：合并最小的 $7$ 和 $8$，生成新节点 $15$。集合变为 $\{10, 15\}$。
   *   第四轮：合并 $10$ 和 $15$，生成根节点 $25$。
   *   **叶子节点对应的路径长度（深度）**：
       *   $7$ 和 $8$：路径长度为 2。
       *   $5$（非合并产生的那个原始叶子）：路径长度为 2。
       *   $2$ 和 $3$：路径长度为 3。
   *   **WPL 计算**：
       $$\text{WPL} = 7 \times 2 + 8 \times 2 + 5 \times 2 + 2 \times 3 + 3 \times 3 = 14 + 16 + 10 + 6 + 9 = 55$$

3. **A**  
   *   `strlen(s)` 遇到第一个空字符 `'\0'` 即停止统计。`"Noi2026"` 包含 7 个有效字符，因此长度为 `7`。
   *   `sizeof(s)` 用于度量编译器分配给该字符数组的总物理空间（包括显式写入的每一个字符和末尾隐含自动追加的一个 `'\0'`）。
   *   物理内容为：`'N', 'o', 'i', '2', '0', '2', '6', '\0', 'C', 'S', 'P', '\0'`，共 12 字节。因此输出 `7 12`。

---

## DAY4：算法入门与分析

### 一、 核心知识点

#### 1. 基础算法思想
*   **枚举法**：在确定的范围内，不重复、不遗漏地尝试每一种可能。关键在于**确定合理的范围**和**判定标准**。
*   **模拟法**：按照题目的业务逻辑、规则，使用代码复现。需要特别注意边界条件和状态更新。
*   **贪心算法**：在每一步决策中都采取**当前局部最优**的选择，以期获得全局最优解。贪心策略需要通过严格的数学证明或反证法来确认其正确性。
*   **二分查找**：在**有序序列**中通过每次折半区间来查找目标，查找的时间复杂度为 $O(\log n)$。
*   **前缀和**：
    *   构造：$S[i] = S[i-1] + A[i]$。
    *   应用：以 $O(1)$ 的时间复杂度快速计算区间和 $\sum_{i=L}^{R} A[i] = S[R] - S[L-1]$。

#### 2. 排序算法对比
*   **稳定性**：若相同数值在排序后保持原有的相对先后位置不变，则称该排序稳定。

| 排序名称 | 最好时间 | 最坏时间 | 平均时间 | 空间复杂度 | 稳定性 |
| :--- | :--- | :--- | :--- | :--- | :--- |
| **冒泡排序** | $O(n)$ 或 $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| **选择排序** | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | **不稳定** |
| **插入排序** | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| **计数排序** | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(k)$ | 稳定 |
| **快速排序** | $O(n \log n)$ | $O(n^2)$ | $O(n \log n)$ | $O(\log n)$ | **不稳定** |

#### 3. 渐进复杂度分析
*   常数级 $O(1) <$ 对数级 $O(\log n) <$ 线性级 $O(n) <$ 线性对数级 $O(n \log n) <$ 平方级 $O(n^2) <$ 指数级 $O(2^n)$。
*   **主定理思维简化**：在递推关系中，如果每次将规模缩小一半（如二分、归并），通常会产生带有 $\log n$ 的复杂度项。

---

### 二、 经典例题

**【例题1】** 依次对数据序列 $[12, 5, 8, 1, 9]$ 进行选择排序（升序），完成第一轮交换后的序列为（ ）。
A. $[5, 12, 8, 1, 9]$  
B. $[1, 5, 8, 12, 9]$  
C. $[1, 12, 8, 5, 9]$  
D. $[1, 5, 8, 9, 12]$

> **【解析】** B。
> 选择排序第一轮：从整段区间 $[12, 5, 8, 1, 9]$ 中搜索最小值。
> 扫描发现最小值为 `1`（下标 3）。
> 将最小值 `1` 与当前待排区间首元素 `12`（下标 0）进行对调。
> 交换后序列变为 $[1, 5, 8, 12, 9]$。选择 B。

**【例题2】** 计算下列程序段的时间复杂度：
```cpp
int count = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j += i) {
        count++;
    }
}
```

> **【解析】**
> 外层循环 $i$ 遍历 $1$ 到 $n$。
> 当外层变量为 $i$ 时，内层循环的步长为 $i$，内层执行次数约为 $\frac{n}{i}$。
> 总执行次数为：
> $$T(n) = \frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n} = n \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)$$
> 根据调和级数求和公式，$1 + \frac{1}{2} + \dots + \frac{1}{n} \approx \ln n$。
> 因此，该程序段的渐进时间复杂度为 $O(n \log n)$。

---

### 三、 巩固练习

1. 在一棵已经排好序（升序）的拥有 $1000$ 个元素的数组中进行二分查找（Binary Search），在最坏情况下，查找某元素或判定其不存在，最多需要进行（ ）次元素比较。
   A. $9$ &emsp; B. $10$ &emsp; C. $11$ &emsp; D. $500$

2. 设原序列中包含两个数值相同的元素 $A$ 和 $B$，且在排序前 $A$ 排在 $B$ 之前。若经过某种排序算法处理后，$B$ 可能会排到 $A$ 之前，则此排序算法被称为是不稳定的。下列四个排序算法中，**不稳定**的是（ ）。
   A. 冒泡排序 &emsp; B. 直接插入排序 &emsp; C. 简单选择排序 &emsp; D. 归并排序

3. 阅读以下程序，写出运行输出结果：
```cpp
#include <iostream>
using namespace std;
int main() {
    int n = 5;
    int a[6] = {0, 2, 4, 1, 5, 3}; // 下标从1开始
    int s[6] = {0};
    for (int i = 1; i <= n; i++) {
        s[i] = s[i-1] + a[i];
    }
    cout << s[4] - s[1] << " " << s[5] - s[2] << endl;
    return 0;
}
```

---

### 四、 答案与解析

1. **B**  
   二分查找在最坏情况下的比较次数为 $\lfloor \log_2 n \rfloor + 1$。
   代入 $n = 1000$：因为 $2^9 = 512 < 1000 < 1024 = 2^{10}$，所以 $\lfloor \log_2 1000 \rfloor = 9$。
   最坏比较次数为 $9 + 1 = 10$ 次。

2. **C**  
   冒泡排序、插入排序和归并排序均为稳定排序。选择排序通过在未排序部分中寻找极值并与首位进行长距离交换，这种操作极易打破相同元素的相对顺序（例如序列 $[5, 5, 2]$，扫描第一轮将最小的 $2$ 与第一个 $5$ 交换，导致两个 $5$ 的先后顺序发生颠倒）。

3. **输出：`10 9`**  
   程序通过循环计算出了前缀和数组 $s$：
   *   $s[0] = 0$
   *   $s[1] = 2$
   *   $s[2] = 2+4 = 6$
   *   $s[3] = 6+1 = 7$
   *   $s[4] = 7+5 = 12$
   *   $s[5] = 12+3 = 15$
   根据区间和公式：
   *   `s[4] - s[1]` = $12 - 2 = 10$（对应元素 $a[2]+a[3]+a[4] = 4+1+5 = 10$）。
   *   `s[5] - s[2]` = $15 - 6 = 9$（对应元素 $a[3]+a[4]+a[5] = 1+5+3 = 9$）。

---

## DAY5：信奥数学基础

### 一、 核心知识点

#### 1. 整除与素数筛
*   **素数（质数）**：大于 1 的自然数中，除 1 和本身外无其他因数。
*   **唯一分解定理**：任何大于 1 的整数 $N$ 均能唯一分解为若干质数的乘积：
    $$N = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$$
    其正因数的个数为 $(e_1 + 1)(e_2 + 1)\dots(e_k + 1)$。
*   **埃氏筛法**：从 2 开始，若当前数未被标记，则其为质数，并将其所有倍数（如 $2i, 3i, \dots$）标记为合数。时间复杂度 $O(n \log \log n)$。

#### 2. 最大公约数（GCD）与最小公倍数（LCM）
*   **欧几里得算法（辗转相除法）**：
    $$\gcd(a, b) = \gcd(b, a \bmod b)$$
    在 C++ 中可以利用递归一行实现。
*   **基本性质**：
    $$\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$$

#### 3. 集合运算与容斥原理
*   **子集数**：大小为 $n$ 的集合，其子集总数为 $2^n$ 个，真子集总数为 $2^n - 1$ 个。
*   **并集与交集**：符号分别为 $\cup$ 和 $\cap$。
*   **容斥原理**：
    $$|A \cup B| = |A| + |B| - |A \cap B|$$
    $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

#### 4. 排列与组合
*   **排列数 $A_n^m$**（考虑先后顺序）：
    $$A_n^m = \frac{n!}{(n-m)!} = n \times (n-1) \times \dots \times (n-m+1)$$
*   **组合数 $C_n^m$**（不考虑相对顺序）：
    $$C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}$$
*   **杨辉三角递推公式**：
    $$C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$$

---

### 二、 经典例题

**【例题1】** 求整数 $360$ 的正因数个数（ ）。
A. $12$  
B. $18$  
C. $24$  
D. $30$

> **【解析】** C。
> 1. 首先对 $360$ 进行质因数分解：
>    $$360 = 36 \times 10 = (2^2 \times 3^2) \times (2 \times 5) = 2^3 \times 3^2 \times 5^1$$
> 2. 根据因数个数定理，正因数个数为各质因子指数加1后的乘积：
>    $$\text{因数个数} = (3 + 1) \times (2 + 1) \times (1 + 1) = 4 \times 3 \times 2 = 24$$

**【例题2】** 某学校共有 100 名学生。其中有 55 人喜欢打篮球，45 人喜欢踢足球，有 22 人这两项运动都喜欢。那么，这两项运动都不喜欢的学生人数为（ ）。
A. $18$  
B. $22$  
C. $25$  
D. $32$

> **【解析】** B。
> 设喜欢篮球的学生集合为 $A$，喜欢足球的学生集合为 $B$。
> 至少喜欢其中一项运动的学生人数为并集的大小：
> $$|A \cup B| = |A| + |B| - |A \cap B| = 55 + 45 - 22 = 78 \text{ 人}$$
> 那么这两项都不喜欢的学生人数为：
> $$\text{总人数} - |A \cup B| = 100 - 78 = 22 \text{ 人}$$

---

### 三、 巩固练习

1. 在 $1$ 到 $100$ 的自然数中，既不能被 $2$ 整除，也不能被 $3$ 整除的数的个数是（ ）。
   A. $33$ &emsp; B. $34$ &emsp; C. $35$ &emsp; D. $37$

2. 从 5 名男同学和 4 名女同学中，选出 3 名代表去参加信息学交流会。要求代表中既有男同学，又有女同学。请问一共有（ ）种不同的选派方案。
   A. $70$ &emsp; B. $74$ &emsp; C. $80$ &emsp; D. $84$

3. 设集合 $U = \{1, 2, 3, 4, 5\}$。已知集合 $A = \{1, 3, 5\}$，$B = \{3, 4\}$。那么集合 $\complement_U (A \cap B)$ 的大小是（ ）。
   A. $1$ &emsp; B. $2$ &emsp; C. $4$ &emsp; D. $5$

---

### 四、 答案与解析

1. **A**  
   使用容斥原理计算。在 $1$ 到 $100$ 中：
   *   能被 $2$ 整除的数有：$|A| = \lfloor 100 / 2 \rfloor = 50$ 个。
   *   能被 $3$ 整除的数有：$|B| = \lfloor 100 / 3 \rfloor = 33$ 个。
   *   既能被 $2$ 也能被 $3$ 整除（即能被 $6$ 整除）的数有：$|A \cap B| = \lfloor 100 / 6 \rfloor = 16$ 个。
   *   能被 $2$ 或被 $3$ 整除的数的总数：
       $$|A \cup B| = |A| + |B| - |A \cap B| = 50 + 33 - 16 = 67 \text{ 个}$$
   *   既不能被 $2$ 也不能被 $3$ 整除的数的个数为：
       $$100 - 67 = 33 \text{ 个}$$

2. **A**  
   采用**挡板/间接法（总数减去不符合条件的方案）**：
   *   任意选 3 人的无条件总方案数为：
       $$C_9^3 = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84 \text{ 种}$$
   *   不符合条件的情况：
       1. 全是男代表：从 5 名男同学中选 3 人，方案数为 $C_5^3 = C_5^2 = 10$ 种。
       2. 全是女代表：从 4 名女同学中选 3 人，方案数为 $C_4^3 = C_4^1 = 4$ 种。
   *   符合既有男又有女的选法为：
       $$\text{总数} - \text{全男} - \text{全女} = 84 - 10 - 4 = 70 \text{ 种}$$

3. **C**  
   *   首先计算交集：$A \cap B = \{1, 3, 5\} \cap \{3, 4\} = \{3\}$。
   *   求相对于全集 $U$ 的补集 $\complement_U (A \cap B)$，即从 $U$ 中剔除属于 $\{3\}$ 的元素：
       $$\complement_U (A \cap B) = \{1, 2, 4, 5\}$$
   *   该补集的大小（元素个数）为 $4$。

---

## DAY6：真题实战与程序阅读突破

### 一、 核心知识点

#### 1. 程序阅读题解题策略
*   **快速通读**：不要纠结于个别生疏的语法细节，首先通过**函数名、变量名、输入输出**判断该程序的核心功能（如：求最大子段和、判断素数、求 GCD、深度优先遍历等）。
*   **特殊情况代入（核心）**：
    *   利用 $N = 0, N = 1$、边界值、负数等，手动模拟一两轮，往往能发现循环终止或条件分支的规律。
    *   在草稿纸上建立变量跟踪表，随着循环执行，记录主要变量的递变值。

#### 2. 程序填空题攻坚套路
*   **代入验证法**：将给出的 A、B、C、D 四个选项依次代入空格中，并运用题目已知输入数据进行模拟。
*   **代码对称性**：
    *   例如：若上方有 `l = mid + 1`，则另一分支高度可能为 `r = mid - 1`。
    *   若上方写了 `visit[i] = true`，其下方或退出递归处多半需要恢复现场 `visit[i] = false`。
*   **边界判断**：重点关注是 `<` 还是 `<=`, 是 `0` 还是 `1` 起点。

---

### 二、 真题模拟精选与深度解析

#### 【题目】 程序阅读题（本题共6小题，共15分）

仔细阅读下列 C++ 代码，并回答后面的问题（判断题请答 T 或 F，单选题请选出唯一正确选项）。

```cpp
#include <iostream>
using namespace std;

int n;
int a[105];

int solve(int L, int R) {
    if (L == R) return a[L];
    int mid = (L + R) / 2;
    int sumL = solve(L, mid);
    int sumR = solve(mid + 1, R);
    
    int sum = 0, maxL = a[mid], maxR = a[mid + 1];
    for (int i = mid; i >= L; i--) {
        sum += a[i];
        if (sum > maxL) maxL = sum;
    }
    sum = 0;
    for (int i = mid + 1; i <= R; i++) {
        sum += a[i];
        if (sum > maxR) maxR = sum;
    }
    
    int ans = sumL;
    if (sumR > ans) ans = sumR;
    if (maxL + maxR > ans) ans = maxL + maxR;
    return ans;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(1, n) << endl;
    return 0;
}
```

##### 判断题
1. 若输入数据全为正数，则 `solve(1, n)` 的返回值必定等于整个数组中所有元素的累加和。（ ）
2. 该算法采用了分治的思想，其整体时间复杂度为 $O(n^2)$。（ ）
3. 当输入为 `5 \n -2 -3 -4 -1 -5` 时，输出的结果是 `-1`。（ ）

##### 单选题
4. 该程序实现的核心功能是（ ）。
   A. 寻找数组中的最大值  
   B. 寻找数组中的最大连续子段和  
   C. 对数组进行分治归并排序  
   D. 计算数组中所有子段和的平均值
5. 若输入数据为 `4 \n 1 -2 3 5`，则程序运行输出的结果是（ ）。
   A. `9` &emsp; B. `8` &emsp; C. `7` &emsp; D. `6`

---

### 三、 深度解析与答案

#### 核心程序分析
本程序是**最大连续子段和（Maximum Subarray Sum）**的经典**分治法**实现。
它的解法逻辑为：
1. **Divide（分）**：将当前区间 $[L, R]$ 划分为左右两半：$[L, mid]$ 和 $[mid+1, R]$。
2. **Conquer（治）**：
   *   最大子段和可能完全分布在左半边：`sumL = solve(L, mid)`。
   *   最大子段和可能完全分布在右半边：`sumR = solve(mid + 1, R)`。
   *   最大子段和可能横跨左右边界，即包含 $a[mid]$ 和 $a[mid+1]$。
3. **Combine（合）**：对于横跨中间的情况，从中间出发分别向左、向右累加搜寻最大单向子段和：
   *   向左累加：`maxL` 记录以 $a[mid]$ 结尾的左侧最大连续和。
   *   向右累加：`maxR` 记录以 $a[mid+1]$ 开始的右侧最大连续和。
   *   横跨中间的最大连续和即为 `maxL + maxR`。
4. 最终比较三者：`sumL`、`sumR`、`maxL + maxR`，返回最大值。

---

#### 题目解答

1. **T**  
   若全为正数，最大连续子段和显然是选择全部元素，故返回值必定等于所有元素的累加和。

2. **F**  
   分治法求解最大子段和的递推式为 $T(n) = 2T(n/2) + O(n)$。
   根据主定理，该递推关系的时间复杂度为 $O(n \log n)$，而非 $O(n^2)$。

3. **T**  
   当数组全为负数时，最大的连续子段和就是这些负数中的最大值（即绝对值最小的那个负数）。输入数据中最大值为 `-1`，故输出 `-1`。

4. **B**  
   通过上述"核心程序分析"可知，该程序通过分治思想寻找并输出了数组的**最大连续子段和**。

5. **B**  
   输入为：`4` 个元素，数组为 `[1, -2, 3, 5]`。
   我们寻找该数组中连续子段的最大和。
   显然，选择子段 `[3, 5]`，其和为 $3 + 5 = 8$。
   其他任何子段：
   *   `[1]` $\to 1$
   *   `[1, -2]` $\to -1$
   *   `[1, -2, 3, 5]` $\to 7$
   *   `[-2, 3, 5]` $\to 6$
   最大和均为 $8$。所以输出结果为 `8`。选择 B。

---

## 考前冲刺复习建议

1. **温故知新**：考前最后一天，建议对照 **DAY1 到 DAY5** 的核心知识卡片和附录公式，重点扫除概念盲区。
2. **临考心态**：初赛笔试满分 100 分。根据往年分数线，大部分省市晋级分数在 **50~75分** 之间。做题时遇到不会的难题，要懂得合理分配时间，优先保障基础选择题和基础程序分析题的得分率。
3. **细节决定成败**：注意填涂答题卡位置，注意 C++ 中 `=` 与 `==` 的区别，防止笔误。

CSP-J 第一轮（初赛）6天系统冲刺讲义

DAY1：计算机基础、进制转换与编码

一、核心知识点

1. 计算机硬件基本构成

五大部件：运算器、控制器、存储器、输入设备、输出设备。
CPU（中央处理器）：由运算器和控制器组成。
存储器：
- 内存（RAM）：随机存取存储器，读写速度快，断电后数据丢失。
- 外存（硬盘、U盘等）：读写速度相对慢，断电后数据不丢失。

2. 操作系统与网络基础

操作系统（OS）：系统软件，是用户和计算机硬件之间的接口（如 Windows, Linux, macOS）。
计算机网络分类：按覆盖范围分为局域网（LAN）、城域网（MAN）、广域网（WAN）。
IP 地址与域名：
- IPv4 地址由 32 位二进制数（4个字节）组成，常用点分十进制表示（如 192.168.1.1），每段范围为 0~255。
- DNS（域名系统）：负责将人类易读的域名（如 www.noi.cn）解析为计算机识别的 IP 地址。
常见网络协议：HTTP（80端口）、HTTPS（443端口）、FTP（21端口）、TCP/IP。

3. 进制转换与存储单位

进制标识：C++ 中，八进制以 0 开头，十六进制以 0x 开头，二进制以 0b 开头。
转换方法：
- R进制转十进制：按权展开法。
- 十进制转R进制：除 R 取余，逆序排列。
- 二、八、十六进制互转：3位二进制对应1位八进制；4位二进制对应1位十六进制。
存储单位： $$1 \text{ Byte} = 8 \text{ bits}$$ $$1 \text{ KB} = 1024 \text{ B}, \quad 1 \text{ MB} = 1024 \text{ KB}, \quad 1 \text{ GB} = 1024 \text{ MB}, \quad 1 \text{ TB} = 1024 \text{ GB}$$

4. 原码、反码与补码

计算机内部一律采用补码存储整数。
正数：原码 = 反码 = 补码。
负数：
- 原码：最高位为符号位（1表示负数），其余为数值位。
- 反码：符号位不变，数值位按位取反。
- 补码：反码 + 1。
特值速记：在 8 位有符号整型中，-1 的补码是 11111111（十六进制 0xFF）。

5. 位运算与字符编码

位运算符：按位与 &、按位或 |、按位异或 ^、按位取反 ~、左移 <<、右移 >>。
ASCII 码常用值：
- '\0' $\to$ 0
- 空格 ' ' $\to$ 32
- '0' $\to$ 48
- 'A' $\to$ 65
- 'a' $\to$ 97
- 大小写字符差值：'a' - 'A' = 32。

二、经典例题

【例题1】 计算机在执行程序时，必须将对应的指令和数据先加载到（）中，CPU 才能进行访问。 A. 键盘
B. 寄存器
C. 内存
D. 硬盘

【解析】 C。外存（硬盘）中的程序和数据必须调入内存（RAM）后，才能被 CPU 读取并执行。寄存器属于 CPU 内部的高速暂存器，不是批量加载程序的地方。

【例题2】 将十进制数 $85.625$ 翻译为二进制数是（）。 A. $1010101.101$
B. $1010101.011$
C. $1011101.101$
D. $1011101.11$

【解析】 A。 1. 整数部分：$85 = 64 + 16 + 4 + 1 = 2^6 + 2^4 + 2^2 + 2^0 \to (1010101)_2$。 2. 小数部分：乘2取整法。 $0.625 \times 2 = 1.25$（取整1） $0.25 \times 2 = 0.5$（取整0） $0.5 \times 2 = 1.0$（取整1，结束）所以小数部分为 $(.101)_2$。合并后为 $1010101.101$。

三、巩固练习

一个 32 位有符号整数，在计算机中以补码形式表示为 0xFFFFFFFA，则它对应的十进制值是（）。 A. $-5$ B. $-6$ C. $-10$ D. $-7$
设变量 $a = 5$，二进制表示为 8 位。执行表达式 a = ~a; 后，变量 $a$ 的十进制值是（）。 A. $-5$ B. $-6$ C. $250$ D. $5$
假设某张高清照片的无损像素大小为 $2048 \times 1024$，每个像素使用 24 位真彩色（RGB，各占 8 位）表示。如果不进行任何压缩，保存该图片需要占用大约（）MB 的存储空间。 A. $2$ B. $6$ C. $16$ D. $48$

四、答案与解析

B
十六进制 0xFFFFFFFA 最高位为 1（二进制 1111...1010），说明是一个负数补码。求原码方法（逆操作）：补码减 1 得到反码 0xFFFFFFF9，再按位取反（符号位不变）得到原码 0x00000006，结合符号位，对应十进制值为 $-6$。
B
在 C++ 中，int 类型的 ~ 是按位取反运算符。 $5$ 的补码为 00000101。按位取反后变为 11111010。这是一个负数补码，将其转换为十进制：先减 1 得到反码 11111001，再取反（除符号位外）得到原码 10000110，其值为 $-6$。 (便捷公式：对整数 $x$ 取反的值为 $-(x+1)$)。
B
总比特数 = $2048 \times 1024 \times 24 \text{ bits}$。转换为字节 = $\frac{2048 \times 1024 \times 24}{8} = 2048 \times 1024 \times 3 \text{ Bytes}$。转换为 KB = $\frac{2048 \times 1024 \times 3}{1024} = 2048 \times 3 = 6144 \text{ KB}$。转换为 MB = $\frac{6144}{1024} = 6 \text{ MB}$。

DAY2：程序结构设计

一、核心知识点

1. C++ 基础要素

标识符命名：只能由字母、数字、下划线组成，不能以数字开头，且不能与关键字重名。区分大小写。
基本数据类型占用空间（常见 32/64 位环境）：
- char (1字节)
- bool (1字节)
- int (4字节，约 $\pm 2.1 \times 10^9$)
- long long (8字节，约 $\pm 9.2 \times 10^{18}$)
- float (4字节)
- double (8字节)

2. 格式化输入输出

scanf / printf 比 cin / cout 具有更快的执行效率。
格式占位符：%d (int), %lld (long long), %f (float), %lf (double), %c (char)。
printf("%.2lf", val)：保留两位小数输出。

3. 分支与循环结构

条件选择：if-else 链，以及 switch-case（case 后面必须为整型或字符型常量，注意 break 的穿透效应）。
循环控制：for、while、do-while（后者至少执行一次）。
跳转语句：break（终止并跳出当前循环），continue（跳过本轮循环余下语句，直接进入下一次循环判断/更新）。

4. 结构化程序设计与流程图

三大基本结构：顺序结构、分支结构、循环结构。
流程图符号：
- 圆角矩形/椭圆：起止框。
- 平行四边形：输入/输出框。
- 矩形：处理/执行框。
- 菱形：判断/条件框（必有两个出口：Y/N）。

5. 结构体（`struct`）

自定义数据类型，可打包多个不同类型的数据成员。
声明末尾不能遗漏分号。支持成员运算符 . 访问。

二、经典例题

【例题1】 下列给出的 C++ 标识符中，合法的是（）。 A. 2_name
B. _temp_val
C. int
D. a#b

【解析】 B。A 选项以数字开头，不合法；C 选项 int 是保留关键字，不能作为标识符；D 选项包含非法字符 #。

【例题2】 阅读以下程序，写出其运行输出结果：

#include <iostream>
using namespace std;
int main() {
    int sum = 0;
    for (int i = 1; i <= 10; i++) {
        if (i % 3 == 0) continue;
        if (i > 7) break;
        sum += i;
    }
    cout << sum << endl;
    return 0;
}

【解析】 运行分析如下： * $i=1$：不满足 i%3==0 和 i>7，sum = 0 + 1 = 1。 * $i=2$：不满足条件，sum = 1 + 2 = 3。 * $i=3$：满足 i%3==0，触发 continue，跳过后续，进入下一轮。 * $i=4$：不满足条件，sum = 3 + 4 = 7。 * $i=5$：不满足条件，sum = 7 + 5 = 12。 * $i=6$：满足 i%3==0，触发 continue。 * $i=7$：不满足条件，sum = 12 + 7 = 19。 * $i=8$：满足 i>7，触发 break，整个循环终止。最终输出 19。

三、巩固练习

在流程图中，表示"对数据进行计算、赋值或执行具体操作"的图形是（）。 A. 菱形 B. 平行四边形 C. 矩形 D. 椭圆形
下列关于 C++ 结构体（struct）的说法，错误的是（）。 A. 结构体中各个成员的类型可以各不相同 B. 结构体定义结束后必须以分号（;）结尾 C. 定义结构体变量时，可以直接使用该结构体名作为类型名 D. 结构体和联合体（union）完全相同，所有成员共用同一段物理内存
阅读以下程序，写出运行输出结果：

#include <iostream>
using namespace std;
int main() {
    int a = 2, b = 3;
    int ans = 0;
    switch (a + b) {
        case 4: ans += 1;
        case 5: ans += 2;
        case 6: ans += 3; break;
        default: ans += 4;
    }
    cout << ans << endl;
    return 0;
}

四、答案与解析

C
矩形代表处理框，用来表示数据的计算、处理与赋值；菱形代表条件判断框；平行四边形代表输入/输出框；椭圆形/圆角矩形代表起止框。
D
结构体的每个成员在内存中拥有独立的存储空间；而联合体（union）的所有成员共享同一段内存空间，其大小由最大成员决定。两者并不等价。
输出：5
a + b = 5，程序跳转至 case 5。由于 case 5 后面没有写 break，程序会发生"穿透"，继续执行 case 6。执行 case 5 时，ans += 2 $\to$ ans 变为 2。继续向下执行 case 6，ans += 3 $\to$ ans 变为 5，随后遇到 break，跳出 switch 语句。最终输出 5。

DAY3：数据结构

一、核心知识点

1. 线性结构

一维与二维数组：
- 在内存中是连续存放的（二维数组按行优先顺序存放）。
- 数组名代表首地址，下标从 0 开始。
字符串：
- C风格字符数组：以 '\0'（ASCII为0）为结束符。strlen() 测量不含 '\0' 的有效长度，而 sizeof() 统计分配的总空间（包含 '\0'）。
- std::string：提供 size()、substr(pos, len)、find(str) 等操作。
栈（Stack）：后进先出（LIFO），仅在栈顶进行操作。
队列（Queue）：先进先出（FIFO），队尾入队（push），队头出队（pop）。

2. 二叉树的性质与遍历

基本公式：
- 第 $i$ 层最多有 $2^{i-1}$ 个节点。
- 深度为 $k$ 的二叉树最多有 $2^k - 1$ 个节点。
- 节点关系：度为 0 的叶子节点数 $n_0$ 与度为 2 的分支节点数 $n_2$ 满足： $$n_0 = n_2 + 1$$
遍历方式：
- 前序（先根）：根 -> 左 -> 右
- 中序（中根）：左 -> 根 -> 右
- 后序（后根）：左 -> 右 -> 根
- 规律：中序序列配合前序（或后序）序列可唯一确定一棵二叉树。若仅知前序和后序，则无法唯一确定。

3. 特殊树与图

哈夫曼树（Huffman Tree）：带权路径长度（WPL）最小的二叉树。每次合并权重最小的两个节点。生成的哈夫曼编码无前缀重合问题。
二叉搜索树（BST）：左子树上所有节点值均小于根节点，右子树上所有节点值均大于根节点。中序遍历 BST 可以得到一个严格单调递增的序列。
图的表示：
- 邻接矩阵：g[i][j] 存储边权，适合稠密图，空间复杂度 $O(V^2)$。
- 邻接表：链表数组，适合稀疏图，空间复杂度 $O(V + E)$。

二、经典例题

【例题1】 某个表达式在栈中的操作顺序为：将元素 $a, b, c, d$ 依次入栈，期间伴随出栈操作。下列哪个序列不可能是该栈输出的序列？（） A. $a, b, c, d$
B. $d, c, b, a$
C. $b, a, c, d$
D. $d, a, b, c$

【解析】 D。由于栈是 LIFO（后进先出），若 $d$ 先出栈，说明 $a, b, c$ 都在栈中。此时栈内自底向上依次为 $[a, b, c]$，因此接下来的出栈顺序只能是 $c$，然后是 $b$，最后是 $a$。所以 $d$ 后面紧跟 $a$ 属于非法出栈序列。

【例题2】 已知某二叉树的前序遍历序列为 ABDECF，中序遍历序列为 DBEACF。求该二叉树的后序遍历序列。

【解析】 1. 根据前序 ABDECF 可知，根节点为 A。 2. 对照中序 DBEACF，以 A 为界限，左半部分 DBE 为左子树，右半部分 CF 为右子树。 3. 对左子树 DBE 递归分析：前序中 B 先出现，故 B 是左子树的根。中序中 D 在 B 左侧，E 在 B 右侧，所以 D 是 B 的左孩子，E 是 B 的右孩子。 4. 对右子树 CF 递归分析：前序中 C 先于 F，故 C 是右子树根。中序中 C 在 F 左侧，故 F 是 C 的右孩子。 5. 还原后进行后序遍历：左 -> 右 -> 根 $\to$ D -> E -> B -> F -> C -> A。结果为 DEBFCA。

三、巩固练习

设一棵完全二叉树包含 $2026$ 个节点，则该树的叶子节点（度为0的节点）个数为（）。 A. $1013$ B. $1014$ C. $1012$ D. $1015$
现有一组权值为 ${2, 3, 5, 7, 8}$ 的叶子节点，用它们构造一棵哈夫曼树，则该树的带权路径长度（WPL）为（）。 A. $53$ B. $55$ C. $57$ D. $59$
字符数组 char s[] = "Noi2026\0CSP";，执行 cout << strlen(s) << " " << sizeof(s); 后的输出是（）。 A. 7 12 B. 7 11 C. 11 12 D. 7 8

四、答案与解析

A
设度为 0, 1, 2 的节点数分别为 $n_0, n_1, n_2$。有方程：$n_0 + n_1 + n_2 = 2026$。又因为 $n_0 = n_2 + 1$，代入消去 $n_2$ 得： $2n_0 - 1 + n_1 = 2026 \implies 2n_0 + n_1 = 2027$。由于该树是完全二叉树，其度为 1 的节点数 $n_1$ 只能是 $0$ 或 $1$。因为 $2n_0$ 必定为偶数，而 $2027$ 为奇数，故 $n_1$ 必须取 $1$。由此得：$2n_0 + 1 = 2027 \implies 2n_0 = 2026 \implies n_0 = 1013$。
B
按照哈夫曼树构造步骤（小根堆贪心合并）：
初始集合：${2, 3, 5, 7, 8}$
第一轮：选择最小的 $2$ 和 $3$ 合并，生成新节点 $5$（其下挂 $2, 3$）。集合变为 ${5, 5, 7, 8}$。
第二轮：合并最小的两个 $5$ 和 $5$，生成新节点 $10$（下挂两个 $5$，其中一个 $5$ 下挂 $2,3$）。集合变为 ${7, 8, 10}$。
第三轮：合并最小的 $7$ 和 $8$，生成新节点 $15$。集合变为 ${10, 15}$。
第四轮：合并 $10$ 和 $15$，生成根节点 $25$。
叶子节点对应的路径长度（深度）：
- $7$ 和 $8$：路径长度为 2。
- $5$（非合并产生的那个原始叶子）：路径长度为 2。
- $2$ 和 $3$：路径长度为 3。
WPL 计算： $$\text{WPL} = 7 \times 2 + 8 \times 2 + 5 \times 2 + 2 \times 3 + 3 \times 3 = 14 + 16 + 10 + 6 + 9 = 55$$
A
strlen(s) 遇到第一个空字符 '\0' 即停止统计。"Noi2026" 包含 7 个有效字符，因此长度为 7。
sizeof(s) 用于度量编译器分配给该字符数组的总物理空间（包括显式写入的每一个字符和末尾隐含自动追加的一个 '\0'）。
物理内容为：'N', 'o', 'i', '2', '0', '2', '6', '\0', 'C', 'S', 'P', '\0'，共 12 字节。因此输出 7 12。

DAY4：算法入门与分析

一、核心知识点

1. 基础算法思想

枚举法：在确定的范围内，不重复、不遗漏地尝试每一种可能。关键在于确定合理的范围和判定标准。
模拟法：按照题目的业务逻辑、规则，使用代码复现。需要特别注意边界条件和状态更新。
贪心算法：在每一步决策中都采取当前局部最优的选择，以期获得全局最优解。贪心策略需要通过严格的数学证明或反证法来确认其正确性。
二分查找：在有序序列中通过每次折半区间来查找目标，查找的时间复杂度为 $O(\log n)$。
前缀和：
- 构造：$S[i] = S[i-1] + A[i]$。
- 应用：以 $O(1)$ 的时间复杂度快速计算区间和 $\sum_{i=L}^{R} A[i] = S[R] - S[L-1]$。

2. 排序算法对比

稳定性：若相同数值在排序后保持原有的相对先后位置不变，则称该排序稳定。

排序名称	最好时间	最坏时间	平均时间	空间复杂度	稳定性
冒泡排序	$O(n)$ 或 $O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(k)$	稳定
快速排序	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	$O(\log n)$	不稳定

3. 渐进复杂度分析

常数级 $O(1) <$ 对数级 $O(\log n) <$ 线性级 $O(n) <$ 线性对数级 $O(n \log n) <$ 平方级 $O(n^2) <$ 指数级 $O(2^n)$。
主定理思维简化：在递推关系中，如果每次将规模缩小一半（如二分、归并），通常会产生带有 $\log n$ 的复杂度项。

二、经典例题

【例题1】 依次对数据序列 $[12, 5, 8, 1, 9]$ 进行选择排序（升序），完成第一轮交换后的序列为（）。 A. $[5, 12, 8, 1, 9]$
B. $[1, 5, 8, 12, 9]$
C. $[1, 12, 8, 5, 9]$
D. $[1, 5, 8, 9, 12]$

【解析】 B。选择排序第一轮：从整段区间 $[12, 5, 8, 1, 9]$ 中搜索最小值。扫描发现最小值为 1（下标 3）。将最小值 1 与当前待排区间首元素 12（下标 0）进行对调。交换后序列变为 $[1, 5, 8, 12, 9]$。选择 B。

【例题2】 计算下列程序段的时间复杂度：

int count = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j += i) {
        count++;
    }
}

【解析】 外层循环 $i$ 遍历 $1$ 到 $n$。当外层变量为 $i$ 时，内层循环的步长为 $i$，内层执行次数约为 $\frac{n}{i}$。总执行次数为： $$T(n) = \frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n} = n \left( 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)$$ 根据调和级数求和公式，$1 + \frac{1}{2} + \dots + \frac{1}{n} \approx \ln n$。因此，该程序段的渐进时间复杂度为 $O(n \log n)$。

三、巩固练习

在一棵已经排好序（升序）的拥有 $1000$ 个元素的数组中进行二分查找（Binary Search），在最坏情况下，查找某元素或判定其不存在，最多需要进行（）次元素比较。 A. $9$ B. $10$ C. $11$ D. $500$
设原序列中包含两个数值相同的元素 $A$ 和 $B$，且在排序前 $A$ 排在 $B$ 之前。若经过某种排序算法处理后，$B$ 可能会排到 $A$ 之前，则此排序算法被称为是不稳定的。下列四个排序算法中，不稳定的是（）。 A. 冒泡排序 B. 直接插入排序 C. 简单选择排序 D. 归并排序
阅读以下程序，写出运行输出结果：

#include <iostream>
using namespace std;
int main() {
    int n = 5;
    int a[6] = {0, 2, 4, 1, 5, 3}; // 下标从1开始
    int s[6] = {0};
    for (int i = 1; i <= n; i++) {
        s[i] = s[i-1] + a[i];
    }
    cout << s[4] - s[1] << " " << s[5] - s[2] << endl;
    return 0;
}

四、答案与解析

B
二分查找在最坏情况下的比较次数为 $\lfloor \log_2 n \rfloor + 1$。代入 $n = 1000$：因为 $2^9 = 512 < 1000 < 1024 = 2^{10}$，所以 $\lfloor \log_2 1000 \rfloor = 9$。最坏比较次数为 $9 + 1 = 10$ 次。
C
冒泡排序、插入排序和归并排序均为稳定排序。选择排序通过在未排序部分中寻找极值并与首位进行长距离交换，这种操作极易打破相同元素的相对顺序（例如序列 $[5, 5, 2]$，扫描第一轮将最小的 $2$ 与第一个 $5$ 交换，导致两个 $5$ 的先后顺序发生颠倒）。
输出：10 9
程序通过循环计算出了前缀和数组 $s$：
$s[0] = 0$
$s[1] = 2$
$s[2] = 2+4 = 6$
$s[3] = 6+1 = 7$
$s[4] = 7+5 = 12$
$s[5] = 12+3 = 15$ 根据区间和公式：
s[4] - s[1] = $12 - 2 = 10$（对应元素 $a[2]+a[3]+a[4] = 4+1+5 = 10$）。
s[5] - s[2] = $15 - 6 = 9$（对应元素 $a[3]+a[4]+a[5] = 1+5+3 = 9$）。

DAY5：信奥数学基础

一、核心知识点

1. 整除与素数筛

素数（质数）：大于 1 的自然数中，除 1 和本身外无其他因数。
唯一分解定理：任何大于 1 的整数 $N$ 均能唯一分解为若干质数的乘积： $$N = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$$ 其正因数的个数为 $(e_1 + 1)(e_2 + 1)\dots(e_k + 1)$。
埃氏筛法：从 2 开始，若当前数未被标记，则其为质数，并将其所有倍数（如 $2i, 3i, \dots$）标记为合数。时间复杂度 $O(n \log \log n)$。

2. 最大公约数（GCD）与最小公倍数（LCM）

欧几里得算法（辗转相除法）： $$\gcd(a, b) = \gcd(b, a \bmod b)$$ 在 C++ 中可以利用递归一行实现。
基本性质： $$\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$$

3. 集合运算与容斥原理

子集数：大小为 $n$ 的集合，其子集总数为 $2^n$ 个，真子集总数为 $2^n - 1$ 个。
并集与交集：符号分别为 $\cup$ 和 $\cap$。
容斥原理： $$|A \cup B| = |A| + |B| - |A \cap B|$$ $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

4. 排列与组合

排列数 $A_n^m$（考虑先后顺序）： $$A_n^m = \frac{n!}{(n-m)!} = n \times (n-1) \times \dots \times (n-m+1)$$
组合数 $C_n^m$（不考虑相对顺序）： $$C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}$$
杨辉三角递推公式： $$C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$$

二、经典例题

【例题1】 求整数 $360$ 的正因数个数（）。 A. $12$
B. $18$
C. $24$
D. $30$

【解析】 C。 1. 首先对 $360$ 进行质因数分解： $$360 = 36 \times 10 = (2^2 \times 3^2) \times (2 \times 5) = 2^3 \times 3^2 \times 5^1$$ 2. 根据因数个数定理，正因数个数为各质因子指数加1后的乘积： $$\text{因数个数} = (3 + 1) \times (2 + 1) \times (1 + 1) = 4 \times 3 \times 2 = 24$$

【例题2】 某学校共有 100 名学生。其中有 55 人喜欢打篮球，45 人喜欢踢足球，有 22 人这两项运动都喜欢。那么，这两项运动都不喜欢的学生人数为（）。 A. $18$
B. $22$
C. $25$
D. $32$

【解析】 B。设喜欢篮球的学生集合为 $A$，喜欢足球的学生集合为 $B$。至少喜欢其中一项运动的学生人数为并集的大小： $$|A \cup B| = |A| + |B| - |A \cap B| = 55 + 45 - 22 = 78 \text{ 人}$$ 那么这两项都不喜欢的学生人数为： $$\text{总人数} - |A \cup B| = 100 - 78 = 22 \text{ 人}$$

三、巩固练习

在 $1$ 到 $100$ 的自然数中，既不能被 $2$ 整除，也不能被 $3$ 整除的数的个数是（）。 A. $33$ B. $34$ C. $35$ D. $37$
从 5 名男同学和 4 名女同学中，选出 3 名代表去参加信息学交流会。要求代表中既有男同学，又有女同学。请问一共有（）种不同的选派方案。 A. $70$ B. $74$ C. $80$ D. $84$
设集合 $U = {1, 2, 3, 4, 5}$。已知集合 $A = {1, 3, 5}$，$B = {3, 4}$。那么集合 $\complement_U (A \cap B)$ 的大小是（）。 A. $1$ B. $2$ C. $4$ D. $5$

四、答案与解析

A
使用容斥原理计算。在 $1$ 到 $100$ 中：
能被 $2$ 整除的数有：$|A| = \lfloor 100 / 2 \rfloor = 50$ 个。
能被 $3$ 整除的数有：$|B| = \lfloor 100 / 3 \rfloor = 33$ 个。
既能被 $2$ 也能被 $3$ 整除（即能被 $6$ 整除）的数有：$|A \cap B| = \lfloor 100 / 6 \rfloor = 16$ 个。
能被 $2$ 或被 $3$ 整除的数的总数： $$|A \cup B| = |A| + |B| - |A \cap B| = 50 + 33 - 16 = 67 \text{ 个}$$
既不能被 $2$ 也不能被 $3$ 整除的数的个数为： $$100 - 67 = 33 \text{ 个}$$
A
采用挡板/间接法（总数减去不符合条件的方案）：
任意选 3 人的无条件总方案数为： $$C_9^3 = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84 \text{ 种}$$
不符合条件的情况：
1. 全是男代表：从 5 名男同学中选 3 人，方案数为 $C_5^3 = C_5^2 = 10$ 种。
2. 全是女代表：从 4 名女同学中选 3 人，方案数为 $C_4^3 = C_4^1 = 4$ 种。
符合既有男又有女的选法为： $$\text{总数} - \text{全男} - \text{全女} = 84 - 10 - 4 = 70 \text{ 种}$$
C
首先计算交集：$A \cap B = {1, 3, 5} \cap {3, 4} = {3}$。
求相对于全集 $U$ 的补集 $\complement_U (A \cap B)$，即从 $U$ 中剔除属于 ${3}$ 的元素： $$\complement_U (A \cap B) = {1, 2, 4, 5}$$
该补集的大小（元素个数）为 $4$。

DAY6：真题实战与程序阅读突破

一、核心知识点

1. 程序阅读题解题策略

快速通读：不要纠结于个别生疏的语法细节，首先通过函数名、变量名、输入输出判断该程序的核心功能（如：求最大子段和、判断素数、求 GCD、深度优先遍历等）。
特殊情况代入（核心）：
- 利用 $N = 0, N = 1$、边界值、负数等，手动模拟一两轮，往往能发现循环终止或条件分支的规律。
- 在草稿纸上建立变量跟踪表，随着循环执行，记录主要变量的递变值。

2. 程序填空题攻坚套路

代入验证法：将给出的 A、B、C、D 四个选项依次代入空格中，并运用题目已知输入数据进行模拟。
代码对称性：
- 例如：若上方有 l = mid + 1，则另一分支高度可能为 r = mid - 1。
- 若上方写了 visit[i] = true，其下方或退出递归处多半需要恢复现场 visit[i] = false。
边界判断：重点关注是 < 还是 <=, 是 0 还是 1 起点。

二、真题模拟精选与深度解析

【题目】程序阅读题（本题共6小题，共15分）

仔细阅读下列 C++ 代码，并回答后面的问题（判断题请答 T 或 F，单选题请选出唯一正确选项）。

#include <iostream>
using namespace std;

int n;
int a[105];

int solve(int L, int R) {
    if (L == R) return a[L];
    int mid = (L + R) / 2;
    int sumL = solve(L, mid);
    int sumR = solve(mid + 1, R);

    int sum = 0, maxL = a[mid], maxR = a[mid + 1];
    for (int i = mid; i >= L; i--) {
        sum += a[i];
        if (sum > maxL) maxL = sum;
    }
    sum = 0;
    for (int i = mid + 1; i <= R; i++) {
        sum += a[i];
        if (sum > maxR) maxR = sum;
    }

    int ans = sumL;
    if (sumR > ans) ans = sumR;
    if (maxL + maxR > ans) ans = maxL + maxR;
    return ans;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(1, n) << endl;
    return 0;
}

判断题

若输入数据全为正数，则 solve(1, n) 的返回值必定等于整个数组中所有元素的累加和。（）
该算法采用了分治的思想，其整体时间复杂度为 $O(n^2)$。（）
当输入为 5 \n -2 -3 -4 -1 -5 时，输出的结果是 -1。（）

单选题

该程序实现的核心功能是（）。 A. 寻找数组中的最大值
B. 寻找数组中的最大连续子段和
C. 对数组进行分治归并排序
D. 计算数组中所有子段和的平均值
若输入数据为 4 \n 1 -2 3 5，则程序运行输出的结果是（）。 A. 9 B. 8 C. 7 D. 6

三、深度解析与答案

核心程序分析

本程序是最大连续子段和（Maximum Subarray Sum）的经典分治法实现。它的解法逻辑为： 1. Divide（分）：将当前区间 $[L, R]$ 划分为左右两半：$[L, mid]$ 和 $[mid+1, R]$。 2. Conquer（治）： * 最大子段和可能完全分布在左半边：sumL = solve(L, mid)。 * 最大子段和可能完全分布在右半边：sumR = solve(mid + 1, R)。 * 最大子段和可能横跨左右边界，即包含 $a[mid]$ 和 $a[mid+1]$。 3. Combine（合）：对于横跨中间的情况，从中间出发分别向左、向右累加搜寻最大单向子段和： * 向左累加：maxL 记录以 $a[mid]$ 结尾的左侧最大连续和。 * 向右累加：maxR 记录以 $a[mid+1]$ 开始的右侧最大连续和。 * 横跨中间的最大连续和即为 maxL + maxR。 4. 最终比较三者：sumL、sumR、maxL + maxR，返回最大值。

题目解答

T
若全为正数，最大连续子段和显然是选择全部元素，故返回值必定等于所有元素的累加和。
F
分治法求解最大子段和的递推式为 $T(n) = 2T(n/2) + O(n)$。根据主定理，该递推关系的时间复杂度为 $O(n \log n)$，而非 $O(n^2)$。
T
当数组全为负数时，最大的连续子段和就是这些负数中的最大值（即绝对值最小的那个负数）。输入数据中最大值为 -1，故输出 -1。
B
通过上述"核心程序分析"可知，该程序通过分治思想寻找并输出了数组的最大连续子段和。
B
输入为：4 个元素，数组为 [1, -2, 3, 5]。我们寻找该数组中连续子段的最大和。显然，选择子段 [3, 5]，其和为 $3 + 5 = 8$。其他任何子段：
[1] $\to 1$
[1, -2] $\to -1$
[1, -2, 3, 5] $\to 7$
[-2, 3, 5] $\to 6$ 最大和均为 $8$。所以输出结果为 8。选择 B。

考前冲刺复习建议

温故知新：考前最后一天，建议对照 DAY1 到 DAY5 的核心知识卡片和附录公式，重点扫除概念盲区。
临考心态：初赛笔试满分 100 分。根据往年分数线，大部分省市晋级分数在 50~75分 之间。做题时遇到不会的难题，要懂得合理分配时间，优先保障基础选择题和基础程序分析题的得分率。
细节决定成败：注意填涂答题卡位置，注意 C++ 中 = 与 == 的区别，防止笔误。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com