---

你预计要花多久能突击学完呢？

从你目前的 GESP 4-6 级 水平跨越到能够稳拿这次自招考试高分，整体所需的纯有效学习与刷题时间大约在 50～70 小时。

因为考试考点范围已经高度确定（明确了考哪些算法和题型），不需要像准备完整竞赛那样地毯式刷题，突击效率会非常高。具体折算到自然时间，取决于你的排期强度：

---

一、 两种常见突击节奏

1. 高强度集中突击（寒假 / 假期集中模式）：约 3～4 周

• 投入时间：每天 2.5～3 小时，每周 15～18 小时。
• 适用场景：利用寒假或周末集中发力，知识点不脱节，短期记忆和手感最强。

2. 平稳推进突击（学期内周末模式）：约 7～8 周（约 2 个月）

• 投入时间：工作日每天 30~45 分钟（复习概念/看模板），周末半天集中刷题 4~5 小时，每周 7~9 小时。
• 适用场景：校内课业压力较大，只能利用零碎时间和周末攻坚。

---

二、 50~70 小时的具体时间切片分配

突击模块	包含考点	预估耗时	学习与突击核心任务
模块 1：知识盲区攻坚（最硬骨头）	并查集、LIS、最小生成树 (Kruskal/Prim)	18～22 小时	彻底理解原理，背熟核心模板代码，能在纸上闭卷手写出核心逻辑（约占 40% 分数）。
模块 2：数据结构与进阶基础补齐	链表、优先队列 (堆)、格雷码、哈希冲突	10～14 小时	搞懂堆的数组上下滤调整、格雷码转换公式、哈希探测手算规则。
模块 3：初赛手推与阅读程序专练	贪心枚举、归并排序、MST 运行手推	12～15 小时	练习用草稿纸快速模拟循环、递归展开、双指针合并，训练“不把代码丢进电脑也能手算出输出”的能力。
模块 4：选择题常识与数学速成	排列组合、运算符优先级、排序稳定性与复杂度对比	6～8 小时	整理表格死记硬背性质（如哪些排序稳定、复杂度最好最坏），刷 20~30 道排列组合经典题。
模块 5：全真模拟与限时控时	10单选 + 3阅读 + 1完型		严格限时 60 分钟做 4~6 套模拟卷，练出做题节奏，消灭粗心失分。

---

三、 突击最高效的三条“捷径”

1. “背模板”优于“死做黑题”： 这次考试是笔试而非上机打代码（机试）。完善程序考的并查集和 LIS 都是教科书级经典板子，只要把标准模板的变量命名和逻辑刻在脑子里，完型填空基本是送分题。
2. 重在“手算模拟”而不是“环境调试”： 阅读程序题考的是人脑单步调试能力。平时练习时，多在草稿纸上画图（画树、画数组变化、画指针移动），适应脱离电脑 IDE 的答题习惯。
3. 优先吃透历年 CSP-J/S 初赛第 2、3 大题： 直接拿近 5 年的全国初赛真题做专项切片训练，题型套路和出题人思维与该自招卷完全一致。

给我简单讲解“归并排序求逆序对”

归并排序求逆序对是分治思想（Divide and Conquer）最经典的实战应用，也是 CSP-J/S、NOIP 初赛代码填空和复赛算法题的必考模板。

---

一、什么是逆序对？

在数组 $A$ 中，如果存在一对下标满足：

$$\mathbf{i < j \quad \text{且} \quad A[i] > A[j]}$$

则称 $(A[i], A[j])$ 是一个逆序对。

• 物理本质：一个序列的逆序对数量，等于冒泡排序将其排成升序所需的相邻元素交换总次数。
• 暴力做法：双重循环枚举 $i, j$，耗时 $O(n^2)$，当 $n=10^5$ 时直接超时（TLE）。
• 归并排序法：在排序合并（Merge）的同时顺手统计，时间复杂度优化到 $O(n \log n)$。

---

二、核心计算原理（为什么归并可以顺手求？）

在归并排序的“分治”过程中，任意一个逆序对 $(A[i], A[j])$ 只可能落在三种情况中：

1. 完全在左半区间：递归调用左半边解决；
2. 完全在右半区间：递归调用右半边解决；
3. 横跨左右区间（$i$ 在左，$j$ 在右）：在双指针 merge 时一次性批量计算！

跨区间计算的关键逻辑：

假设左半区 [L, mid] 和右半区 [mid+1, R] 都已经排好升序：

• 设指针 $i$ 遍历左区，指针 $j$ 遍历右区；

• 若 $A[i] \le A[j]$：正常取出 $A[i]$，不构成逆序对，$i{++}$；

• 若 $A[i] > A[j]$： 因为左半区本身是有序的，既然 $A[i] > A[j]$，那么左区中从 $i$ 到 $mid$ 的所有元素（$A[i], A[i+1], \dots, A[mid]$）都必然大于 $A[j]$！

  $$\text{本步新增逆序对数} = \mathbf{mid - i + 1}$$

---

三、手算演练（一图看懂）

合并以下两个已经排好序的子区间（mid = 2）：

• 左半区：[ 2, 5, 8 ]（下标 $i$ 从 0 到 2）
• 右半区：[ 3, 4, 7 ]（下标 $j$ 从 3 到 5）

