一、基础算法

1. 贪心算法（Greedy）

核心思想：在每一步决策时，都采取当前状态下的最优选择（局部最优），期望通过一系列局部最优达到全局最优。

关键判断标准：贪心算法不一定能得到全局最优解，只有满足最优子结构和贪心选择性质的问题才适用。初赛常考查贪心算法的适用条件判断——给出一个场景，让你判断贪心策略是否可行。

CSP-S真题应用：CSP-S 2025第1题“社团招新”的标准解法就是贪心算法，结合排序或优先队列实现贪心策略。

初赛考点：贪心算法适用性判断（如“以下哪个问题可以用贪心算法求解”）、贪心策略设计（完善程序题中填写贪心决策代码）。

2. 分治算法（Divide and Conquer）

核心思想：将一个大问题分解为若干个规模较小的相同子问题，分别解决子问题，最后合并子问题的解得到原问题的解。

三大步骤：

1. 分解（Divide） ：将原问题分解为若干子问题

2. 解决（Conquer） ：递归解决子问题（子问题足够小时直接求解）

3. 合并（Combine） ：将子问题的解合并为原问题的解

典型应用：归并排序、快速排序、二分查找、最近点对问题。

初赛考点：分治算法的时间复杂度分析（主定理）、分治与递归的关系。

3. 递推与递归

递归：函数直接或间接调用自身。递归三要素——终止条件、递归公式、边界处理。

递推：从已知条件出发，按照一定的递推关系逐步推出未知结果（如斐波那契数列）。

初赛高频考点：

• 递归层数限制与栈溢出

• 递推函数计算

• 递归低效的原因——重叠子问题（引出动态规划）

• 斐波那契数列的递归复杂度O(2^n)

4. 二分查找（Binary Search）

核心思想：在有序序列中，每次将查找范围缩小一半，通过比较中间值与目标值决定向左或向右继续查找。

时间复杂度：O(log n)

适用条件：序列必须有序（或具有单调性）。

初赛考点：二分查找的条件判断、二分答案框架（最小化最大值/最大化最小值问题）。

5. 高精度计算

核心思想：当数据超出基本数据类型范围时，用数组模拟大数的存储和运算（按位存储、逐位运算、处理进位/借位）。

初赛考点：高精度加减乘除的基本原理、进位/借位处理逻辑。

二、排序算法

排序算法是初赛必考内容，重点考察时间复杂度和稳定性。

各排序算法对比总表

排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	稳定性
插入排序	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²)	❌不稳定
归并排序	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(n+m)	O(n+m)	O(n+m)	❌不稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	稳定

1. 插入排序

原理：将序列分为有序区（初始为第一个元素）和无序区，依次从无序区取出元素插入到有序区的正确位置。最佳情况：序列已有序，只需比较n-1次，O(n)。稳定排序。

2. 冒泡排序

原理：相邻元素两两比较，将较大的元素逐步“冒泡”到序列末尾。最佳情况：序列已有序，O(n)。稳定排序。

3. 选择排序

原理：每轮选择未排序部分的最小值放到已排序部分的末尾。特点：比较次数与初始排列无关，总是比较n(n-1)/2次。不稳定排序。

4. 快速排序 ⭐（CSP-S重点）

原理：选择基准值（pivot），将序列分为小于基准和大于基准两部分，递归排序两部分。

关键考点：

• 最坏情况O(n²) ：当序列已经有序时，快速排序退化为冒泡排序。这是初赛极高频考点！

• 平均情况最快：在平均情况下，快速排序是所有排序算法中最快的

• 不稳定排序

5. 归并排序

原理：分治思想——将序列不断二分至单个元素，再两两合并有序序列。

特点：时间复杂度稳定O(n log n)；稳定排序；最坏情况下表现稳定。

6. 堆排序

原理：利用堆这种数据结构（完全二叉树），通过建堆和反复取出堆顶实现排序。

特点：时间复杂度O(n log n)；不稳定排序；最坏情况下表现稳定。

7. 桶排序 / 基数排序

桶排序：将数据分到有限数量的桶中，每个桶内再排序。

基数排序：按位（个位、十位、百位……）依次排序。非比较排序，不是以“比较”为主要操作的算法。

排序算法初赛典型真题

• “在待排序数据已经有序时，哪个排序算法花费时间反而多？” → 答案：快速排序（退化为O(n²)）

• “关键字比较次数与初始排列次序无关的是？” → 答案：选择排序

• “不以比较为主要操作的算法是？” → 答案：基数排序

三、搜索算法

搜索算法在CSP-S中占比重大，初赛常考剪枝优化和搜索策略选择。

1. 深度优先搜索（DFS）

