# CSP-J 第一轮（初赛）通关集训 · 第六天

---

# Day 6 上午：搜索算法（DFS/BFS）、回溯与动态规划入门（3小时）

## 第一部分：核心知识精讲与考点速记

### 1. DFS（深度优先搜索）与回溯法核心机制
*   **核心思想**：“不撞南墙不回头”，沿着一条路径尽可能深地搜索，遇到死胡同则**回溯（Backtracking）**返回上一层继续探索。
*   **底层支撑**：依赖**系统调用栈（递归实现）**或手写显式栈。
*   **三大经典要素与标准模板**：
    ```cpp
    void dfs(int step, 状态参数) {
        if (到达目标状态 / 满足终止条件) {
            记录最优解或方案数累加;
            return;
        }
        for (int i = 0; i < 所有可行分支; i++) {
            if (满足剪枝条件 / 未被访问) {
                标记当前状态已访问（vis[i] = true）; // 做出选择
                dfs(step + 1, 更新后的状态);         // 递归深入
                标记当前状态未访问（vis[i] = false）; // 【回溯核心：撤销选择】
            }
        }
    }
    ```
*   **剪枝优化思想**：
    *   **可行性剪枝**：若当前状态已经非法或不可能到达终点，提前 `return`。
    *   **最优性剪枝**：若当前花费已经超过已知最优解，提前 `return`。

---

### 2. BFS（广度优先搜索）与泛洪算法（Flood Fill）
*   **核心思想**：“层层扩散，由近及远”，从起点开始逐层向外扫描所有相邻节点。
*   **底层支撑**：必须依赖**队列（Queue，先进先出 FIFO）**。
*   **黄金应用法则（初赛常考性质）**：
    *   在**边权均为 1（无权图）**的图中，**BFS 第一次遍历到目标节点时所经过的步数，必定是全局最短路径（最少步数）**。
*   **DFS vs BFS 综合特性对比表**：

---

### 3. 动态规划（DP）基础与背包模型
*   **动态规划三大核心特征**：
    1.  **最优子结构**：大问题的最优解可以由子问题的最优解推导得出。
    2.  **重叠子问题**：在递归求解过程中，相同的子问题会被反复计算多次（DP 通过表格记忆化避免重复计算）。
    3.  **无后效性**：一旦某个阶段的状态确定，后续决策只取决于当前状态，不受“如何到达该状态”的历史过程影响。
*   **经典模型 1：0/1 背包问题（初赛必背转移方程）**：
    *   *问题描述*：$N$ 件物品，背包容量为 $V$。第 $i$ 件物品体积为 $w[i]$，价值为 $v[i]$，每件物品只能选 0 件或 1 件。
    *   *二维状态转移*：$dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])$
    *   *一维滚动数组空间优化*：
        $$dp[j] = \max(dp[j], dp[j - w[i]] + v[i]) \quad \text{（容量 } j \text{ 必须严格从 } V \text{ 到 } w[i] \text{ 逆序遍历！）}$$
*   **经典模型 2：最长上升子序列（LIS）**：
    *   *状态定义*：$dp[i]$ 表示以 $a[i]$ 结尾的最长上升子序列长度。
    *   *转移方程*：$dp[i] = \max\_{j < i, a[j] < a[i]}(dp[j]) + 1$（基础时间复杂度 $O(n^2)$）。
*   **数列取模的周期性分析（初赛高频技巧）**：
    *   形如斐波那契数列等线性递推数列在模 $m$ 意义下**必然存在周期性（皮萨诺周期 Pisano Period）**。通过手算前几项找出循环节长度 $T$，即可将大指数 $N$ 转化为 $N \bmod T$ 极速求解。

---

## 第二部分：上午精选真题实战（1~15题）

1. 在解决问题时，先选择一种可能的方式向前搜索，一旦发现原先选择并不优或达不到目标就退回一步重新选择，这种算法思想被称为（ ）。【NOIP 2011 普及组】
   A. 回溯法
   B. 枚举法
   C. 动态规划
   D. 贪心法

2. 广度优先搜索（BFS）算法在遍历图或状态空间时，底层必须使用的数据结构是（ ）。【NOIP 2011 普及组】
   A. 单链表
   B. 队列
   C. 栈
   D. 散列表（哈希表）

3. 对一个无向图进行深度优先遍历（DFS），从顶点 $a$ 出发，下列遍历序列中可能合法的是（ ）。【NOIP 2015 普及组】
   A. $a, b, e, c, d, f$
   B. $a, c, f, e, b, d$
   C. $a, e, b, c, f, d$
   D. $a, b, e, d, f, c$

4. 在无向图以顶点 $A\_0$ 为起点进行深度优先搜索遍历，下列顶点序列中绝对不可能出现的是（ ）。【NOIP 2013 普及组】
   A. $A\_0, A\_1, A\_2, A\_3$（已知 $A\_1$ 与 $A\_2$ 无直接连边）
   B. $A\_0, A\_1, A\_3, A\_2$
   C. $A\_0, A\_2, A\_1, A\_3$
   D. $A\_0, A\_3, A\_1, A\_2$

5. 在无向连通图中以顶点 $a$ 为起点进行 DFS 遍历，根据分支搜索对称性，可能最后被遍历到的不同顶点个数有（ ）个。【CSP-J 2021】
   A. 1
   B. 2
   C. 3
   D. 4

6. 4 个人在黑夜中需要穿过一座狭窄的独木桥，他们只有一个手电筒，且桥上每次最多只能同时由 2 人通过。4 人单程过桥所需时间分别为 1、2、5、10 分钟。过桥时由于光线限制，速度必须以较慢者为准，手电筒不能丢掷而必须有人送回。所有人全部安全过桥的最短时间是（ ）分钟。【CSP-J 2021】
   A. 14
   B. 15
   C. 16
   D. 17

7. 下列关于各类数据结构及其典型应用的表述中，**不恰当**的是（ ）。【CSP-J 2022】
   A. 深度优先搜索（DFS）通常借助栈或系统递归栈来实现
   B. 栈的特性是后进先出，队列的特性是先进先出
   C. 广度优先搜索（BFS）通常借助队列来实现
   D. 仅使用两个栈在逻辑上绝对无法模拟出一个队列的功能

8. 已知斐波那契数列定义为 $f[0] = 0, f[1] = 1, f[n] = f[n-1] + f[n-2]$（$n \ge 2$）。计算数列各项对 7 取模后的值，则 $f[2025] \bmod 7$ 的最终结果是（ ）。【CSP-J 2025】
   A. 3
   B. 4
   C. 5
   D. 6