第1步: A[i]=2 <= A[j]=3  -> 取出 2, 逆序对 +0
第2步: A[i]=5 >  A[j]=3  -> 取出 3, 逆序对 += (mid - i + 1) = (2 - 1 + 1) = 2对!
                           (即 (5,3) 和 (8,3) 这一对批处理全数拿到)
第3步: A[i]=5 >  A[j]=4  -> 取出 4, 逆序对 += (2 - 1 + 1) = 2对!
                           (即 (5,4) 和 (8,4))
第4步: A[i]=5 <= A[j]=7  -> 取出 5, 逆序对 +0
第5步: A[i]=8 >  A[j]=7  -> 取出 7, 逆序对 += (2 - 2 + 1) = 1对!
                           (即 (8,7))
第6步: 左边剩余 8 全部放入。

总计产生跨区间逆序对 = 0 + 2 + 2 + 0 + 1 = 5 对。

---

四、高频踩坑点（考场失分雷区）

1. 必须开 long long（致命易错）：
   • 当数组长度 $n = 10^5$ 时，逆序对数量最多可达：$$\frac{n(n-1)}{2} \approx \frac{10^{10}}{2} = 5 \times 10^9 $$
   • 32 位整型 int 上限约为 $2.14 \times 10^9$，必定爆 int！统计变量 ans 必须声明为 long long。
2. 比较条件必须是 $A[i] \le A[j]$（必须带等号）：
   • 逆序对要求严格大于（$A[i] > A[j]$）。
   • 若两数相等（$A[i] == A[j]$），不构成逆序对，必须优先放左区元素（$i{++}$），否则会误算逆序对且破坏算法稳定性。

---

五、标准 C++ 模板（背诵级精简代码）

#include <iostream>
using namespace std;

const int MAXN = 100005;
int a[MAXN], temp[MAXN];
long long ans = 0; // 必须 long long

void merge_sort(int L, int R) {
    if (L >= R) return;
    int mid = (L + R) / 2;
    merge_sort(L, mid);     // 递归求左半区
    merge_sort(mid + 1, R); // 递归求右半区

    // 双指针合并与统计
    int i = L, j = mid + 1, k = L;
    while (i <= mid && j <= R) {
        if (a[i] <= a[j]) { // 相等时优先放左边
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
            ans += (mid - i + 1); // 核心统计语句！
        }
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= R) temp[k++] = a[j++];
    for (int p = L; p <= R; p++) a[p] = temp[p];
}

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

给我简单讲Kruskal、Prim以及两者的区别

最小生成树（Minimum Spanning Tree, MST）是图论中的绝对核心考点。两者的终极目标完全一致：在一个包含 $V$ 个顶点的连通无向带权图中，挑出 $V-1$ 条边，使得所有顶点连通且总边权和最小。

它们的区别可以用六个字概括：Kruskal 贪边，Prim 贪点。

---

一、Kruskal 算法（克鲁斯卡尔 ——“加边法”）

1. 核心思想（全局贪心选边）

先把图里所有边拆下来，按权值从小到大排好队。每次挑一条当前权值最小的边：

• 若加上这条边不会形成环（即边的两个端点原本不连通），就把它收编进生成树；
• 若加上会成环，则直接扔掉；
• 重复此过程，直到选满了 $V-1$ 条边为止。

2. 底层武器：并查集（DSU）

• 如何高效判环？ 用并查集维护连通块。
• 检查一条边的两端点 $u, v$：若 find(u) == find(v)，说明两点早已连通，加上必成环，舍弃；否则 merge(u, v)，计数器加 1。

3. 复杂度

• 边排序需要 $O(E \log E)$，并查集操作近乎 $O(1)$。
• 总时间复杂度：$O(E \log E)$（即 $O(E \log V)$），仅与边数 $E$ 强相关。

---

二、Prim 算法（普里姆 ——“加点法”）

1. 核心思想（滚雪球扩充点集）

从任意一个起点开始，维护一个**“已经在树里的点集 $S$”**：

1. 初始时，集合 $S$ 只有起点 1 个点；
2. 每次在“尚未入树的所有点”中，寻找一个距离集合 $S$ 最近的点（即连接已选点集与未选点集的权重最小的边）；
3. 把该点加入 $S$，并用它的所有出边更新其它未入树点到 $S$ 的最短距离；
4. 重复此过程，直到所有 $V$ 个点都被收进 $S$。

灵感直通车：Prim 的扩张过程和单源最短路 Dijkstra 算法几乎完全一致！唯一区别是更新数组的定义：Dijkstra 存的是“到起点的累加距离”，Prim 存的是“到当前生成树点集的单边最近距离”。

2. 复杂度

• 朴素 Prim（基于邻接矩阵 + 暴力循环）：$O(V^2)$，与边数无关。
• 堆优化 Prim（基于邻接表 + 优先队列）：$O(E \log V)$。

---

三、两者的核心区别与做题选型对照表