原理：从起点出发，沿着一条路径一直走到底，走不通时回溯到上一个分叉点，继续探索其他路径。通常用递归或栈实现。

应用：连通性判断、找连通分量、检测环、拓扑排序（后序逆序）。

初赛考点：DFS复杂度分析、回溯条件判断。

2. 广度优先搜索（BFS）

原理：从起点出发，逐层访问所有相邻节点，先访问的节点的相邻节点先被访问。通常用队列实现。

特点：首次找到的路径一定是最短路径（无权图）。适合“最小化”问题（如最短路）。

3. 搜索的剪枝优化 ⭐（CSP-S重点）

剪枝：在搜索过程中，通过条件判断提前排除不可能产生最优解的分支，减少搜索空间。

剪枝的两种主要类型：

• 可行性剪枝：当前分支不可能达到目标（如剩余体积不够），直接放弃

• 最优性剪枝：当前分支即使继续也不可能优于已有最优解，直接放弃

初赛考点：剪枝条件的设计（完善程序题中填写剪枝判断代码）。

4. 记忆化搜索

原理：搜索与DP的结合——在DFS过程中，将已经计算过的状态结果保存下来（用数组或哈希表），遇到重复状态时直接返回保存的结果，避免重复计算。

本质：搜索 + 备忘录 = 自顶向下的动态规划。

5. 双向BFS（Bidirectional BFS）

原理：从起点和终点同时进行BFS，两个方向的搜索“相遇”时即找到最短路径。

优势：相比单向BFS，搜索空间大幅减少（从O(b^d)降为O(b^(d/2))）。

CSP-S真题应用：2020年CSP-S初赛阅读程序题，通过双向BFS求解字符串状态变换的最短路径。

初赛考点：双向BFS的相遇条件判断、状态去重机制。

6. 迭代加深搜索（IDDFS）⭐

原理：给DFS套上一层“深度限制”循环——从深度限制1开始，逐步增加深度限制，每次在当前限制下进行DFS，直到找到解或达到上限。

为什么需要它：BFS空间消耗大，DFS可能无限递归。IDDFS结合了两者优点：空间消耗与DFS相同（O(d)），又能保证找到最优解（深度最浅）。

初赛考点：IDDFS的原理与适用场景。

四、图论算法

图论是CSP-S的绝对重点，初赛中图论相关题目占比很高。

1. 图的基本概念（初赛高频）

• 有向图 vs 无向图：边是否有方向

• 稀疏图 vs 稠密图：边数远小于n²为稀疏图，接近n²为稠密图

• 连通图：任意两点之间都有路径

• 强连通图：有向图中任意两点互相可达

• 欧拉图：存在经过每条边恰好一次的回路——所有顶点的度数均为偶数

• DAG（有向无环图） ：有向且无环的图

2. 图的存储

• 邻接矩阵：二维数组，O(n²)空间，适合稠密图

• 邻接表：链表数组，O(n+m)空间，适合稀疏图

3. 拓扑排序（Topological Sort）

定义：将DAG中所有顶点排成一个线性序列，使得对每条有向边(u→v)，u都出现在v之前。

实现：统计入度，将入度为0的节点入队，依次取出并移除其出边。

初赛考点：拓扑排序的序列种数——没有统一的n、m公式。

4. 最短路径算法

Dijkstra算法（单源最短路径）

原理：贪心思想——从起点开始，每次选择距离起点最近的未处理节点，用该节点更新其邻接节点的距离。

时间复杂度：O((n+m)log n)（堆优化）

限制：不能处理负权边

初赛考点：Dijkstra的贪心本质、堆优化的实现。

Floyd算法（多源最短路径）

原理：动态规划——枚举中间点k，用dist[i][k]+dist[k][j]更新dist[i][j]。

时间复杂度：O(n³)

特点：可以处理负权边（但不能有负环），代码极其简短（三重循环）。

初赛考点：Floyd的三重循环顺序、复杂度分析。

5. 最小生成树（MST）

Prim算法

原理：从任意顶点开始，每次选择连接已选集合与未选集合的最小权值边加入树中。

适用：稠密图

Kruskal算法

原理：将所有边按权值从小到大排序，依次加入，若加入后不形成环则保留（用并查集判断环）。

适用：稀疏图

初赛考点：Prim和Kruskal的对比与适用场景。

五、字符串算法

KMP算法（Knuth-Morris-Pratt）⭐

核心作用：解决单模式串匹配问题——在文本串中查找模式串出现的位置。

核心思想：匹配失败时，利用已经匹配的部分信息（next数组），将模式串向右滑动尽可能远的距离，避免重复比较已经匹配过的字符。

next数组（部分匹配表） ：next[i] = 模式串P[0…i]的最长公共前后缀的长度。注意：最长公共前后缀不能是字符串本身。