9. 在求解 0/1 背包问题时，若使用一维滚动数组 `dp[j]` 优化空间复杂度，则背包容量 `j` 的循环遍历方向必须是（ ）。【模拟强化题】
   A. 从 $0$ 到 $V$ 顺序遍历
   B. 从 $V$ 到 $w[i]$ 逆序遍历
   C. 先正序再逆序
   D. 任意顺序均可

10. 小胖跑步锻炼，计划在周一到周日安排运动。已知运动方案一每次跑步 3 公里消耗 300 千卡，方案二每次跑步 5 公里消耗 600 千卡。受体能限制，周一到周四最多跑 4 次方案一，周五到周日最多跑 3 次方案二，且一周总跑步里程不能超过 21 公里。小胖一周最多能够消耗的热量是（ ）千卡。【CSP-J 2019】
    A. 3000
    B. 2500
    C. 2400
    D. 2520

11. 在一个网格迷宫中寻找从起点到终点的最短移动步数，最适宜采用的算法策略是（ ）。【模拟强化题】
    A. 贪心算法
    B. 深度优先搜索（DFS）
    C. 广度优先搜索（BFS）
    D. 分治算法

12. 动态规划算法能够有效解决问题的两个最基本前提特征是（ ）。【模拟强化题】
    A. 贪心选择性质与独立子问题
    B. 最优子结构与重叠子问题
    C. 递归定义与快速排序划分
    D. 状态空间极大且无环

13. 设有序列 $\{3, 1, 4, 1, 5, 9, 2, 6, 5\}$，该序列的最长严格上升子序列（LIS）的长度为（ ）。【模拟强化题】
    A. 3
    B. 4
    C. 5
    D. 6

14. 有 8 个互不相同的活动，每个活动有确定的起止时间区间，现需在互不冲突的前提下选择活动。若选 1 个有 7 种方案，选 2 个有 10 种方案，选 3 个有 1 种方案，则所有合法的非空选择方案数总共有（ ）种。【CSP-J 2023】
    A. 31
    B. 18
    C. 21
    D. 33

15. 使用 DFS 遍历包含 $n$ 个顶点、$m$ 条边的图，若采用邻接表存储，其时间复杂度为（ ）。【模拟强化题】
    A. $O(n^2)$
    B. $O(n + m)$
    C. $O(m \log n)$
    D. $O(n \times m)$

---

## 第三部分：上午真题解析与答案速查

1. **【答案】A**  
   **【解析】** 遇到死胡同退回一步重新试探并撤销选择，这是回溯法（Backtracking）的标准定义。
2. **【答案】B**  
   **【解析】** BFS 依据层序由近及远扩散，必须依赖队列（Queue）维护待扩展的状态。
3. **【答案】D**  
   **【解析】** 根据 DFS 规则，从 $a$ 出发，沿邻接边深入访问，合法序列为 $a, b, e, d, f, c$。
4. **【答案】A**  
   **【解析】** A 选项中 $A\_1$ 与 $A\_2$ 之间没有直接连边，DFS 在访问完 $A\_1$ 后若无回溯无法突跳到不相邻的 $A\_2$ 节点，故 A 序列不可能。
5. **【答案】B**  
   **【解析】** 从 $a$ 点出发深入图分支，由搜索分支的对称性，最终叶子端点有 2 种可能。
6. **【答案】B**  
   **【解析】** 经典过河贪心策略：让最快的两人先过送手电，或者让最快的两人送手电掩护最慢的两人一起过。最优步骤：  
   1. 1 和 2 过去（用时 2 分钟）；  
   2. 1 带手电回来（用时 1 分钟）；  
   3. 5 和 10 两个最慢的一起过去（用时 10 分钟）；  
   4. 2 带手电回来（用时 2 分钟）；  
   5. 1 和 2 再次一起过去（用时 2 分钟）。  
   总时间 $= 2 + 1 + 10 + 2 + 2 = 15$ 分钟。
7. **【答案】D**  
   **【解析】** 两个栈完全可以模拟实现一个队列（一个栈负责入队 `push`，另一个栈负责出队 `pop`，当出队栈为空时将入队栈全部元素倒入出队栈即可完成 FIFO）。
8. **【答案】D**  
   **【解析】** 斐波那契数列模 7 的余数序列：$0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1 \dots$  
   循环节长度为 $16$（皮萨诺周期）。$2025 \bmod 16 = 9$，对应余数序列第 9 项（下标 9）为 $6$。
9. **【答案】B**  
   **【解析】** 0/1 背包每个物品只能选一次。逆序遍历容量 $j$ 保证了计算 $dp[j]$ 时所用到的子状态 $dp[j - w[i]]$ 来自上一轮（即尚未放入当前物品 $i$ 的状态），若正序遍历则会退化为完全背包（物品被重复多次选取）。
10. **【答案】C**  
    **【解析】** 设方案一执行 $x$ 天（$x \le 4$），方案二执行 $y$ 天（$y \le 3$），满足约束 $3x + 5y \le 21$。目标最大化消耗热量 $300x + 600y$。枚举可行整数解：当 $y=3$ 时，$3x \le 21 - 15 = 6 \implies x \le 2$，取 $x=2, y=3$，总热量 $= 300 \times 2 + 600 \times 3 = 600 + 1800 = 2400$ 千卡（为全局最大值）。
11. **【答案】C**  
    **【解析】** 网格迷宫中每走一步花费均为 1（无权图），BFS 第一次到达终点即为最少步数最短路径。
12. **【答案】B**  
    **【解析】** 动态规划求解的两大要素是最优子结构（子问题最优推导全局最优）与重叠子问题（记忆化化解重复计算）。
13. **【答案】B**  
    **【解析】** 严格递增子序列如 $\{1, 4, 5, 9\}$ 或 $\{1, 4, 5, 6\}$ 或 $\{3, 4, 5, 6\}$，最大长度为 4。
14. **【答案】B**  
    **【解析】** 加法原理：所有非空方案数 $= 7 + 10 + 1 = 18$ 种。
15. **【答案】B**  
    **【解析】** 邻接表存储下，DFS 每个顶点访问一次 $O(n)$，每条边被扫描一次 $O(m)$，总时间复杂度为 $O(n + m)$。

---
---

# Day 6 下午：初赛全真模拟策略与答题技巧（3小时）

## 第一部分：核心应试方法与各题型答题策略