维度	Kruskal（克鲁斯卡尔）	Prim（普里姆）
贪心对象	边（每次挑全局权值最小的边）	点（每次挑离当前树最近的点）
核心数据结构	并查集 + 边结构体数组排序	优先队列（小根堆） 或 距离数组
中间状态	中途是由多棵小树构成的森林，最后合为一体	中途始终是一棵完整生长的树，像滚雪球
最适用的图	稀疏图（边较少，$E \ll V^2$）	稠密图（边极多，$E \approx V^2$ 时用朴素版）
时间复杂度	永远是 $O(E \log E)$	朴素版 $O(V^2)$，堆优化版 $O(E \log V)$
代码好写程度	极高（结构体排序 + 4 行并查集，初学者首选）	稍长（需类似 Dijkstra 进行松弛和建图）

---

四、考场决断指南（3 秒决定用谁）

1. 看数据规模（选型黄金法则）：

   • 给出点数 $V \le 1000$，边数 $E$ 很大（完全图或接近稠密图）：选 朴素 Prim（稳过 $O(V^2)$，完全不用建几百万条边）。
   • 给出点数 $V \le 10^5$，边数 $E \le 2 \times 10^5$（常规稀疏网格/公路网）：闭眼写 Kruskal，排序+并查集又快又绝不易写挂。

2. 考场特例辨析题（概念常考坑点）：

   • 所有边权均不同时：图的最小生成树唯一（此时 Kruskal 和 Prim 算出的生成树结构完全相同）。
   • 边权有重复时：最小生成树可能不唯一，但最小边权和必定唯一。
   • 负权边：Kruskal 和 Prim 完全支持负权边（这与求最短路的 Dijkstra 截然不同！因为 MST 只追求边的相对大小，不依赖“非递减距离和”的贪心条件）。

给我简单讲解排序算法核心知识点以及快速记忆方法：稳定性（快排/堆排/选择不稳定）、时空复杂度（最坏/最好/平均）、开放寻址与链地址法手算。

初赛（CSP-J/S 与海中自招）中，排序算法和哈希冲突是年年必出选择题的高频阵地。掌握以下体系化的口诀、对照表和手算模板，可在考场上直接秒杀。

---

第一部分：排序算法核心记忆法

一、稳定性口诀（秒杀判断题）

稳定性的定义：若序列中存在两个相同元素 $A_1 = A_2$，排序前 $A_1$ 在 $A_2$ 前面；若排序后 $A_1$ 必定依然在 $A_2$ 前面，则该排序算法是稳定的。

• 终极记忆口诀：

  $$\text{“考试成绩}\mathbf{不稳定}\text{就}\mathbf{快}\mathbf{选}\mathbf{对}\mathbf{C}\text{（快选堆希）}\text{”} $$
  • 快：快速排序
  • 选：简单选择排序
  • 堆：堆排序
  • 希：希尔排序（Shell Sort）

  考场规则：除了“快、选、堆、希”这 4 种跨步长/跨区间交换的算法不稳定，其余所有常见排序（冒泡、直接插入、归并、基数排序、计数排序）全部都是稳定的！

一句话直击为什么不稳定（反例）：

• 选择排序：序列 [5, 5*, 2] $\to$ 找到最小值 2，与第 1 个 5 交换 $\to$ [2, 5*, 5]，相对次序颠倒。
• 快速排序：双指针远距离交换，若遇到相同值元素极易被越过。
• 堆排序：建立大根堆/小根堆时，父子节点跨层交换调整破坏次序。
• 希尔排序：按步长分组，相同的两个元素被分到不同组别独立插入。

---

二、时空复杂度终极对照表

排序算法	最好时间	平均时间	最坏时间	辅助空间	稳定性	考场高频命题特征
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	稳定	优化版带 flag 标记时，原本有序只需扫一趟 $O(n)$
直接插入						基本有序时效率最高（接近 $O(n)$）
简单选择	$O(n^2)$				不稳定	无论原数组怎样，都要固定比满 $\frac{n(n-1)}{2}$ 次
希尔排序	$O(n)$	$O(n^{1.3})$				突破 $O(n^2)$ 的第一批算法，步长递减插入
快速排序	$O(n\log n)$		$\mathbf{O(n^2)}$	$O(\log n) \sim O(n)$		原数组已完全有序/逆序且基准选端点时最坏退化为 $O(n^2)$；空间为递归栈
堆排序	$\mathbf{O(n\log n)}$			$\mathbf{O(1)}$		表现最稳定（无论好坏都是 $n\log n$），且空间只需 $O(1)$
归并排序	$O(n\log n)$			$\mathbf{O(n)}$	稳定	比较类排序中唯一时空平稳且稳定的算法，代价是需要 $O(n)$ 辅助数组
基数排序	$O(d(n+r))$			$O(n+r)$		非基于比较的排序；$d$ 为位数，$r$ 为基数（如10进制 $r=10$）

---

第二部分：哈希冲突手算（拉链法 vs 开放寻址）

设待插入关键字序列为：{19, 14, 23, 1, 68}，哈希表长度 $M = 11$，哈希函数为 $H(key) = key \bmod 11$。

先算各元素初始哈希地址：

• $19 \bmod 11 = 8$
• $14 \bmod 11 = 3$
• $23 \bmod 11 = 1$
• $1 \bmod 11 = 1$（冲突）
• $68 \bmod 11 = 2$

---

方法一：链地址法（拉链法 / 链表法）

每个哈希桶维护一个单链表（新节点通常插在表头或表尾，初赛默认按插入次序挂链）：

地址 0: 空
地址 1: -> 23 -> 1
地址 2: -> 68
地址 3: -> 14
地址 4 ~ 7: 空
地址 8: -> 19
地址 9 ~ 10: 空

