2025 寒假线上培训

第一讲：字符串算法与哈希技巧 @Online Feb 7 19:00-20:00

讲义链接：字符串算法与哈希技巧

幻灯片PDF：字符串算法与哈希技巧

1. 字符串哈希与快速匹配：介绍字符串哈希的原理、常见哈希函数以及应用场景，例如字符串匹配、最长回文子串等。
2. KMP算法与高效字符串匹配：讲解KMP算法的原理、next数组的求解以及代码实现，分析其时间复杂度。

第二讲：图与树的基本概念 @Online Feb 9 19:00-20:00

1. 介绍图的基本概念（有向图、无向图、权重图等）。讲解图的常见存储方式（邻接矩阵、邻接表）。
2. 介绍树的性质（连通无环图、根树、子树等）。讲解树的遍历算法（前序遍历、中序遍历、后序遍历、层序遍历）。

第三讲：图上的遍历算法 @Online Feb 11 19:00-20:00

讲义链接：图上的遍历算法

1. 广度优先搜索 (BFS)： 讲解BFS算法的原理、实现方法（队列实现）。应用场景：无权图中的单源最短路径问题、连通分量问题等。
2. 深度优先搜索 (DFS)：讲解DFS算法的原理、实现方法（递归或栈实现）。 应用场景：图的拓扑排序、强连通分量、环检测等。

第四讲：区间查询与更新问题 @Online Feb 13 19:00-20:00

讲义链接：区间查询与更新问题

1. 树状数组与单点更新区间查询：介绍树状数组的原理、操作以及应用场景，例如求解逆序对、区间和等。
2. 线段树与区间更新区间查询：讲解线段树的原理、操作以及应用场景，例如求解区间最大值、区间最小值等。
3. 树状数组与线段树的比较：分析树状数组和线段树的优缺点，以及各自适用的场景。

第五讲：最短路径问题 @Online Feb 15 19:00-20:00

讲义链接：最短路径问题

1. Dijkstra算法与单源最短路径：讲解Dijkstra算法的原理、实现方法（优先队列优化）以及应用场景，例如求解非负权图中的单源最短路径问题。
2. SPFA算法与负权边处理：介绍SPFA算法的原理、实现方法以及应用场景，例如求解存在负权边情况下的单源最短路径问题。
3. Dijkstra算法与SPFA算法的比较：分析Dijkstra算法和SPFA算法的优缺点，以及各自适用的场景。

第六讲：最小生成树问题 @Online Feb 17 19:00-20:00

讲义链接：最小生成树问题

1. 并查集：讲解并查集的原理
2. Kruskal算法与贪心策略：讲解Kruskal算法的原理、实现方法（并查集优化）以及应用场景，例如求解最小生成树问题。
3. Prim算法与优先队列：介绍Prim算法的原理、实现方法（优先队列优化）以及应用场景，例如求解最小生成树问题。
4. Kruskal算法与Prim算法的比较：分析Kruskal算法和Prim算法的优缺点，以及各自适用的场景。