2025年CSP-S真题示例：模式串P="abacaba"的next数组计算：

i	子串P[0…i]	最长公共前后缀	next[i]
0	"a"	无	0
1	"ab"	无	0
2	"aba"	"a"	1
3	"abac"	无	0
4	"abaca"	"a"	1
5	"abacab"	"ab"	2
6	"abacaba"	"aba"	3

答案：{0,0,1,0,1,2,3}

初赛考点：next数组的手动计算（必考！）。

六、动态规划（DP）

动态规划是CSP-S拉差距的主战场，初赛中DP相关题目逐年增多。

DP的核心思想：将大问题分解为重叠子问题，通过状态定义和状态转移方程，利用已计算的子问题结果推导当前问题。递归低效正是因为存在大量重叠子问题，而DP通过记忆化/填表避免了重复计算。

DP三要素：

1. 状态定义：dp[i]表示什么

2. 状态转移方程：如何从子问题推导当前问题

3. 初始条件和边界：最小子问题的解

1. 线性DP

定义：状态按线性顺序（如序列位置）递推的DP。

经典问题：最长上升子序列（LIS）、最大连续子段和。

示例：以i结尾的最大连续和 dp[i] = max(dp[i-1], 0) + A[i]。

2. 背包DP（0-1背包）

问题：n个物品，每个物品有重量w[i]和价值v[i]，背包容量为C，每个物品只能选一次，求最大总价值。

状态定义：dp[i][j] = 考虑前i个物品、容量为j时的最大价值。

状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

一维优化：j从C到w[i]倒序遍历。

初赛考点：0-1背包的状态转移方程、一维优化的遍历顺序。

3. 区间DP

定义：状态定义在区间[l, r]上的DP，大区间由小区间合并得到。

经典问题：石子合并、矩阵链乘。

转移模式：dp[l][r] = max/min(dp[l][k] + dp[k+1][r] + cost)，其中k在[l, r)之间。

4. 树形DP

定义：在树结构上进行的DP。状态转移通常从叶子向根方向进行。

经典问题：树的最大独立集、树的最小点覆盖、树的直径。

5. 状态压缩DP

定义：当状态维度太多时，用二进制位表示状态集合（如哪些元素已选）。

经典问题：TSP（旅行商问题）、集合覆盖。

七、数学算法

1. 排列组合（初赛必考）

核心概念：

2025年CSP-S真题：5红5蓝排成一排，蓝球不相邻 → 先排5个红球（形成6个空隙），选5个放蓝球 → C(6,5)=6种。

2. 数论基础

模运算性质

在模 m 的运算系统中，加法、减法和乘法运算具有封闭性：

乘法逆元

当整数 a 与模数 m 互质（即 gcd(a,m)=1）时，存在唯一的整数 x ∈ [1,m-1] 满足： ax ≡ 1 (mod m) x 称为 a 模 m 的乘法逆元，记作 a⁻¹。例如：

费马小定理

对于素数 p 和与 p 互质的整数 a，有： a^(p-1) ≡ 1 (mod p) 这个定理提供了计算模素数的逆元的简便方法： a⁻¹ ≡ a^(p-2) (mod p) 示例：

扩展欧几里得算法

该算法不仅能计算 gcd(a,b)，还能求出贝祖等式 ax + by = gcd(a,b) 的整数解。算法步骤如下：

应用示例： 求解 35x + 15y = gcd(35,15)=5

中国剩余定理（CRT）

用于求解形式为： x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂) ... x ≡ aₙ (mod mₙ) 的同余方程组，其中模数 m₁,m₂,...,mₙ 两两互质。

求解步骤：

示例： 求解： x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7) 解： M=105, M₁=35, M₂=21, M₃=15 求逆元：35 ≡ 2 (mod 3), 逆元为2；21 ≡1 (mod5), 逆元为1；15≡1(mod7), 逆元为1 x = 2×35×2 + 3×21×1 + 2×15×1 = 140+63+30 = 233 ≡ 23 (mod 105)

应用：求1~1000中不被2、3、5整除的数的个数。

3.容斥原理

• 排列：与顺序有关

• 组合：与顺序无关

• 常用方法：

• 插空法：先排无限制元素，再将有限制元素插入空隙——解决不相邻问题

• 捆绑法：将必须相邻的元素捆在一起作为一个整体——解决相邻问题

• 挡板法：用隔板将相同元素分组——解决分配问题

• 圆排列：(n-1)!种

• 错排列：n个元素都不在自己位置上的排列数

• 同余关系

  同余关系是数论中重要的等价关系，记作 a ≡ b (mod m)，表示整数 a 和 b 除以正整数 m 后余数相同。具体而言，这意味着存在整数 k 使得 a - b = km。例如：