考题核心计算：平均查找长度（ASL）

1. 成功查找的 ASL（ASL_succ）：

   • 查 23：比较 1 次（链表第 1 个）
   • 查 1：比较 2 次（链表第 2 个）
   • 查 68：比较 1 次
   • 查 14：比较 1 次
   • 查 19：比较 1 次
   $$\text{ASL}_{\text{succ}} = \frac{1 + 2 + 1 + 1 + 1}{5} = \frac{6}{5} = 1.2 $$

2. 失败查找的 ASL（ASL_unsucc）：
   （指查找一个不存在的数，哈希定位到该地址后需要比较到空指针的次数，分母为哈希表长 $M$）

   • 桶 1 有 2 个节点，比较 2 次后发现到链尾 NULL；
   • 桶 2、3、8 各有 1 个节点，各比较 1 次；其余 7 个桶为空（比较 0 次）：
   $$\text{ASL}_{\text{unsucc}} = \frac{2 + 1 + 1 + 1 + 0\times 7}{11} = \frac{5}{11} $$

---

方法二：开放寻址法（数组内挪位）

所有元素都存放在同一个大小为 $M$ 的连续数组里。通用探测公式：

$$H_i = (H(key) + d_i) \bmod M$$

1. 线性探测法（Linear Probing）

步长 $d_i = 1, 2, 3, 4, \dots$（冲突了就挨个看右边下一个位置，环形回绕）：

1. 存 19：$H=8$ 空闲，放入桶 8（比较 1 次）；
2. 存 14：$H=3$ 空闲，放入桶 3（比较 1 次）；
3. 存 23：$H=1$ 空闲，放入桶 1（比较 1 次）；
4. 存 1：$H=1$ 冲突！
   • 尝试 $(1+1) \bmod 11 = 2$，空闲，放入桶 2（比较 2 次）；
5. 存 68：$H=2$ 冲突（被 1 占了）！
   • 尝试 $(2+1) \bmod 11 = 3$，冲突（被 14 占了）；
   • 尝试 $(2+2) \bmod 11 = 4$，空闲，放入桶 4（比较 3 次）。

• 最终散列表分布： | 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 值 | - | 23 | 1 | 14 | 68 | - | - | - | 19 | - | - | | 比较次数 | - | 1 | 2 | 1 | 3 | - | - | - | 1 | - | - |

• 查找成功的 ASL：

  $$\text{ASL} = \frac{1 + 2 + 1 + 3 + 1}{5} = \frac{8}{5} = 1.6 $$

优缺点考点：线性探测容易发生聚集（堆积）现象（Cluster），即连续一段地址被占满后，后续冲突的探测链越来越长，严重拉低性能。

---

2. 二次探测法（平方探测法，Quadratic Probing）

步长序列：$d_i = +1^2, -1^2, +2^2, -2^2, +3^2, -3^2, \dots$（即 $+1, -1, +4, -4, +9, -9, \dots$）

注意负数取模的手算技巧：$(-k) \bmod M = (M - (k \bmod M)) \bmod M$。
例如在 $M=11$ 时：$(2 - 1^2) \bmod 11 = 1$；$(2 - 2^2) \bmod 11 = (2 - 4) = -2 \equiv 9$。

• 二次探测核心优点：能有效缓解线性探测的聚集堆积问题，散布更均匀。

给我简单讲解：格雷码

格雷码（Gray Code）是初赛（CSP-J/S 及海中自招）中高频必考的编码知识点（CSP-S 2019 Day 1 第 1 题就直接考了格雷码生成）。

用最通俗易懂的方式，掌握以下 3 个核心 即可完全吃透：

---

一、什么是格雷码？为什么需要它？

• 普通二进制的缺点：
  从 $3$ 变到 $4$：011 $\to$ 100，3 个 bit 同时翻转。在真实的硬件传感器或芯片电路中，多位同时跳变极易因为微小的纳秒级延迟产生毛刺干扰和读数错误。
• 格雷码的本质：
  任意相邻的两个数，二进制表示中只有 1 位（bit）不同。
  （首尾相接也是只差 1 位，因此也是一种循环码）。

3 位格雷码与普通二进制对照：

十进制	普通二进制	格雷码	变化位（与上一行对比）
0	000	000	-
1	001	001	最低位变 1
2	010	011	中间位变 1
3	011	010	最低位变 0
4	100	110	最高位变 1
5	101	111	最低位变 1
6	110	101	中间位变 0
7	111	100	最低位变 0

---

二、考点 1：二进制转格雷码（秒杀公式）

如果你已知十进制或二进制数 $B$，求对应的格雷码 $G$：

$$G = B \oplus (B >> 1)$$

即：原数异或上原数右移 1 位。

手算口诀：

1. 最高位不变：$g_n = b_n$；
2. 其余每位等于原码该位与高一位“异或”：$g_i = b_{i+1} \oplus b_i$。

• 实战演练：把二进制 1011 转换为格雷码

    B      =  1  0  1  1
    B >> 1 =  0  1  0  1   (右移补0)
  ----------------------- (按位异或)
    G      =  1  1  1  0
  

  结果就是 1110，考场上 3 秒得出！

---

