知识块①：计数原理——「加法原理与乘法原理」
1.1 加法原理——「要么……要么……，各种情况相加」
定义： 如果完成一件事有n类不同的方案，第1类方案有m₁种方法，第2类方案有m₂种方法，……，第n类方案有mₙ种方法，且这些方案互不重叠，那么完成这件事共有 m₁ + m₂ + … + mₙ 种方法。
（2025年12月判断第1题） 练习题： 若一项任务可用两种互斥方案完成：方案A有m种做法，方案B有n种做法，则总做法数为m+n。
答案：√。这就是加法原理的直接应用。
1.2 乘法原理——「先……再……，各步相乘」
定义： 如果完成一件事需要分成n个步骤，第1步有m₁种方法，第2步有m₂种方法，……，第n步有mₙ种方法，且各步骤之间相互独立，那么完成这件事共有 m₁ × m₂ × … × mₙ 种方法。
1.3 加法原理与乘法原理的区别
适用场景
加法原理：分类完成（「要么选A，要么选B」）
乘法原理：分步完成（「先做A，再做B」）
关键词
加法原理：「或者」、「任选其一」
乘法原理：「并且」、「先……再……」
运算
加法原理：加法（各类相加）
乘法原理：乘法（各步相乘）
互斥性
加法原理：各类方案互不重叠
乘法原理：各步骤相互独立
（2025年12月第2题） 练习题： 用0~9组成没有重复数字的三位数，百位不能为0，有多少种？
解析： 分三步：百位1~9（9种），十位0~9中除去百位已选的（9种），个位0~9中除去百位和十位已选的（8种）。总方案数 = 9 × 9 × 8 = 648。
知识块②：排列与组合——「选出来是组合，排好序是排列」
2.1 排列——「顺序重要」
排列数： 从n个不同元素中取出m个（m≤n）元素，按照一定顺序排成一列，称为排列。所有排列的个数称为排列数。
公式： P(n, m) = n × (n-1) × (n-2) × … × (n-m+1) = n! / (n-m)!
（2024年6月第1题） 练习题： ABCDE五个小朋友，排成一队跑步，其中AB两人必须排在一起，一共有多少种排法？
解析： 将AB看作一个整体，有4个「元素」排列：4! = 24种。AB内部可以互换：2! = 2种。总方案数 = 24 × 2 = 48种。
答案： 48种。
（2026年3月第10题） 练习题： 6个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头，不同排法有（ ）种？
解析： ①先将甲乙捆绑看作一个整体，有2! = 2种内部排列。②此时有5个「元素」（甲乙整体+丙丁戊己）排列，总排列数5! = 120。③丙在排头的情况：丙固定排头，剩余4个「元素」（甲乙整体+丁戊己）排列，4! = 24，但甲乙内部有2! = 2种，所以丙在排头的情况有24×2=48种。④总方案数 = 120×2 - 48 = 240 - 48 = 192种。
答案： C（192种）。
2.2 组合——「顺序不重要」
组合数： 从n个不同元素中取出m个（m≤n）元素，不考虑顺序，称为组合。所有组合的个数称为组合数。
公式： C(n, m) = P(n, m) / m! = n! / [m! × (n-m)!]
重要性质：
· C(n, m) = C(n, n-m) —— 对称性
· C(n, 0) = C(n, n) = 1
· C(n, 1) = C(n, n-1) = n
（2024年3月第2题） 练习题： 从10个不同元素中选3个，有多少种选法？
答案： C(10, 3) = 10×9×8 / (3×2×1) = 120种。
2.3 有重复元素的全排列
公式： 如果n个元素中有k种不同的元素，每种元素分别有n₁, n₂, …, nₖ个（n₁+n₂+…+nₖ=n），那么全排列数为：
n! / (n₁! × n₂! × … × nₖ!)
（2024年6月判断第3题） 练习题： 一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个，再放回袋子，这样进行3次后，可能的颜色顺序有8种。
解析： 每次取出后放回，所以每次取球是独立的，有红和蓝2种可能。3次独立取球，共有2³ = 8种可能的颜色顺序。
答案：√。注意问题中「放回」是关键词，有放回时每次独立。
（2023年12月判断第2题） 练习题： 一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个，且不放回，这样进行3次后，将取出的小球依次排列，则可能的颜色顺序有7种。
解析： 不放回，从5个球中取3个。相当于从3红2蓝中选3个球排列。可能的红球数量可以是3、2、1。
· 3红：只有1种顺序（红红红）
· 2红1蓝：相当于3个位置选1个放蓝球，C(3,1)=3种
· 1红2蓝：相当于3个位置选1个放红球，C(3,1)=3种
总方案数 = 1 + 3 + 3 = 7种。
答案：√。
2.4 组合数学常见题型总结
题型1：相邻问题——捆绑法
将必须相邻的元素视为一个整体，先排整体，再排内部。（2026年3月第10题）
题型2：不相邻问题——插空法
先排其他元素，再在空隙中插入不能相邻的元素。
题型3：限定位置问题
先考虑特殊位置（如排头/排尾）的约束，再排其他元素。
题型4：至少/至多问题
用补集思想：总方案数 - 不满足条件的方案数。（2026年3月第1题、第4题）
题型5：有重复元素问题
用公式 n! / (n₁! × n₂! × … × nₖ!)
知识块③：杨辉三角与二项式定理——「数与形的完美结合」
3.1 杨辉三角的定义
杨辉三角（又称帕斯卡三角形） 是一种二项式系数的三角形排列。在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现，是中国数学史上的一项伟大成就。
（2023年12月判断第3题） 判断题：杨辉三角，是二项式系数的一种三角形排列，在中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现，是中国数学史上的一项伟大成就。
答案：√。
3.2 杨辉三角的构造
第0行： 1
第1行： 1 1
第2行： 1 2 1
第3行： 1 3 3 1
第4行： 1 4 6 4 1
第5行： 1 5 10 10 5 1
构造规则： 第n行有n+1个数，每行首尾都是1，中间每个数等于它上方两数之和。
3.3 杨辉三角与组合数的关系
杨辉三角第n行第k个数（从0开始计数）等于 C(n, k)，即组合数。
· 第0行：C(0,0) = 1
· 第1行：C(1,0)=1, C(1,1)=1
· 第2行：C(2,0)=1, C(2,1)=2, C(2,2)=1
· 第3行：C(3,0)=1, C(3,1)=3, C(3,2)=3, C(3,3)=1
3.4 杨辉三角的重要性质
（2025年12月判断第5题） 练习题： 在杨辉三角形中，第n行（从0开始计数，即第n行有n+1个数）的所有数字之和等于2ⁿ。
答案：√。第n行各数之和 = C(n,0) + C(n,1) + … + C(n,n) = 2ⁿ。
（2026年3月第2题） 练习题： 二项式(a+b)ⁿ展开式中各项的二项式系数之和等于2ⁿ。
答案：√。这就是杨辉三角第n行之和。
（2026年3月判断第2题） 练习题： 对于任意正整数n，二项式(a+b)ⁿ展开式中各项的二项式系数之和等于2ⁿ。
答案：√。
3.5 二项式定理
公式： (a+b)ⁿ = C(n,0) × aⁿ + C(n,1) × aⁿ⁻¹b + … + C(n,k) × aⁿ⁻ᵏbᵏ + … + C(n,n) × bⁿ
（2024年6月第12题） 练习题： (x+1)⁶的展开式中x³项的系数是？
解析： 根据二项式定理，x³项对应C(6,3) = 6×5×4/(3×2×1) = 20。
答案： 20。
知识块④：倍增法——「用指数级增长来加速查询」
4.1 倍增法的核心思想
倍增法（Binary Lifting） 是一种利用二进制分解来加速查询和计算的算法思想。核心是：将一次需要O(n)的查询，通过预处理，降为O(log n)甚至O(1)。
4.2 快速幂——「倍增法最经典的应用」
（2026年3月第3题） 练习题：快速幂算法的时间复杂度是多少？
答案： O(log n)。每次将指数减半，只需要log₂n次乘法。
// 快速幂计算 a^b % mod
long long fastPow(long long a, long long b, long long mod) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
4.3 RMQ（区间最值查询）——「ST表」
（2026年3月判断第7题） 练习题： 使用倍增法预处理区间最值问题时，预处理的时间复杂度为O(n log n)，查询的时间复杂度为O(1)。
答案：√。ST表用倍增法预处理，每次查询O(1)即可得到区间最值。
ST表原理： st[i][k]表示从i开始长度为2ᵏ的区间的最值。
· 预处理：st[i][0] = a[i]，st[i][k] = max(st[i][k-1], st[i+2ᵏ⁻¹][k-1])
· 查询[l, r]：k = floor(log₂(r-l+1))，答案为max(st[l][k], st[r-2ᵏ+1][k])
4.4 LCA（最近公共祖先）
倍增法求LCA： 预处理每个节点向上跳2ᵏ步的祖先节点，查询时先将两个节点跳到同一深度，再一起向上跳。
时间复杂度： 预处理O(n log n)，单次查询O(log n)。
知识块⑤：代数与平面几何（初中数学部分）
5.1 一元一次方程
形式： ax + b = 0（a ≠ 0），解为 x = -b/a
（2023年12月判断第1题） 判断题： C++语言非常强大，可以用来求解方程的解。例如，如果变量x为double类型的变量，则执行语句 x * 2 - 4 = 0; 后，变量x的值会变为2.0。
答案：×。C++中 x * 2 - 4 = 0 不是赋值语句，这是一个表达式，不能用于赋值给x。正确的写法是 x = (0 + 4) / 2;。
5.2 二元一次方程
形式： 两个方程组成的方程组，如：
解法： 代入消元法、加减消元法。
5.3 平面几何基本图形面积
三角形面积： S = 底 × 高 / 2
（2023年12月判断第7题） 练习题： 已知int类型的变量a、b和h中分别存储着一个梯形的顶边长、底边长和高，则这个梯形的面积可以通过表达式 (a+b)*h/2 求得。
答案：√。梯形面积公式为 (上底+下底)×高/2。
长方形面积： S = 长 × 宽
圆形面积： S = π × r²
勾股定理（2023年12月判断第4题）： 直角三角形两直角边a、b的平方和等于斜边c的平方，即 a² + b² = c²。
（2024年6月判断第4题） 练习题： 已知int类型的变量a和b中分别存储着一个直角三角形的两条直角边的长度，则斜边的长度可以通过表达式 sqrt(a * a + b * b) 求得。
答案：√。勾股定理，sqrt函数计算平方根。
（2026年6月第8题） 练习题： 判断点P(x, y)是否在以原点为圆心、半径为5的圆内或圆上，正确的判断条件是？
答案：x * x + y * y <= 25。到原点距离的平方 ≤ 半径的平方。
（2026年3月第14题） 三点共线判定： 给定三个点，通过斜率相等或向量叉积为0来判断是否共线。
知识块⑥：图论算法及综合应用——「八级的绝对核心」
6.1 最小生成树（MST）
定义： 在一个连通无向带权图中，找出一个包含所有顶点的树形子图，使得所有边权之和最小。
（2024年6月第9题） 练习题： 某无向带权图有边(1,2,4)、(1,3,2)、(2,3,1)、(2,4,5)、(3,4,8)、(3,5,10)、(4,5,2)。该图最小生成树的总权值为？
解析： 用Kruskal算法，按边权从小到大选择：
· 选(2,3)权1 → 选(1,3)权2 → 选(4,5)权2 → 选(1,2)权4（但(1,2)和(2,3)(1,3)连通了，形成环，跳过）→ 选(2,4)权5
总权值 = 1 + 2 + 2 + 5 = 10。
答案： D（10）。
算法1：Kruskal算法——「选边法」
核心思想： 将所有边按权值从小到大排序，依次选择不会形成环的边加入MST，直到选够n-1条边。
（2025年12月第15题） 练习题： 对连通无向图执行Kruskal算法。已按边权从小到大依次扫描到某条边e=(u,v)。此时在已经构建的部分MST结构中，(u,v)已在同一连通块内。关于边e的处理，下列说法正确的是？
解析： 如果(u,v)已在同一连通块内，再选这条边会形成环，所以一定不能选入MST（在此扫描顺序下）。
答案： B。
// Kruskal算法（并查集实现）
struct Edge { int u, v, w; };
vector<Edge> edges;
vector<int> parent(n+1);
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
int kruskal() {
sort(edges.begin(), edges.end(), [](Edge a, Edge b){ return a.w < b.w; });
iota(parent.begin(), parent.end(), 0);
int total = 0, cnt = 0;
for (auto& e : edges) {
int ru = find(e.u), rv = find(e.v);
if (ru != rv) {
parent[ru] = rv;
total += e.w;
if (++cnt == n-1) break;
}
}
return total;
}
（2025年9月第14题） 练习题： Prim算法中松弛操作的条件是？
答案：graph[u][v] != 0 && key[v] > graph[u][v]。当u和v之间有边且v的当前key值大于边的权值时，更新key值。
算法2：Prim算法——「选点法」
核心思想： 从一个顶点开始，每次选择与当前已选顶点集合相连的最小权值边，将新顶点加入集合，直到所有顶点都被选中。
Kruskal vs Prim：
策略
Kruskal算法：选边（按权值从小到大）
Prim算法：选点（从已选集合向外扩展）
数据结构
Kruskal算法：并查集
Prim算法：堆/优先队列
时间复杂度
Kruskal算法：O(E log E)
Prim算法：O(E log V)（堆优化）/ O(V²)（朴素）
适用场景
Kruskal算法：稀疏图（E较小）
Prim算法：稠密图（V较小）
（2026年3月判断第9题） 练习题： Kruskal算法和Prim算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。
答案：×。如果图中有多条权值相同的边，不同的MST算法可能选择不同的边，但总边权值相同。但「必定相同」的说法过于绝对——如果图中有相同权值的边，不同的实现可能选出不同的边集，但总权值一定相同。这道题需要注意：总边权和一定相同，因为最小生成树的总权值是唯一的，但具体选哪条边可能不同。
（2026年3月判断第4题） 练习题： 若一个无向图的最小生成树唯一，则图中所有边权必定各不相同。
答案：×。边权各不相同是MST唯一的充分条件，但不是必要条件。即使有相同权值的边，MST也可能唯一。
（2026年3月判断第8题） 练习题： 如果将一个连通无向图G₁中所有边的权值都统一增加同一个正整数常数C，形成图G₂。则G₁的最小生成树中每条边在G₂中对应的边组成的树，一定是G₂的最小生成树。
答案：×。所有边权统一增加C后，原来的MST不一定是新的MST。因为MST的选边依据是边权大小比较，统一增加后，原来权值较大的边和权值较小的边之间的相对差距不变，所以MST结构不变。但注意：如果图中有两条边权值相同，增加相同常数后仍然相等，所以MST不变。但如果增加的是同一个常数，其实所有边的相对大小关系不变，所以MST结构不变。这道题实际上需要仔细分析——如果所有边权统一增加同一个正数，MST结构不变，因为MST只依赖于边的相对大小顺序。但答案为什么是×？因为题目说的是「统一增加同一个正整数常数C」，如果C是负数或者考虑边的权值可能为0的情况，情况可能不同。实际上在正权图中，统一增加同一正数，MST结构保持不变。但命题的陷阱在于「增加」后，如果有两条边权值相同，原本可以选其中任意一条，但增加后仍然相等，所以MST结构保持不变。这道题的正确答案存在争议，建议以官方答案为准。
6.2 最短路径——「Dijkstra算法与Floyd算法」
算法1：Dijkstra算法——「单源最短路」
（2026年6月第10题） 练习题： 有向非负权图边为1→2(3)、2→4(4)、1→3(10)、3→4(1)、2→3(2)。使用Dijkstra算法从1号顶点出发到4号顶点的最短距离为？
解析：
· 从1出发：dist[1]=0，dist[2]=3，dist[3]=10，dist[4]=∞
· 选最小未访问节点2：通过2更新dist[3]=min(10, 3+2)=5，dist[4]=min(∞, 3+4)=7
· 选最小未访问节点3：通过3更新dist[4]=min(7, 5+1)=6
· 选最小未访问节点4：结束
答案： A（6）。
Dijkstra算法的时间复杂度（2026年3月第6题）：
· 朴素实现：O(V²)
· 优先队列（小根堆）优化：O((V+E) log V)（2025年9月第11题）
Dijkstra算法的重要限制：不能处理负权边。（2026年3月第9题）
（2026年3月第9题） 练习题： 关于图论中的最短路径算法，下列说法中严格正确的是？
· A. Dijkstra算法能够高效处理包含负权边的有向图 → ×
· B. Floyd算法可以求出任意两点间的最短路径，且允许图中存在负权边（但不能有负权环） → √
· C. 单源最短路径算法无法用于无向图 → ×，无向图可用于Dijkstra
· D. Dijkstra算法的每一步必定从当前未访问的节点中，选取距离起始点最远的节点进行松弛操作 → ×，是选取距离最近的节点
（2025年12月判断第6题） 练习题： 使用二叉堆优化的Dijkstra最短路算法，在某些特殊情况下时间复杂度不如朴素实现的O(V²)。
答案：√。当图是稠密图（E接近V²）时，堆优化的Dijkstra为O((V+V²)log V) = O(V² log V)，反而不如朴素实现的O(V²)。
算法2：Floyd算法——「全源最短路」
（2026年3月第11题） 练习题：Floyd算法中，横线处应填入？
void floyd(int n, int dist[][MAXN]) {
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if ( ______ )
dist[i][j] = dist[i][k] + dist[k][j];
}
答案：dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]。需要同时满足：i到k有路径、k到j有路径、且通过k中转更短。
Floyd算法时间复杂度： O(V³)
（2026年3月第8题） 练习题： 在使用Floyd算法求任意两点间最短路径时，时间复杂度为O(V³)。若在某次算法执行前，已经用Dijkstra算法正确求出了所有点对的最短路并存入了dist数组。如果此时继续对该dist数组执行一次完整的Floyd算法过程（无任何提前终止），执行完毕后dist数组内的值（ ）。
答案： B（不会发生改变）。因为dist数组中已经是正确的最短路径，Floyd的松弛操作不会产生更小的值。
6.3 欧拉回路
（2026年3月判断第6题） 练习题： 若一个图中所有顶点的度数为偶数，则一定存在欧拉回路。
答案：×。还需要图是连通的。对于无向图，欧拉回路存在的充要条件是：所有顶点度数均为偶数，且图是连通的（或所有边属于同一个连通分量）。
知识块⑦：算法的时间和空间效率分析
7.1 时间复杂度分析
大O表示法： 描述算法运行时间随输入规模增长的趋势，忽略常数因子和低阶项。
常见时间复杂度比较：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ)
7.2 各类算法的时间复杂度
（2025年12月判断第3题） 练习题： 快速排序和归并排序的平均时间复杂度都是O(n log n)，但快速排序是不稳定的排序算法，归并排序是稳定的排序算法。
答案：√。
（2025年12月判断第8题） 练习题： 快速排序在最坏情况下的时间复杂度为O(n log n)，可以通过随机化选择基准值(pivot)的方法完全避免退化。
答案：×。快速排序最坏情况时间复杂度为O(n²)。随机化选择基准值可以降低退化为最坏情况的概率，但无法完全避免。
（2026年6月第11题） 练习题： 下列代码片段的时间复杂度为？
for (int i = 1; i <= n; i++)
for (int j = 1; j * j <= n; j++)
s += i + j;
解析： 外层循环n次，内层循环√n次，总时间复杂度为O(n√n)。
答案： C（O(n√n)）。
时间复杂度速查表：
冒泡排序
最好情况：O(n)
平均情况：O(n²)
最坏情况：O(n²)
插入排序
最好情况：O(n)
平均情况：O(n²)
最坏情况：O(n²)
选择排序
最好情况：O(n²)
平均情况：O(n²)
最坏情况：O(n²)
快速排序
最好情况：O(n log n)
平均情况：O(n log n)
最坏情况：O(n²)
归并排序
最好情况：O(n log n)
平均情况：O(n log n)
最坏情况：O(n log n)
堆排序
最好情况：O(n log n)
平均情况：O(n log n)
最坏情况：O(n log n)
二分查找
最好情况：O(log n)
平均情况：O(log n)
最坏情况：O(log n)
二叉树查找
最好情况：O(log n)
平均情况：O(log n)
最坏情况：O(n)
DFS/BFS（邻接表）
最好情况：O(V+E)
平均情况：O(V+E)
最坏情况：O(V+E)
埃氏筛法
最好情况：O(n log log n)
平均情况：O(n log log n)
最坏情况：O(n log log n)
快速幂
最好情况：O(log n)
平均情况：O(log n)
最坏情况：O(log n)
（2024年6月第13题） 练习题： 埃拉托斯特尼筛法（埃氏筛法）的时间复杂度是？
答案： O(n log log n)。
（2024年6月第14题） 练习题： 辗转相除法（欧几里得算法）求最大公约数的最差时间复杂度是？
答案： O(log n)。
7.3 空间复杂度分析
空间复杂度是指算法在运行过程中所占用的存储空间大小，通常也用大O表示法。
常见空间复杂度：
· O(1)：只需要常数个额外变量
· O(n)：需要线性大小的额外空间（如数组）
· O(n²)：需要二维数组大小的空间
· O(n log n)：如归并排序的临时数组、ST表
知识块⑧：算法优化——「让程序跑得更快」
8.1 数学知识优化
例1：等差数列求和
// 优化前：循环求和 O(n)
int sum = 0;
for (int i = 1; i <= n; i++) sum += i;
// 优化后：数学公式 O(1)
int sum = n * (n + 1) / 2;
例2：快速幂（知识块④已介绍）
8.2 时间与空间的权衡
典型场景：
· 滚动数组： 用O(n)空间代替O(n²)空间，但时间不变（如DP优化）
· 哈希表： 用空间换时间，查找O(1)但需要额外存储
· 记忆化搜索： 用数组存储中间结果，避免重复计算
8.3 不同算法求解同一问题的差异分析
例： 求最短路径
· BFS（无权图）： O(V+E)，但只能处理无权图
· Dijkstra（非负权图）： O((V+E)log V)，处理非负权图
· Floyd（任意图，无负环）： O(V³)，求所有点对最短路
· Bellman-Ford（任意图，含负权）： O(VE)，可检测负环
（2025年9月第8题） 练习题： 贪心法和动态规划都是解决最优化问题的方法，下列说法正确的是？
解析： 贪心法每一步选择局部最优，不一定得到全局最优；动态规划通过子问题的最优解构建全局最优解。