### 1. 考场时间分配黄金法则（120分钟满分100分）

```
 [ 0 ~ 25 min ]  第一部分：单项选择题（15 题，共 30 分）─── 目标保底 26 分
 [ 25 ~ 70 min ] 第二部分：阅读程序题（3 大题，共 40 分）─── 目标攻下 30 分
 [ 70 ~ 110 min] 第三部分：完善程序题（2 大题，共 30 分）─── 目标拿下 24 分
 [110 ~ 120 min] 填涂答题卡复查、极端边界排查与代入验证
```

---

### 2. 三大题型解题技巧与提分秘籍

#### （1）单项选择题（15 题，每题 2 分）
*   **代入排除法**：将 4 个选项代入题干条件反推，只要发现 1 个反例立刻排除。
*   **极端值法 / 特殊值验证**：在排列组合或图论计算中，设 $n = 1, 2, 3$ 画出极小图验证选项公式。
*   **常识秒杀**：牢记前五天讲义中的人物（图灵、冯·诺依曼、香农）、单位换算（$1\text{ MB} = 1024^2\text{ B}$）、$n\_0 = n\_2 + 1$、握手定理（度数和 $= 2m$）等直接选出正确答案。

#### （2）阅读程序题（3 大题，共 40 分，含判断题与单选题）
*   **第一步：先扫一眼判断题**。判断题的设问往往在**剧透程序的功能边界**（例如：“当输入 $n \le 0$ 时会发生死循环”、“若数组元素完全相同时输出 0”等）。
*   **第二步：手写“变量跟踪表（人脑模拟 CPU）”**。
    *   在草稿纸上建立包含核心变量（如 `i`, `j`, `ans`, `sum`, `flag`）的表格。
    *   **代入小样例**（如 $n=3$ 或小数组 `[2, 1, 3]`）在纸上手算推演 2~3 轮，摸清代码的真实意图（如：这是在求逆序对、进制转换、质数筛还是最长子段和）。
*   **第三步：选择题利用特殊值逆推**。若完全看不懂代码逻辑，将选项中的具体数值代入程序逐步跟踪验证。

#### （3）完善程序题（2 大题，共 10 空，共 30 分）
*   **第一步：通读题干与注释，明确算法原型**。
    *   CSP-J 完善程序必定考查经典算法模板（二分查找、快速幂、01背包、广搜走迷宫、贪心排队）。
*   **第二步：关注代码结构对称性与边界条件**。
    *   循环边界：从 `0` 还是 `1` 开始？结束条件是 `< n` 还是 `<= n`？
    *   更新方向：正序还是逆序？（如背包一维优化必须逆序）。
*   **第三步：语法与变量名拼写排查**。
    *   检查选项中的变量名是否存在拼写错误、类型是否匹配（如指针传参还是变量传参）。

---

## 第二部分：下午全真模拟精选真题实战（1~15题）

1. 某键盘输入序列连续循环输入 `CapsLock`, `A`, `S`, `D`（每按一次 `CapsLock` 会切换大小写状态，初始为小写状态），则第 81 个被输入的字符是（ ）。【NOIP 2016 普及组】
   A. A
   B. S
   C. D
   D. a

2. 厨房制作三道菜，小明洗菜分别需要 10、20、10 分钟；爸爸切菜分别需要 10、10、20 分钟；妈妈炒菜分别需要 10、10、10 分钟。每道菜必须按照“洗菜 $\to$ 切菜 $\to$ 炒菜”的顺序进行，且每人同一时刻只能做一道菜的工序。做完这三道菜最少需要（ ）分钟。【NOIP 2016 普及组】
   A. 90
   B. 60
   C. 50
   D. 40

3. 已知 2017 年 10 月 1 日是星期日，则 1999 年 10 月 1 日是（ ）。【NOIP 2017 普及组】
   A. 星期三
   B. 星期日
   C. 星期五
   D. 星期二

4. 某键盘输入序列连续循环输入 `CapsLock`, `A`, `S`, `D`, `F`，初始为小写状态，则第 81 个被输入的字符是（ ）。【NOIP 2018 普及组】
   A. A
   B. S
   C. D
   D. a

5. 中国传统农历采用“干支纪年法”。已知公历 1949 年的天干地支纪年是（ ）。（天干：甲乙丙丁戊己庚辛壬癸；地支：子丑寅卯辰巳午未申酉戌亥；已知 1984 年为甲子年）【CSP-J 2020】
   A. 己酉
   B. 己亥
   C. 己丑
   D. 己卯

6. 设有一个 $4 \times 4$ 的网格迷宫，从左上角 $(1, 1)$ 出发走到右下角 $(4, 4)$，每次只能向下或向右走 1 步，且中间某个障碍格 $(2, 3)$ 无法通过，则不同的合法最短路径共有（ ）条。【模拟强化题】
   A. 20
   B. 14
   C. 12
   D. 16

7. 阅读下列 C++ 代码段，该程序的主要功能是（ ）。【模拟强化题】
   ```cpp
   int solve(int a[], int n) {
       int ans = a[0], cur = a[0];
       for (int i = 1; i < n; i++) {
           cur = max(a[i], cur + a[i]);
           ans = max(ans, cur);
       }
       return ans;
   }
   ```
   A. 求数组的最大值
   B. 求数组的最大连续子段和
   C. 求数组的最长上升子序列
   D. 求数组的前缀和

8. 在 CSP-J 认证考试中，下列关于编写程序规范的描述中，**错误**的是（ ）。【模拟强化题】
   A. 提交的源程序文件名必须与题目要求的英文名称完全一致（包括大小写）
   B. 若题目要求使用文件输入输出，代码中必须包含 `freopen` 相关语句
   C. 主函数 `main` 的返回值必须显式返回 0
   D. 比赛时可以在自己的代码中包含任何非官方支持的第三方扩展库

9. 阅读下列递归代码段：
   ```cpp
   int f(int n) {
       if (n <= 1) return 1;
       return f(n - 1) + 2 * f(n - 2);
   }
   ```
   调用 `f(5)` 的最终返回值是（ ）。【模拟强化题】
   A. 21
   B. 11
   C. 31
   D. 43

10. 某算法的递推方程为 $T(n) = 2T(n/2) + O(\sqrt{n})$，根据主定理，该算法的时间复杂度为（ ）。【模拟强化题】
    A. $O(n)$
    B. $O(n \log n)$
    C. $O(\sqrt{n})$
    D. $O(n^2)$