三、考点 2：格雷码还原回二进制（解码）

已知格雷码 $G$，求它代表的原二进制 $B$。

手算口诀（从左往右前缀异或累积）：

1. 最高位直接抄下来：$b_n = g_n$；
2. 往后每一位，用“刚算出的上一位二进制”与“当前格雷码位”做异或：$$b_i = b_{i+1} \oplus g_i$$

• 实战演练：把格雷码 1110 还原为普通二进制
  • 最高位：$b_3 = g_3 = \mathbf{1}$
  • 次高位：$b_2 = b_3 \oplus g_2 = 1 \oplus 1 = \mathbf{0}$
  • 第三位：$b_1 = b_2 \oplus g_1 = 0 \oplus 1 = \mathbf{1}$
  • 最低位：$b_0 = b_1 \oplus g_0 = 1 \oplus 0 = \mathbf{1}$
  • 拼起来得到二进制 1011（还原正确）。

---

四、考点 3：镜像构造法（递归生成）

$n$ 位格雷码可以由 $n-1$ 位格雷码**“镜像翻转”**推出来：

1. 1 位格雷码：0, 1
2. 2 位格雷码：
   • 前半部分：在 1 位码前加 0 $\to$ 00, 01
   • 后半部分：把 1 位码倒序并在前面加 1 $\to$ 11, 10
3. 3 位格雷码：
   • 前半部分（加0）：000, 001, 011, 010
   • 后半部分（倒序加1）：110, 111, 101, 100

考题常见问法（如“求 $n$ 位格雷码中排名第 $k$ 个的编码”）：

• 若 $k < 2^{n-1}$，首位填 0，继续在 $n-1$ 位中找第 $k$ 个；
• 若 $k \ge 2^{n-1}$，首位填 1，接下来在 $n-1$ 位中找第 $(2^n - 1 - k)$ 个（倒序找）。

---

考场速记卡

// 1. 二进制转格雷码 (一行搞定)
unsigned int binaryToGray(unsigned int n) {
    return n ^ (n >> 1);
}

// 2. 格雷码转二进制 (从高到低异或累加)
unsigned int grayToBinary(unsigned int g) {
    unsigned int b = 0;
    for (; g > 0; g >>= 1) {
        b ^= g;
    }
    return b;
}

给我简单讲解：哈希冲突（Hash Collision）的开地址法（线性探测与二次探测）

在 CSP-J/S 初赛和各省名校自招中，“哈希冲突（Hash Collision）的开地址法（线性探测与二次探测）” 是每年必考、且只要考就属于 100% 拿分的送分题。

这类题目不需要写代码，关键在于搞懂探测公式，并在草稿纸上模拟画表格。

---

一、 核心背景：什么是哈希冲突？

• 假设我们有一个长度为 $M$ 的哈希表（数组下标 $0 \sim M-1$）。
• 散列函数通常是模运算：$H(key) = key \bmod M$。
• 冲突：两个不同的数算出来的下标一样（比如 $M=11$，$key_1=1$ 和 $key_2=12$，因为 $1 \bmod 11 = 12 \bmod 11 = 1$，它们都想挤进下标 1 的位置）。
• 开地址法（Open Addressing）：既然原本的家被占了，就按照某种“既定规则”在数组里找下一个空位置。

---

二、 线性探测法（Linear Probing）——“挨个往后挪”

1. 核心公式

如果算出来的初始位置 $H_0 = H(key)$ 已经有人了，就依次往后看：

$$H_i = (H(key) + i) \bmod M \quad (i = 1, 2, 3, \dots) $$

通俗说就是：+1，+2，+3，+4……挨个往后找，走到数组末尾就绕回开头（取模）。

2. 手推实战演练

题目：散列表长 $M = 11$，$H(key) = key \bmod 11$。采用线性探测法，依次插入 {12, 23, 34}。求 34 最终落在哪个位置？

我们画一个下标 $0 \sim 10$ 的表格：

1. 插入 12：$12 \bmod 11 = 1$。下标 1 是空的，直接放入：
   • 表格：位置 1: 12
2. 插入 23：$23 \bmod 11 = 1$。发现下标 1 已经被 12 占了（冲突）！
   • 启动线性探测：试探 $(1 + 1) \bmod 11 = 2$。
   • 下标 2 是空的，放入：
   • 表格：位置 1: 12，位置 2: 23
3. 插入 34：$34 \bmod 11 = 1$。下标 1 冲突！
   • 试探 $(1 + 1) \bmod 11 = 2$，也被 23 占了，继续冲突！
   • 试探 $(1 + 2) \bmod 11 = 3$，下标 3 是空的，成功放入！
   • 结果：34 最终存放在下标 3。

• 优缺点常考点：容易产生**“聚集/堆积（Clustering）”**现象——连续一长串都被占满，后面的数冲突越来越频繁。

---

三、 二次探测法（Quadratic Probing）——“跳跃着找”

为了解决线性探测“容易扎堆”的问题，二次探测改成了步长平方跳跃（有的教材也叫平方法）。

1. 核心公式

如果 $H(key)$ 冲突，探测序列为：

$$H_i = (H(key) \pm i^2) \bmod M \quad (i = 1, 2, 3, \dots) $$

即偏移量依次为：

$$+1^2, \ -1^2, \ +2^2, \ -2^2, \ +3^2, \ -3^2, \dots $$

