CCF GESP C++G5核心知识点速记手册
一、核心知识点框架
（一）数论基础
- 初等数论核心概念
- 辗转相除法（欧几里得算法）
- 素数筛选（埃氏筛法、线性筛法）
- 唯一分解定理
（二）数据结构
- 链表（单链表、双链表、循环链表）
- 数组模拟高精度运算（加、减、乘、除）
（三）核心算法
- 二分查找/二分答案
- 贪心算法
- 分治算法（归并排序、快速排序）
- 递归算法
（四）算法复杂度
- 多项式复杂度（O(n)、O(n²)等）
- 对数复杂度（O(log n)、O(n log n)等）
- 指数复杂度（O(2ⁿ)等）
- 复杂度比较与选择
二、高频考点速记
（一）数论基础
1. 辗转相除法（求最大公约数）
- 核心公式：gcd(a, b) = gcd(b, a % b)，当b=0时返回a
- 代码模板（迭代版）：
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}
- 扩展：最小公倍数lcm(a,b) = a*b / gcd(a,b)（需注意溢出）
2. 素数筛选
- 埃氏筛法（O(n log log n)）：
- 核心：标记每个素数的倍数为合数，从i*i开始标记可优化
- 适用场景：快速生成n以内所有素数
- 线性筛法（O(n)）：
- 核心：每个合数仅被其最小质因子标记一次，避免重复
- 关键代码：
if (i % primes[j] == 0) break;
3. 唯一分解定理
- 核心：每个大于1的自然数可唯一分解为素数幂乘积（如12=2²×3）
- 质因子分解步骤：
- 枚举2到√n的因子，记录质因子及指数
- 若剩余n>2，补充为最后一个质因子
- 应用：质因数分解、约数个数计算、倍数判断
（二）数据结构
1. 链表操作
| 链表类型 |
核心操作 |
时间复杂度 |
| 单链表 |
插入、删除、遍历 |
O(n)（查找）、O(1)（已知位置操作） |
| 双链表 |
双向插入、删除 |
O(n)（查找）、O(1)（已知位置操作） |
| 循环链表 |
首尾相连遍历 |
O(n) |
- 关键技巧：
- 单链表删除节点：找到前驱节点，修改指针指向
- 双链表插入：同时维护prev和next指针
- 循环链表判断：尾节点next指向头节点
2. 高精度运算（数组模拟）
- 存储方式：数组逆序存储（低位存数组低位）
- 加法核心：逐位相加+进位处理（carry = sum / 10）
- 减法核心：逐位相减+借位处理（借位时当前位+10，高位-1）
- 乘法核心：逐位相乘+错位相加+进位处理
- 除法核心：模拟手工除法，逐位求商+余数更新
（三）核心算法
1. 二分查找/二分答案
int binarySearch(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2; // 避免溢出if (nums[mid] == target) return mid;else if (nums[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}
- 二分答案（求满足条件的最值）：
- 适用场景：答案存在上下界，且满足单调性
- 步骤：确定边界→判断条件→收缩区间
2. 贪心算法
- 核心思想：每步选择局部最优解，逼近全局最优
- 典型应用：
- 硬币找零（大面值优先）
- 活动安排（结束时间最早优先）
- 区间覆盖（选覆盖广的区间）
- 关键：证明问题满足贪心选择性质和最优子结构
3. 分治算法
- 归并排序（稳定排序）：
- 步骤：分解（拆分为两个子数组）→ 求解（子数组排序）→ 合并（合并有序子数组）
- 时间复杂度：O(n log n)，空间复杂度：O(n)
- 快速排序（不稳定排序）：
- 步骤：选择基准→分区（小于基准放左，大于放右）→ 递归排序
- 时间复杂度：平均O(n log n)，最坏O(n²)（可通过随机基准优化）
4. 递归算法
- 核心要素：终止条件+递归表达式
- 典型应用：斐波那契数列、汉诺塔、阶乘计算
- 注意事项：
- 避免重复计算（如斐波那契数列可加记忆化）
- 防止栈溢出（递归深度不宜过大）
- 时间复杂度分析（递归树法、主定理）
（四）算法复杂度
1. 常见复杂度排序
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
2. 高频算法复杂度
| 算法 |
时间复杂度 |
空间复杂度 |
| 冒泡排序 |
O(n²) |
O(1) |
| 归并排序 |
O(n log n) |
O(n) |
| 快速排序 |
平均O(n log n) |
平均O(log n) |
| 二分查找 |
O(log n) |
O(1) |
| 埃氏筛法 |
O(n log log n) |
O(n) |
| 线性筛法 |
O(n) |
O(n) |
3. 复杂度优化技巧
- 用O(n log n)算法替代O(n²)算法（如排序用归并/快排替代冒泡）
- 用二分查找优化线性查找（将O(n)降为O(log n)）
- 用空间换时间（如筛法生成素数表）
三、易错点提醒
- 素数判断：循环条件需到√n（i*i <= n），避免遗漏因子
- 链表操作：注意空指针判断，双链表需同时维护prev和next
- 高精度运算：逆序存储、进位/借位处理、前导零去除
- 递归算法：必须设置明确终止条件，避免无限递归
- 二分查找：边界处理（left <= right vs left < right），避免死循环
- 贪心算法：并非所有问题都适用，需验证可行性
四、解题策略
- 读题分析：明确问题类型（数论、排序、查找等），确定适用算法
- 复杂度估算：根据数据规模选择算法（n≤1e5优先O(n log n)算法）
- 代码实现：
- 优先使用模板代码（如gcd、二分查找）
- 处理边界情况（如n=0、n=1、空链表等）
- 调试优化：
- 小数据测试（验证逻辑正确性）
- 大数据优化（如筛法的边界优化、递归改迭代）