课程简介

本课程分为三个部分：

语法部分：讲解竞赛与笔试面试中常用的 C++语法知识与实用技巧。

算法基础：系统讲解基础算法与数据结构的 原理，并给出相应 代码模板。

算法提高：系统讲解常用算法与数据结构的 应用方式与技巧。

知识点

语法基础：

1. 变量、表达式与顺序语句
2. scanf/printf语法及判断语句
3. 循环语句
4. 数组
5. 字符串
6. 函数
7. 结构体、类、指针与引用
8. STL容器、位运算与常用库函数

算法基础：

1. 基础算法 —— 代码模板链接 常用代码模板1——基础算法

   • 排序
   • 二分
   • 高精度
   • 前缀和与差分
   • 双指针算法
   • 位运算
   • 离散化
   • 区间合并

2. 数据结构 —— 代码模板链接 常用代码模板2——数据结构

   • 链表与邻接表：树与图的存储
   • 栈与队列：单调队列、单调栈
   • kmp
   • Trie
   • 并查集
   • 堆
   • Hash表

3. 搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论

   • DFS与BFS
   • 树与图的遍历：拓扑排序
   • 最短路
   • 最小生成树
   • 二分图：染色法、匈牙利算法

4. 数学知识 —— 代码模板链接 常用代码模板4——数学知识

   • 质数
   • 约数
   • 欧拉函数
   • 快速幂
   • 扩展欧几里得算法
   • 中国剩余定理
   • 高斯消元
   • 组合计数
   • 容斥原理
   • 简单博弈论

5. 动态规划

   • 背包问题
   • 线性DP
   • 区间DP
   • 计数类DP
   • 数位统计DP
   • 状态压缩DP
   • 树形DP
   • 记忆化搜索

6. 贪心

7. 时空复杂度分析

算法提高：

1. 动态规划——从集合角度考虑DP问题

   • 1.1 数字三角形模型
   • 1.2 最长上升子序列模型
   • 1.3 背包模型
   • 1.4 状态机模型
   • 1.5 状态压缩DP
   • 1.6 区间DP
   • 1.7 树形DP
   • 1.8 数位DP
   • 1.9 单调队列优化的DP问题
   • 1.10 斜率优化的DP问题

2. 搜索

   • 2.1 BFS
   • 2.1.1 Flood Fill
   • 2.1.2 最短路模型
   • 2.1.3 多源BFS
   • 2.1.4 最小步数模型
   • 2.1.5 双端队列广搜
   • 2.1.6 双向广搜
   • 2.1.7 A*
   • 2.2 DFS
   • 2.2.1 连通性模型
   • 2.2.2 搜索顺序
   • 2.2.3 剪枝与优化
   • 2.2.4 迭代加深
   • 2.2.5 双向DFS
   • 2.2.6 IDA*

3. 图论

   • 3.1.1 单源最短路的建图方式
   • 3.1.2 单源最短路的综合应用
   • 3.1.3 单源最短路的扩展应用
   • 3.2 floyd算法及其变形
   • 3.3.1 最小生成树的典型应用
   • 3.3.2 最小生成树的扩展应用
   • 3.4 SPFA求负环
   • 3.5 差分约束
   • 3.6 最近公共祖先
   • 3.7 有向图的强连通分量
   • 3.8 无向图的双连通分量
   • 3.9 二分图
   • 3.10 欧拉回路和欧拉路径
   • 3.11 拓扑排序

4. 高级数据结构

   • 4.1 并查集
   • 4.2 树状数组
   • 4.3.1 线段树（一）
   • 4.3.2 线段树（二）
   • 4.4 可持久化数据结构
   • 4.5 平衡树——Treap
   • 4.6 AC自动机

5. 数学知识

   • 5.1 筛质数
   • 5.2 分解质因数
   • 5.3 快速幂
   • 5.4 约数个数
   • 5.5 欧拉函数
   • 5.6 同余
   • 5.7 矩阵乘法
   • 5.8 组合计数
   • 5.9 高斯消元
   • 5.10 容斥原理
   • 5.11 概率与数学期望
   • 5.12 博弈论

6. 基础算法

   • 6.1 位运算
   • 6.2 递归
   • 6.3 前缀和与差分
   • 6.4 二分
   • 6.5 排序
   • 6.6 RMQ