11. 现有 5 个不同大小的砝码，重量分别为 1g、2g、4g、8g、16g。若天平的一端只能放置待称物体，另一端放置砝码，则使用这 5 个砝码总共可以称出（ ）种不同重量的物体（不含 0g）。【模拟强化题】
    A. 30
    B. 31
    C. 32
    D. 16

12. 下列排序算法中，在最坏情况下空间复杂度为 $O(1)$ 且时间复杂度为 $O(n \log n)$ 的是（ ）。【模拟强化题】
    A. 归并排序
    B. 堆排序
    C. 快速排序
    D. 冒泡排序

13. 在二叉树中，前序遍历序列为 `ABDECF`，中序遍历序列为 `DBEACF`，则其后序遍历序列为（ ）。【模拟强化题】
    A. DEBFCA
    B. DEBAFC
    C. EDBFCA
    D. DEBCFA

14. 8 个人围坐成一张圆桌开会，其中甲和乙两人必须坐在一起，则所有不同的相对排座方案共有（ ）种（旋转后相同的排座视为同一种）。【模拟强化题】
    A. 5040
    B. 1440
    C. 720
    D. 2880

15. 在 32 位计算机系统中，执行语句 `cout << (1 << 31);` 输出的结果最可能表现为（ ）。【模拟强化题】
    A. $2147483648$
    B. $-2147483648$
    C. $0$
    D. 编译报错

---

## 第三部分：下午真题解析与答案速查

1. **【答案】C**  
   **【解析】** 输出字符序列按周期循环：第 1 周期输出小写 `a, s, d`；按下 CapsLock 后第 2 周期输出大写 `A, S, D`；整个循环周期包含 6 个输出字符（3 小写 + 3 大写），每个周期需按键 8 次。$81 \bmod 6 = 3$（或按击键周期 $81 \bmod 8 = 1$，第 81 次击键恰好按下并输出字母），推算对应输出为大写字符 `D`。
2. **【答案】C**  
   **【解析】** 流水线甘特图调度：  
   * 菜 1：洗(0~10) $\to$ 切(10~20) $\to$ 炒(20~30)；  
   * 菜 2：洗(10~30) $\to$ 切(30~40) $\to$ 炒(40~50)；  
   * 菜 3：洗(30~40) $\to$ 切(40~60)（爸爸在40~60切菜20分钟，妈妈在50~60炒菜2和菜3）。  
   做完三道菜的最少时间为 50 分钟。
3. **【答案】C**  
   **【解析】** 从 1999 年到 2017 年相隔 18 年。其中包含闰年（2000, 2004, 2008, 2012, 2016）共 5 个，平年 13 个。总天数偏移量 $= 13 \times 1 + 5 \times 2 = 23$ 天。$23 \bmod 7 = 2$ 天。星期日往前倒推 2 天为星期五。
4. **【答案】A**  
   **【解析】** 循环节：`CapsLock, A, S, D, F`（输出小写 `asdf`），再按 `CapsLock` 输出大写 `ASDF`，击键周期为 10（输出字符周期为 8）。$81 \bmod 10 = 1$，第 81 次击键恰好完成大小写切换后的第 1 个字母输入，对应大写字母 `A`。
5. **【答案】C**  
   **【解析】** 1984 年为甲子年（天干甲=1，地支子=1）。$1984 - 1949 = 35$ 年。  
   天干：$(1 - 35) \bmod 10 \equiv 6 \implies$ 己；  
   地支：$(1 - 35) \bmod 12 \equiv 2 \implies$ 丑。故 1949 年为己丑年。
6. **【答案】B**  
   **【解析】** 从 $(1, 1)$ 到 $(4, 4)$ 总路径数 $\binom{3+3}{3} = \binom{6}{3} = 20$ 条。经过障碍格 $(2, 3)$ 的路径数：从 $(1, 1)$ 到 $(2, 3)$ 有 $\binom{1+2}{1} = 3$ 条；从 $(2, 3)$ 到 $(4, 4)$ 有 $\binom{2+1}{1} = 3$ 条。经过障碍格的路径数 $= 3 \times 3 = 6$ 条。合法路径 $= 20 - 6 = 14$ 条。
7. **【答案】B**  
   **【解析】** 经典的 Kadane 算法，用于在线性时间 $O(n)$ 内求解最大连续子段和。
8. **【答案】D**  
   **【解析】** NOI/CSP 竞赛评测机只支持标准 C++ 库，绝对禁止使用任何非官方支持的第三方扩展库（如某些自定义图形库），否则会导致编译失败零分。
9. **【答案】A**  
   **【解析】** 手算递推：$f(0)=1, f(1)=1$；  
   $f(2) = f(1) + 2f(0) = 1 + 2 = 3$；  
   $f(3) = f(2) + 2f(1) = 3 + 2 = 5$；  
   $f(4) = f(3) + 2f(2) = 5 + 6 = 11$；  
   $f(5) = f(4) + 2f(3) = 11 + 10 = 21$。
10. **【答案】A**  
    **【解析】** 主定理参数：$a=2, b=2, d=0.5$。比较 $\log\_b a = \log\_2 2 = 1 > d (0.5)$，属于第一种情况，时间复杂度为 $O(n^{\log\_b a}) = O(n^1) = O(n)$。
11. **【答案】B**  
    **【解析】** 砝码重量成二进制倍增序列（$1, 2, 4, 8, 16$），每个砝码有选或不选两种状态，共有 $2^5 - 1 = 31$ 种不同组合，能精确表示 $1 \sim 31\text{ g}$ 的所有整数重量。
12. **【答案】B**  
    **【解析】** 堆排序在最坏情况下时间复杂度为 $O(n \log n)$，且为原地排序算法，空间复杂度为 $O(1)$（归并排序空间为 $O(n)$，快排最坏时间为 $O(n^2)$）。
13. **【答案】A**  
    **【解析】** 前序 A 为根，中序切分为左子树 DBE、右子树 CF。左子树前序 BDE，中序 DBE $\to$ 后序为 DEB；右子树前序 CF，中序 CF $\to$ 后序为 FC。后序遍历拼接为 `DEBFCA`。
14. **【答案】B**  
    **【解析】** 圆排列公式：$n$ 个不同元素围成一圈的排列数为 $(n - 1)!$。将甲乙捆绑为 1 个整体，与其余 6 人共 7 个对象进行圆排列，方案数为 $(7 - 1)! = 6! = 720$；甲乙内部有 $2! = 2$ 种顺序。总排座数 $= 720 \times 2 = 1440$ 种。