也就是：

$$+1, \ -1, \ +4, \ -4, \ +9, \ -9, \dots$$

⚠️ 草稿纸算负数取模秘诀（极其重要，考场避坑点）： 如果算出来是负数，直接加上表长 $M$ 即可！ 例如：$(0 - 1) \bmod 11 = -1 \rightarrow -1 + 11 = 10$。

2. 手推实战演练

题目：散列表长 $M = 11$，$H(key) = key \bmod 11$。采用二次探测法，依次插入 {12, 23, 34}。求 34 最终落在哪个位置？

1. 插入 12：$12 \bmod 11 = 1$，下标 1 空闲，存入 1。
2. 插入 23：$23 \bmod 11 = 1$，冲突！
   • 探测第一步（$+1^2$）：$(1 + 1) \bmod 11 = 2$，下标 2 空闲，存入 2。
3. 插入 34：$34 \bmod 11 = 1$，冲突！
   • 探测第一步（$+1^2$）：$(1 + 1) \bmod 11 = 2$，位置 2 已被 23 占领，继续冲突！
   • 探测第二步（$-1^2$）：$(1 - 1) \bmod 11 = 0$！
   • 下标 0 是空的，成功放入！
   • 结果：34 最终存放在下标 0（注意与线性探测得到的结果不同！）。

---

四、 考场应试“三步做题法”

初赛或自招考场上遇到这类选择题，不要在脑子里凭空想，按以下 3 步做：

1. 画尺子：草稿纸画一条横线，标出下标 $0 \sim M-1$。
2. 算模数：把每一个给出的数先模上 $M$，写在草稿纸上。
3. 按顺序落子：
   • 没冲突直接填进去；
   • 遇到冲突看清题干：
     • 若是线性：+1, +2, +3... 顺延往后走；
     • 若是二次：先试 +1，不行试 -1，再不行试 +4，再不行试 -4……（负数直接加模数 $M$）。

考试范围与备考建议

从题目结构和考点设置来看，这场自主招生考试本质上就是一套高密度的“CSP-J/S 初赛笔试精简版”。题型与全国青少年信息学奥林匹克联赛初赛完全接轨（单选、阅读程序、完善程序），且由于考试时间仅有 1 小时，考查重点在于对经典算法模板的快速理解、手推代码运行过程以及扎实的数据结构基础。

---

一、 考点难度与 GESP / CSP 对应级别映射表

题型	具体考点	GESP 对应级别	CSP 对应级别	核心备考要求与踩坑点
单项选择	进制转换、运算符优先级	GESP 1-3 级	CSP-J 初赛基础题	基础语法送分项，熟练掌握位运算、逻辑与算术运算符结合顺序，确保 100% 准确率。
	排列组合	GESP 5-6 级	CSP-J 初赛数学基础	加乘原理、排列数与组合数计算、隔板法与容斥原理基础。
	格雷码 (Gray Code)	GESP 6-7 级	CSP-S 初赛常考点	掌握二进制与格雷码互转公式（G = B ^ (B >> 1)）及递归/对称构造规律。
	链表、优先队列 (堆)	GESP 5-6 级	CSP-J / CSP-S 初赛	链表指针操作、堆的完全二叉树数组表示、priority_queue 底层调整时间复杂度。
	排序算法对比、哈希冲突		CSP-J 初赛常考点	稳定性（快排/堆排/选择不稳定）、时空复杂度（最坏/最好/平均）、开放寻址与链地址法手算。
阅读程序	贪心枚举	GESP 4-5 级	CSP-J 阅读程序	模拟小规模数据运行，推断程序在选局部最优解还是做区间覆盖/背包变体。
	归并排序 (Merge Sort)	GESP 5-6 级	CSP-J/S 核心算法	递归树分析、分治手推、双指针合并过程，注意逆序对计数变体。
	最小生成树 (MST)	GESP 7-8 级	CSP-S 核心图论	Kruskal（结合并查集）与 Prim 算法的手推执行顺序、边权与生成树权值计算。
完善程序	并查集 (Disjoint Set)	GESP 7 级	CSP-J/S 核心数据结构	路径压缩、按秩合并模板填空，查找根节点循环/递归写法。
	最长上升子序列 (LIS)	GESP 6-7 级	CSP-J/S 经典动态规划	掌握 $O(n^2)$ 传统 DP 转移与 $O(n \log n)$ 贪心+二分（lower_bound）两种模板填空。

综合定级结论：

• 整体难度定位：CSP-J 提高档 至 CSP-S 入门档（相当于 GESP 6-7 级水准）。
• 你当前的差距：你目前在 GESP 4-6 级，已具备基础语法、简单搜索与基础排序思维，主要薄弱点集中在图论算法（最小生成树）、高阶数据结构（并查集/堆/手写链表）及动态规划（LIS）的手推与笔试填空。

---

二、 突击备考规划（阶梯突击计划表）

由于目标是 9 年级下学期开学考试，且属于突击性质，策略应为：“算法模板吃透 + 历年初赛手推技巧训练 + 针对性笔试限时刷题”，无需花海量时间在 Codeforces/洛谷写大黑题，重点吃透笔试出题规律。