• 17 ≡ 5 (mod 6)，因为 17 - 5 = 12 = 2×6
• 同余关系具有自反性、对称性和传递性
• 加法封闭性：(a + b) mod m = [(a mod m) + (b mod m)] mod m
  • 例：(15 + 23) mod 7 = 38 mod 7 = 3
• 减法封闭性：(a - b) mod m = [(a mod m) - (b mod m)] mod m
  • 例：(23 - 15) mod 7 = 8 mod 7 = 1
• 乘法封闭性：(a × b) mod m = [(a mod m) × (b mod m)] mod m
  • 例：(5 × 3) mod 7 = 15 mod 7 = 1
• 3 模 7 的逆元是 5，因为 3×5 = 15 ≡ 1 (mod 7)
• 逆元在模除运算中起关键作用，因为模运算中 a/b ≡ a×b⁻¹ (mod m)
• 计算 3 模 7 的逆元：3^(7-2) = 3^5 = 243 ≡ 5 (mod 7)
• 验证：3×5 = 15 ≡ 1 (mod 7)
• 若 b=0，返回 (a,1,0)
• 递归计算 (g,x₁,y₁) = exgcd(b, a mod b)
• 返回 (g,y₁,x₁ - ⌊a/b⌋y₁)
• 递归过程：exgcd(35,15)→exgcd(15,5)→exgcd(5,0)
• 回代得到解：x=1, y=-2 验证：35×1 + 15×(-2) = 35 - 30 = 5
• 计算 M = ∏mᵢ
• 对每个 i，计算 Mᵢ = M/mᵢ
• 求 Mᵢ 模 mᵢ 的逆元 yᵢ
• 解为 x ≡ ∑aᵢMᵢyᵢ (mod M)

核心思想：容斥原理是一种常用的组合数学方法，其基本思路是：先不考虑集合之间的交集关系，将所有集合的元素数量相加（可能造成重复计算），然后通过逐步减去交集部分来消除重复计算，最终得到准确的并集大小。

具体来说：

• 对于两个集合A和B：|A∪B| = |A| + |B| - |A∩B|
• 对于三个集合A、B、C：|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| 这个模式可以推广到n个集合的情况，通过交替加减交集项来实现精确计数。

应用示例：求1~1000中不被2、3、5整除的数的个数

解决步骤：

1. 先计算被2、3或5整除的数的个数：
   • 被2整除的数：⌊1000/2⌋=500个
   • 被3整除的数：⌊1000/3⌋=333个
   • 被5整除的数：⌊1000/5⌋=200个
2. 减去被两个数同时整除的重复计算部分：
   • 被2和3整除(即6的倍数)：⌊1000/6⌋=166个
   • 被2和5整除(即10的倍数)：⌊1000/10⌋=100个
   • 被3和5整除(即15的倍数)：⌊1000/15⌋=66个
3. 加回被三个数同时整除的部分(因为被减去了三次)：
   • 被2、3和5整除(即30的倍数)：⌊1000/30⌋=33个
4. 最终计算被2、3或5整除的数的总数： 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734个
5. 求不被2、3、5整除的数的个数： 总数1000 - 被整除数734 = 266个

典型应用场景：

• 组合计数问题
• 概率计算
• 数论问题
• 几何图形计数
• 数据统计分析中的重叠情况处理

4. 复杂度分析

时间复杂度：算法运行时间随输入规模增长的变化趋势。

常见复杂度排序：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)

初赛高频考点：

附录：算法考点优先级速查

优先级	算法类别	具体考点	考察频率
⭐⭐⭐	排序算法	稳定性、时间复杂度（快排最坏O(n²)）	每年必考
⭐⭐⭐	KMP算法	next数组手动计算	近年必考
⭐⭐⭐	搜索剪枝	可行性剪枝、最优性剪枝	高频
⭐⭐⭐	图论	Dijkstra、Floyd、Prim、Kruskal、拓扑排序	高频
⭐⭐	动态规划	状态定义、转移方程（背包、区间、树形）	中高频
⭐⭐	贪心算法	适用条件判断	中频
⭐⭐	组合数学	插空法、捆绑法、容斥原理	中频
⭐	数论	同余、逆元、费马小定理	中低频
⭐	分治/二分	时间复杂度分析	中低频

冲刺建议：排序算法和KMP是初赛性价比最高的考点——规律性强、容易拿分、几乎每年都考。务必熟练掌握！

初赛考点：同余运算、逆元计算、模运

• 快速排序最坏O(n²)

• 快速幂O(log n)

• 斐波那契递归O(2^n)

• 二分查找O(log n)

• 主定理分析递归复杂度