15. **【答案】B**  
    **【解析】** 字面量 `1` 默认为 32 位有符号整型 `int`，最高位为符号位。左移 31 位后符号位变为 1，其余各位全为 0，代表 32 位补码有符号整数的最小值 $-2^{31} = -2147483648$。

---
---

# 🎓 6天 CSP-J 初赛集训结语与终极通关锦囊

1. **稳拿基础分（60分）**：计算机常识、二进制转换、ASCII 码、栈队列性质、二叉树性质（$n\_0 = n\_2 + 1$）与握手定理，考场上一分不丢！
2. **死磕中档分（25分）**：排列组合（捆绑/插空/隔板）、排序算法稳定性对比、表达式转换、递归变量追踪表，细致草稿手推！
3. **沉着冲高分（15分）**：阅读程序大题遇到复杂循环莫慌，代入 $n=2,3$ 小样例找寻数学本质；完善程序牢记典型模板边界代入法！祝所有学员初赛高分晋级！

CSP-J 第一轮（初赛）通关集训 · 第六天

Day 6 上午：搜索算法（DFS/BFS）、回溯与动态规划入门（3小时）

第一部分：核心知识精讲与考点速记

1. DFS（深度优先搜索）与回溯法核心机制

核心思想：“不撞南墙不回头”，沿着一条路径尽可能深地搜索，遇到死胡同则回溯（Backtracking）返回上一层继续探索。
底层支撑：依赖系统调用栈（递归实现）或手写显式栈。
三大经典要素与标准模板： cpp void dfs(int step, 状态参数) { if (到达目标状态 / 满足终止条件) { 记录最优解或方案数累加; return; } for (int i = 0; i < 所有可行分支; i++) { if (满足剪枝条件 / 未被访问) { 标记当前状态已访问（vis[i] = true）; // 做出选择 dfs(step + 1, 更新后的状态); // 递归深入标记当前状态未访问（vis[i] = false）; // 【回溯核心：撤销选择】 } } }
剪枝优化思想：
- 可行性剪枝：若当前状态已经非法或不可能到达终点，提前 return。
- 最优性剪枝：若当前花费已经超过已知最优解，提前 return。

2. BFS（广度优先搜索）与泛洪算法（Flood Fill）

核心思想：“层层扩散，由近及远”，从起点开始逐层向外扫描所有相邻节点。
底层支撑：必须依赖队列（Queue，先进先出 FIFO）。
黄金应用法则（初赛常考性质）：
- 在边权均为 1（无权图）的图中，BFS 第一次遍历到目标节点时所经过的步数，必定是全局最短路径（最少步数）。
DFS vs BFS 综合特性对比表：

特性维度	深度优先搜索（DFS）	广度优先搜索（BFS）
底层数据结构	栈（Stack / 递归栈帧）	队列（Queue）
空间复杂度	$O(h)$（$h$ 为树/递归最大深度，空间省）	$O(w)$（$w$ 为最大宽度，空间随层数膨胀）
核心适用场景	方案总数、排列组合生成、连通性判断、棋盘回溯	无权图最短路径、最少步数、连通块染色（Flood Fill）

3. 动态规划（DP）基础与背包模型

动态规划三大核心特征：
1. 最优子结构：大问题的最优解可以由子问题的最优解推导得出。
2. 重叠子问题：在递归求解过程中，相同的子问题会被反复计算多次（DP 通过表格记忆化避免重复计算）。
3. 无后效性：一旦某个阶段的状态确定，后续决策只取决于当前状态，不受“如何到达该状态”的历史过程影响。
经典模型 1：0/1 背包问题（初赛必背转移方程）：
- 问题描述：$N$ 件物品，背包容量为 $V$。第 $i$ 件物品体积为 $w[i]$，价值为 $v[i]$，每件物品只能选 0 件或 1 件。
- 二维状态转移：$dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])$
- 一维滚动数组空间优化： $$dp[j] = \max(dp[j], dp[j - w[i]] + v[i]) \quad \text{（容量 } j \text{ 必须严格从 } V \text{ 到 } w[i] \text{ 逆序遍历！）}$$
经典模型 2：最长上升子序列（LIS）：
- 状态定义：$dp[i]$ 表示以 $a[i]$ 结尾的最长上升子序列长度。
- 转移方程：$dp[i] = \max_{j < i, a[j] < a[i]}(dp[j]) + 1$（基础时间复杂度 $O(n^2)$）。
数列取模的周期性分析（初赛高频技巧）：
- 形如斐波那契数列等线性递推数列在模 $m$ 意义下必然存在周期性（皮萨诺周期 Pisano Period）。通过手算前几项找出循环节长度 $T$，即可将大指数 $N$ 转化为 $N \bmod T$ 极速求解。

第二部分：上午精选真题实战（1~15题）

在解决问题时，先选择一种可能的方式向前搜索，一旦发现原先选择并不优或达不到目标就退回一步重新选择，这种算法思想被称为（）。【NOIP 2011 普及组】 A. 回溯法 B. 枚举法 C. 动态规划 D. 贪心法
广度优先搜索（BFS）算法在遍历图或状态空间时，底层必须使用的数据结构是（）。【NOIP 2011 普及组】 A. 单链表 B. 队列 C. 栈 D. 散列表（哈希表）
对一个无向图进行深度优先遍历（DFS），从顶点 $a$ 出发，下列遍历序列中可能合法的是（）。【NOIP 2015 普及组】 A. $a, b, e, c, d, f$ B. $a, c, f, e, b, d$ C. $a, e, b, c, f, d$ D. $a, b, e, d, f, c$
在无向图以顶点 $A_0$ 为起点进行深度优先搜索遍历，下列顶点序列中绝对不可能出现的是（）。【NOIP 2013 普及组】 A. $A_0, A_1, A_2, A_3$（已知 $A_1$ 与 $A_2$ 无直接连边） B. $A_0, A_1, A_3, A_2$ C. $A_0, A_2, A_1, A_3$ D. $A_0, A_3, A_1, A_2$
在无向连通图中以顶点 $a$ 为起点进行 DFS 遍历，根据分支搜索对称性，可能最后被遍历到的不同顶点个数有（）个。【CSP-J 2021】 A. 1 B. 2 C. 3 D. 4
4 个人在黑夜中需要穿过一座狭窄的独木桥，他们只有一个手电筒，且桥上每次最多只能同时由 2 人通过。4 人单程过桥所需时间分别为 1、2、5、10 分钟。过桥时由于光线限制，速度必须以较慢者为准，手电筒不能丢掷而必须有人送回。所有人全部安全过桥的最短时间是（）分钟。【CSP-J 2021】 A. 14 B. 15 C. 16 D. 17
下列关于各类数据结构及其典型应用的表述中，不恰当的是（）。【CSP-J 2022】 A. 深度优先搜索（DFS）通常借助栈或系统递归栈来实现 B. 栈的特性是后进先出，队列的特性是先进先出 C. 广度优先搜索（BFS）通常借助队列来实现 D. 仅使用两个栈在逻辑上绝对无法模拟出一个队列的功能
已知斐波那契数列定义为 $f[0] = 0, f[1] = 1, f[n] = f[n-1] + f[n-2]$（$n \ge 2$）。计算数列各项对 7 取模后的值，则 $f[2025] \bmod 7$ 的最终结果是（）。【CSP-J 2025】 A. 3 B. 4 C. 5 D. 6
在求解 0/1 背包问题时，若使用一维滚动数组 dp[j] 优化空间复杂度，则背包容量 j 的循环遍历方向必须是（）。【模拟强化题】 A. 从 $0$ 到 $V$ 顺序遍历 B. 从 $V$ 到 $w[i]$ 逆序遍历 C. 先正序再逆序 D. 任意顺序均可
小胖跑步锻炼，计划在周一到周日安排运动。已知运动方案一每次跑步 3 公里消耗 300 千卡，方案二每次跑步 5 公里消耗 600 千卡。受体能限制，周一到周四最多跑 4 次方案一，周五到周日最多跑 3 次方案二，且一周总跑步里程不能超过 21 公里。小胖一周最多能够消耗的热量是（）千卡。【CSP-J 2019】 A. 3000 B. 2500 C. 2400 D. 2520
在一个网格迷宫中寻找从起点到终点的最短移动步数，最适宜采用的算法策略是（）。【模拟强化题】 A. 贪心算法 B. 深度优先搜索（DFS） C. 广度优先搜索（BFS） D. 分治算法
动态规划算法能够有效解决问题的两个最基本前提特征是（）。【模拟强化题】 A. 贪心选择性质与独立子问题 B. 最优子结构与重叠子问题 C. 递归定义与快速排序划分 D. 状态空间极大且无环
设有序列 ${3, 1, 4, 1, 5, 9, 2, 6, 5}$，该序列的最长严格上升子序列（LIS）的长度为（）。【模拟强化题】 A. 3 B. 4 C. 5 D. 6
有 8 个互不相同的活动，每个活动有确定的起止时间区间，现需在互不冲突的前提下选择活动。若选 1 个有 7 种方案，选 2 个有 10 种方案，选 3 个有 1 种方案，则所有合法的非空选择方案数总共有（）种。【CSP-J 2023】 A. 31 B. 18 C. 21 D. 33
使用 DFS 遍历包含 $n$ 个顶点、$m$ 条边的图，若采用邻接表存储，其时间复杂度为（）。【模拟强化题】 A. $O(n^2)$ B. $O(n + m)$ C. $O(m \log n)$ D. $O(n \times m)$

第三部分：上午真题解析与答案速查

【答案】A
【解析】 遇到死胡同退回一步重新试探并撤销选择，这是回溯法（Backtracking）的标准定义。
【答案】B
【解析】 BFS 依据层序由近及远扩散，必须依赖队列（Queue）维护待扩展的状态。
【答案】D
【解析】 根据 DFS 规则，从 $a$ 出发，沿邻接边深入访问，合法序列为 $a, b, e, d, f, c$。
【答案】A
【解析】 A 选项中 $A_1$ 与 $A_2$ 之间没有直接连边，DFS 在访问完 $A_1$ 后若无回溯无法突跳到不相邻的 $A_2$ 节点，故 A 序列不可能。
【答案】B
【解析】 从 $a$ 点出发深入图分支，由搜索分支的对称性，最终叶子端点有 2 种可能。
【答案】B
【解析】 经典过河贪心策略：让最快的两人先过送手电，或者让最快的两人送手电掩护最慢的两人一起过。最优步骤：
1 和 2 过去（用时 2 分钟）；
1 带手电回来（用时 1 分钟）；
5 和 10 两个最慢的一起过去（用时 10 分钟）；
2 带手电回来（用时 2 分钟）；
1 和 2 再次一起过去（用时 2 分钟）。
总时间 $= 2 + 1 + 10 + 2 + 2 = 15$ 分钟。
【答案】D
【解析】 两个栈完全可以模拟实现一个队列（一个栈负责入队 push，另一个栈负责出队 pop，当出队栈为空时将入队栈全部元素倒入出队栈即可完成 FIFO）。
【答案】D
【解析】 斐波那契数列模 7 的余数序列：$0, 1, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1 \dots$
循环节长度为 $16$（皮萨诺周期）。$2025 \bmod 16 = 9$，对应余数序列第 9 项（下标 9）为 $6$。
【答案】B
【解析】 0/1 背包每个物品只能选一次。逆序遍历容量 $j$ 保证了计算 $dp[j]$ 时所用到的子状态 $dp[j - w[i]]$ 来自上一轮（即尚未放入当前物品 $i$ 的状态），若正序遍历则会退化为完全背包（物品被重复多次选取）。
【答案】C
【解析】 设方案一执行 $x$ 天（$x \le 4$），方案二执行 $y$ 天（$y \le 3$），满足约束 $3x + 5y \le 21$。目标最大化消耗热量 $300x + 600y$。枚举可行整数解：当 $y=3$ 时，$3x \le 21 - 15 = 6 \implies x \le 2$，取 $x=2, y=3$，总热量 $= 300 \times 2 + 600 \times 3 = 600 + 1800 = 2400$ 千卡（为全局最大值）。
【答案】C
【解析】 网格迷宫中每走一步花费均为 1（无权图），BFS 第一次到达终点即为最少步数最短路径。
【答案】B
【解析】 动态规划求解的两大要素是最优子结构（子问题最优推导全局最优）与重叠子问题（记忆化化解重复计算）。
【答案】B
【解析】 严格递增子序列如 ${1, 4, 5, 9}$ 或 ${1, 4, 5, 6}$ 或 ${3, 4, 5, 6}$，最大长度为 4。
【答案】B
【解析】 加法原理：所有非空方案数 $= 7 + 10 + 1 = 18$ 种。
【答案】B
【解析】 邻接表存储下，DFS 每个顶点访问一次 $O(n)$，每条边被扫描一次 $O(m)$，总时间复杂度为 $O(n + m)$。

---

Day 6 下午：初赛全真模拟策略与答题技巧（3小时）

第一部分：核心应试方法与各题型答题策略

1. 考场时间分配黄金法则（120分钟满分100分）

 [ 0 ~ 25 min ]  第一部分：单项选择题（15 题，共 30 分）─── 目标保底 26 分
 [ 25 ~ 70 min ] 第二部分：阅读程序题（3 大题，共 40 分）─── 目标攻下 30 分
 [ 70 ~ 110 min] 第三部分：完善程序题（2 大题，共 30 分）─── 目标拿下 24 分
 [110 ~ 120 min] 填涂答题卡复查、极端边界排查与代入验证

2. 三大题型解题技巧与提分秘籍

（1）单项选择题（15 题，每题 2 分）

代入排除法：将 4 个选项代入题干条件反推，只要发现 1 个反例立刻排除。
极端值法 / 特殊值验证：在排列组合或图论计算中，设 $n = 1, 2, 3$ 画出极小图验证选项公式。
常识秒杀：牢记前五天讲义中的人物（图灵、冯·诺依曼、香农）、单位换算（$1\text{ MB} = 1024^2\text{ B}$）、$n_0 = n_2 + 1$、握手定理（度数和 $= 2m$）等直接选出正确答案。

（2）阅读程序题（3 大题，共 40 分，含判断题与单选题）

第一步：先扫一眼判断题。判断题的设问往往在剧透程序的功能边界（例如：“当输入 $n \le 0$ 时会发生死循环”、“若数组元素完全相同时输出 0”等）。
第二步：手写“变量跟踪表（人脑模拟 CPU）”。
- 在草稿纸上建立包含核心变量（如 i, j, ans, sum, flag）的表格。
- 代入小样例（如 $n=3$ 或小数组 [2, 1, 3]）在纸上手算推演 2~3 轮，摸清代码的真实意图（如：这是在求逆序对、进制转换、质数筛还是最长子段和）。
第三步：选择题利用特殊值逆推。若完全看不懂代码逻辑，将选项中的具体数值代入程序逐步跟踪验证。

（3）完善程序题（2 大题，共 10 空，共 30 分）

第一步：通读题干与注释，明确算法原型。
- CSP-J 完善程序必定考查经典算法模板（二分查找、快速幂、01背包、广搜走迷宫、贪心排队）。
第二步：关注代码结构对称性与边界条件。
- 循环边界：从 0 还是 1 开始？结束条件是 < n 还是 <= n？
- 更新方向：正序还是逆序？（如背包一维优化必须逆序）。
第三步：语法与变量名拼写排查。
- 检查选项中的变量名是否存在拼写错误、类型是否匹配（如指针传参还是变量传参）。

第二部分：下午全真模拟精选真题实战（1~15题）

某键盘输入序列连续循环输入 CapsLock, A, S, D（每按一次 CapsLock 会切换大小写状态，初始为小写状态），则第 81 个被输入的字符是（）。【NOIP 2016 普及组】 A. A B. S C. D D. a
厨房制作三道菜，小明洗菜分别需要 10、20、10 分钟；爸爸切菜分别需要 10、10、20 分钟；妈妈炒菜分别需要 10、10、10 分钟。每道菜必须按照“洗菜 $\to$ 切菜 $\to$ 炒菜”的顺序进行，且每人同一时刻只能做一道菜的工序。做完这三道菜最少需要（）分钟。【NOIP 2016 普及组】 A. 90 B. 60 C. 50 D. 40
已知 2017 年 10 月 1 日是星期日，则 1999 年 10 月 1 日是（）。【NOIP 2017 普及组】 A. 星期三 B. 星期日 C. 星期五 D. 星期二
某键盘输入序列连续循环输入 CapsLock, A, S, D, F，初始为小写状态，则第 81 个被输入的字符是（）。【NOIP 2018 普及组】 A. A B. S C. D D. a
中国传统农历采用“干支纪年法”。已知公历 1949 年的天干地支纪年是（）。（天干：甲乙丙丁戊己庚辛壬癸；地支：子丑寅卯辰巳午未申酉戌亥；已知 1984 年为甲子年）【CSP-J 2020】 A. 己酉 B. 己亥 C. 己丑 D. 己卯
设有一个 $4 \times 4$ 的网格迷宫，从左上角 $(1, 1)$ 出发走到右下角 $(4, 4)$，每次只能向下或向右走 1 步，且中间某个障碍格 $(2, 3)$ 无法通过，则不同的合法最短路径共有（）条。【模拟强化题】 A. 20 B. 14 C. 12 D. 16
阅读下列 C++ 代码段，该程序的主要功能是（）。【模拟强化题】 cpp int solve(int a[], int n) { int ans = a[0], cur = a[0]; for (int i = 1; i < n; i++) { cur = max(a[i], cur + a[i]); ans = max(ans, cur); } return ans; } A. 求数组的最大值 B. 求数组的最大连续子段和 C. 求数组的最长上升子序列 D. 求数组的前缀和
在 CSP-J 认证考试中，下列关于编写程序规范的描述中，错误的是（）。【模拟强化题】 A. 提交的源程序文件名必须与题目要求的英文名称完全一致（包括大小写） B. 若题目要求使用文件输入输出，代码中必须包含 freopen 相关语句 C. 主函数 main 的返回值必须显式返回 0 D. 比赛时可以在自己的代码中包含任何非官方支持的第三方扩展库
阅读下列递归代码段： cpp int f(int n) { if (n <= 1) return 1; return f(n - 1) + 2 * f(n - 2); } 调用 f(5) 的最终返回值是（）。【模拟强化题】 A. 21 B. 11 C. 31 D. 43
某算法的递推方程为 $T(n) = 2T(n/2) + O(\sqrt{n})$，根据主定理，该算法的时间复杂度为（）。【模拟强化题】 A. $O(n)$ B. $O(n \log n)$ C. $O(\sqrt{n})$ D. $O(n^2)$
现有 5 个不同大小的砝码，重量分别为 1g、2g、4g、8g、16g。若天平的一端只能放置待称物体，另一端放置砝码，则使用这 5 个砝码总共可以称出（）种不同重量的物体（不含 0g）。【模拟强化题】 A. 30 B. 31 C. 32 D. 16
下列排序算法中，在最坏情况下空间复杂度为 $O(1)$ 且时间复杂度为 $O(n \log n)$ 的是（）。【模拟强化题】 A. 归并排序 B. 堆排序 C. 快速排序 D. 冒泡排序
在二叉树中，前序遍历序列为 ABDECF，中序遍历序列为 DBEACF，则其后序遍历序列为（）。【模拟强化题】 A. DEBFCA B. DEBAFC C. EDBFCA D. DEBCFA
8 个人围坐成一张圆桌开会，其中甲和乙两人必须坐在一起，则所有不同的相对排座方案共有（）种（旋转后相同的排座视为同一种）。【模拟强化题】 A. 5040 B. 1440 C. 720 D. 2880
在 32 位计算机系统中，执行语句 cout << (1 << 31); 输出的结果最可能表现为（）。【模拟强化题】 A. $2147483648$ B. $-2147483648$ C. $0$ D. 编译报错

第三部分：下午真题解析与答案速查

【答案】C
【解析】 输出字符序列按周期循环：第 1 周期输出小写 a, s, d；按下 CapsLock 后第 2 周期输出大写 A, S, D；整个循环周期包含 6 个输出字符（3 小写 + 3 大写），每个周期需按键 8 次。$81 \bmod 6 = 3$（或按击键周期 $81 \bmod 8 = 1$，第 81 次击键恰好按下并输出字母），推算对应输出为大写字符 D。
【答案】C
【解析】 流水线甘特图调度：
菜 1：洗(0~10) $\to$ 切(10~20) $\to$ 炒(20~30)；
菜 2：洗(10~30) $\to$ 切(30~40) $\to$ 炒(40~50)；
菜 3：洗(30~40) $\to$ 切(40~60)（爸爸在40~60切菜20分钟，妈妈在50~60炒菜2和菜3）。
做完三道菜的最少时间为 50 分钟。
【答案】C
【解析】 从 1999 年到 2017 年相隔 18 年。其中包含闰年（2000, 2004, 2008, 2012, 2016）共 5 个，平年 13 个。总天数偏移量 $= 13 \times 1 + 5 \times 2 = 23$ 天。$23 \bmod 7 = 2$ 天。星期日往前倒推 2 天为星期五。
【答案】A
【解析】 循环节：CapsLock, A, S, D, F（输出小写 asdf），再按 CapsLock 输出大写 ASDF，击键周期为 10（输出字符周期为 8）。$81 \bmod 10 = 1$，第 81 次击键恰好完成大小写切换后的第 1 个字母输入，对应大写字母 A。
【答案】C
【解析】 1984 年为甲子年（天干甲=1，地支子=1）。$1984 - 1949 = 35$ 年。
天干：$(1 - 35) \bmod 10 \equiv 6 \implies$ 己；
地支：$(1 - 35) \bmod 12 \equiv 2 \implies$ 丑。故 1949 年为己丑年。
【答案】B
【解析】 从 $(1, 1)$ 到 $(4, 4)$ 总路径数 $\binom{3+3}{3} = \binom{6}{3} = 20$ 条。经过障碍格 $(2, 3)$ 的路径数：从 $(1, 1)$ 到 $(2, 3)$ 有 $\binom{1+2}{1} = 3$ 条；从 $(2, 3)$ 到 $(4, 4)$ 有 $\binom{2+1}{1} = 3$ 条。经过障碍格的路径数 $= 3 \times 3 = 6$ 条。合法路径 $= 20 - 6 = 14$ 条。
【答案】B
【解析】 经典的 Kadane 算法，用于在线性时间 $O(n)$ 内求解最大连续子段和。
【答案】D
【解析】 NOI/CSP 竞赛评测机只支持标准 C++ 库，绝对禁止使用任何非官方支持的第三方扩展库（如某些自定义图形库），否则会导致编译失败零分。
【答案】A
【解析】 手算递推：$f(0)=1, f(1)=1$；
$f(2) = f(1) + 2f(0) = 1 + 2 = 3$；
$f(3) = f(2) + 2f(1) = 3 + 2 = 5$；
$f(4) = f(3) + 2f(2) = 5 + 6 = 11$；
$f(5) = f(4) + 2f(3) = 11 + 10 = 21$。
【答案】A
【解析】 主定理参数：$a=2, b=2, d=0.5$。比较 $\log_b a = \log_2 2 = 1 > d (0.5)$，属于第一种情况，时间复杂度为 $O(n^{\log_b a}) = O(n^1) = O(n)$。
【答案】B
【解析】 砝码重量成二进制倍增序列（$1, 2, 4, 8, 16$），每个砝码有选或不选两种状态，共有 $2^5 - 1 = 31$ 种不同组合，能精确表示 $1 \sim 31\text{ g}$ 的所有整数重量。
【答案】B
【解析】 堆排序在最坏情况下时间复杂度为 $O(n \log n)$，且为原地排序算法，空间复杂度为 $O(1)$（归并排序空间为 $O(n)$，快排最坏时间为 $O(n^2)$）。
【答案】A
【解析】 前序 A 为根，中序切分为左子树 DBE、右子树 CF。左子树前序 BDE，中序 DBE $\to$ 后序为 DEB；右子树前序 CF，中序 CF $\to$ 后序为 FC。后序遍历拼接为 DEBFCA。
【答案】B
【解析】 圆排列公式：$n$ 个不同元素围成一圈的排列数为 $(n - 1)!$。将甲乙捆绑为 1 个整体，与其余 6 人共 7 个对象进行圆排列，方案数为 $(7 - 1)! = 6! = 720$；甲乙内部有 $2! = 2$ 种顺序。总排座数 $= 720 \times 2 = 1440$ 种。
【答案】B
【解析】 字面量 1 默认为 32 位有符号整型 int，最高位为符号位。左移 31 位后符号位变为 1，其余各位全为 0，代表 32 位补码有符号整数的最小值 $-2^{31} = -2147483648$。

---

🎓 6天 CSP-J 初赛集训结语与终极通关锦囊

稳拿基础分（60分）：计算机常识、二进制转换、ASCII 码、栈队列性质、二叉树性质（$n_0 = n_2 + 1$）与握手定理，考场上一分不丢！
死磕中档分（25分）：排列组合（捆绑/插空/隔板）、排序算法稳定性对比、表达式转换、递归变量追踪表，细致草稿手推！
沉着冲高分（15分）：阅读程序大题遇到复杂循环莫慌，代入 $n=2,3$ 小样例找寻数学本质；完善程序牢记典型模板边界代入法！祝所有学员初赛高分晋级！

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