阶段	周期	核心突击目标	每日/每周任务拆解	检验标准
第一阶段：补齐盲区知识点	第 1 ~ 3 周	攻克 MST、并查集、LIS、格雷码与优先队列底层	1. 手写并默写 Kruskal、Prim、并查集（路径压缩）、LIS（两类写法） 代码模板。

2. 学习格雷码与二进制变换公式、链表指针手写实现。

3. 掌握哈希线性探测法与二次探测法手推过程。 | 能在白纸上 5 分钟内盲默写出并查集与 LIS 核心逻辑代码。 | | 第二阶段：阅读与完型专项突破 | 第 4 ~ 6 周 | 提升阅读程序与完善程序的阅读速度与手推能力 | 1. 刷历年 CSP-J/S 初赛第 2、3 大题（阅读程序、完善程序）。

2. 重点训练根据变量名、边界条件反推算法意图的能力。

3. 总结归并排序求逆序对、树形图遍历等常见套路。 | 阅读程序 10 分钟内手推完毕并得出边界输出，完型填空不错超过 1 空。 | | 第三阶段：选择题与计算机常识速刷 | 第 7 ~ 8 周 | 巩固单选 10 题，确保 20 分全拿 | 1. 整理排序稳定性与复杂度速查表，完成 20 组排列组合概率题。

2. 专项做 5 套历年 CSP-J 第一大题单选题。 | 单选题稳定在 9/10 或 10/10。 | | 第四阶段：全真模拟与限时冲刺 | 考前 2 周 | 适应 1 小时 50 分的高压答题节奏 | 1. 按照自招题型组卷（10选 + 3阅读 + 1完型），限时 50 分钟完成，预留 10 分钟涂卡/检查。

2. 针对错题复盘“手推越界”、“算错边界条件”等非知识性失分。 | 模拟考得分稳定在 42/50 分以上。 |

---

三、 考场应试与拿分关键点

1. 答题时间分配策略（满分 50 分，限时 60 分钟）：

• 单选题（10 题）：控制在 12 分钟内。进制、优先级、排序性质直接秒杀；排列组合草稿纸仔细计算。
• 完善程序（1 题）：控制在 10 分钟内。因为已经明示考查并查集或 LIS，直接对齐脑海中的经典模板，比对变量名填空即可，性价比最高。
• 阅读程序（3 题）：留足 30 分钟。每题 10 分钟，先读懂大意（分治、贪心还是图论算法），用题目给的小样例走一遍流程，再去勾选判断与选择。
• 检查与复核：剩余 8 分钟。重点核对单选计算题与完型填空的数组下标（是 1 还是 0 起始）。

2. 重点突破资料推荐：

• 直接刷 2020~2024 年 CSP-J/S 第一轮（初赛）真题，重点挑阅读程序和完善程序中的经典算法部分做，精准覆盖上述所有考点。

全套试题标准参考答案与讲师深度剖析

快速查对速查表

题号	1	2	3	4	5	6	7	8	9	10
单选	A	B		A	B			C	A	D

题号	11(判)	12(判)	13(选)	14(选)	15(判)	16(判)	17(选)	18(选)	19(判)	20(判)	21(选)	22(选)
阅读	B(错)	A(对)	A	C	A(对)	B(错)	C	A	A(对)		A	B

题号	23(1)	24(2)	25(3)	26(4)	27(5)
完型	A	C	B	A	C

---

逐题深度解析

第一部分：单项选择题

1. 【答案】A
   【解析】

   • $(375)_8 = 3 \times 64 + 7 \times 8 + 5 = 192 + 56 + 5 = 253$。写成二进制为 11111101。
   • $(1A)_{16} = 1 \times 16 + 10 = 26$。写成二进制为 00011010。
   • 按位异或（相同为 0，不同为 1）：
     11111101 ^ 00011010 = 11100111。对应选项 A。

2. 【答案】B
   【解析】
   C++ 运算符优先级顺序为：算术运算符（* 高于 +、-） > 关系运算符（>） > 相等运算符（!=） > 逻辑与运算符（&&）。

   • 先算 b * c = 20，a + 20 = 23；
   • 23 > b（即 23 > 4）为真（true）；
   • 右边 c - a = 2，2 != 4 为真（true）；
   • 最后计算逻辑与：true && true 结果为 1。故选 B。

3. 【答案】B
   【解析】
   按除以 3 的余数分类：

   • 余 0 集合 $A = \{3, 6, 9\}$（共 3 个）
   • 余 1 集合 $B = \{1, 4, 7\}$（共 3 个）
   • 余 2 集合 $C = \{2, 5, 8\}$（共 3 个）
     选出 3 个数的和是 3 的倍数，有两种情况：
   • 情况 1：3 个数来自同一个集合：$C_3^3 + C_3^3 + C_3^3 = 1 + 1 + 1 = 3$ 种；
   • 情况 2：3 个数分别来自 3 个不同集合：$C_3^1 \times C_3^1 \times C_3^1 = 3 \times 3 \times 3 = 27$ 种。
     总方案数为 $3 + 27 = 30$ 种。选 B。

4. 【答案】A
   【解析】
   十进制 11 的二进制为 $B = (1011)_2$。
   右移 1 位得 $B \gg 1 = (0101)_2$。
   按位异或：
   1011 $\oplus$ 0101 = 1110。选 A。

5. 【答案】B
   【解析】
   在单链表中插入节点，必须先将新节点 s 的后继指向 p 原来的后继（s->next = p->next;），然后再将 p 的后继修改为 s（p->next = s;）。若先执行 p->next = s;，原后续节点的地址就会丢失造成断链。选 B。

6. 【答案】B
   【解析】
   已有 15 个节点（此时刚好是一棵高为 4 的满二叉树，节点数 $2^4 - 1 = 15$）。新插入第 16 个元素放入完全二叉树的第 5 层。新节点向上调整（Heapify Up）最多沿着树枝一路交换到树根，交换的次数等于节点的深度，即 $\log_2(16) = 4$ 次。选 B。

7. 【答案】B
   【解析】

   • 冒泡、插入、归并都是稳定排序，B 正确；
   • 快速排序在最坏情况下退化为 $O(n^2)$，且是不稳定排序，A、C 错误；
   • 选择排序跨距离交换相同元素，是不稳定的，D 错误。

8. 【答案】C
   【解析】
   哈希表长度为 11，$H(x) = x \bmod 11$：

   • 插入 12：$12 \bmod 11 = 1$，存入下标 1；
   • 插入 23：$23 \bmod 11 = 1$，发生冲突，线性探测到下标 2，存入下标 2；
   • 插入 34：$34 \bmod 11 = 1$，发生冲突，探测下标 2 仍被占用，继续线性探测到下标 3 空闲，最终存入下标 3。故选 C。

9. 【答案】A
   【解析】
   无向连通图是树的充分必要条件是：连通且恰好包含 $n-1$ 条边（少一条不连通，多一条必有环）。选 A。

10. 【答案】D
    【解析】
    0-1 背包问题具有后效性，单纯按照单位重量价值最大贪心无法保证全局最优，必须采用动态规划求解；而分数背包问题才能用贪心。选 D。

---

第二部分：程序阅读题

（一）区间合并

• 第 11 题（B / 错）：若按右端点排序，当区间包含时（如 [1, 10] 与 [2, 3]），按右端点排会导致 [2, 3] 排在前面，算法无法单调合并重叠区间，结果会错误。
• 第 12 题（A / 对）：遍历是一次 $O(n)$，瓶颈在于前面的 std::sort，时间复杂度为 $O(n \log n)$。
• 第 13 题（A）：[1, 3] 和 [2, 6] 合并为 [1, 6]（长 5）；[8, 10]（长 2）；[15, 18]（长 3）。总长度为 $5 + 2 + 3 = 10$。选 A。
• 第 14 题（C）：所有区间完全重合，合并后为单个区间 [1, 10]，长度为 $10 - 1 = 9$。选 C。

（二）归并求逆序对

• 第 15 题（A / 对）：当左半段指针 $i$ 处的元素大于右半段 $j$ 时，由于左半段已升序排列，说明从 $i$ 到 $mid$ 的所有元素都大于 $a[j]$，共有 $mid - i + 1$ 个逆序对，完全正确。
• 第 16 题（B / 错）：由于右边已经归并了一部分，$r - j + 1$ 无法正确反映逆序对数量，统计逻辑彻底错误。
• 第 17 题（C）：长度为 5 的完全逆序数组，逆序对数为 $\frac{5 \times 4}{2} = 10$。选 C。
• 第 18 题（A）：完全升序数组没有任何逆序对，输出为 0。选 A。

（三）Kruskal 最小生成树

• 第 19 题（A / 对）：find_root 递归时执行了 parent_node[x] = find_root(...)，是标准的路径压缩，平摊复杂度接近 $O(1)$。
• 第 20 题（A / 对）：若图不连通，循环结束时加入的边数 edge_count < n - 1，程序进入 else 分支打印 -1。
• 第 21 题（A）：
  边按权值升序：
  1. (1, 2, 1)：选入，权值累加 1
  2. (2, 3, 2)：选入，权值累加 2
  3. (3, 4, 3)：选入，权值累加 3（此时已选 3 条边，$n-1=3$，满足条件终止）
     最小生成树总权值为 $1 + 2 + 3 = 6$。选 A。
• 第 22 题（B）：Kruskal 算法的瓶颈在于对 $m$ 条边排序，时间复杂度为 $O(m \log m)$。选 B。

---

第三部分：完善程序题（LIS 贪心+二分）

• 第 23 题（A）：在二分查找第一个大于等于 target 的位置时，当 d[mid] >= target，说明 mid 是一个合法候选，但左边可能还有更小的合法位置，因此记录 ans = mid 后收缩右边界：r = mid - 1。选 A。
• 第 24 题（C）：当 d[mid] < target 时，mid 处过小不满足要求，必须向右寻找，故 l = mid + 1。选 C。
• 第 25 题（B）：求严格单调递增子序列，新元素只有严格大于当前最长序列的末尾时才能延长长度，故条件为 a[i] > d[len]。选 B。
• 第 26 题（A）：长度延长至 len 后，该长度子序列的最小末尾即为当前新加入的元素 a[i]，故 d[len] = a[i]。选 A。
• 第 27 题（C）：二分找到第一个 $\ge a[i]$ 的位置 pos 后，将该位置的末尾值替换为更小的 a[i]，为后续元素留下更充裕的上升空间，故 d[pos] = a[i]。选 C。