AcWing算法基础课学习指南

基础算法

• 排序算法：快速排序、归并排序、堆排序等
• 二分查找：解决查找问题的高效算法
• 高精度计算：处理大整数的运算
• 前缀和与差分：优化数列操作
• 双指针算法：解决数组或链表相关问题
• 位运算：高效处理二进制数据
• 离散化：将离散数据映射到连续区间
• 区间合并：合并重叠区间

数据结构

• 链表与邻接表：存储图和树等数据结构
• 栈与队列：实现先进后出和先进先出操作
• 单调队列、单调栈：解决特定问题的高效数据结构
• KMP算法：字符串匹配算法
• Trie树：高效存储和检索字符串
• 并查集：维护集合关系
• 堆：实现优先队列
• Hash表：高效查找数据

搜索与图论

• DFS与BFS：图的遍历算法
• 拓扑排序：解决依赖关系问题
• 最短路算法：Dijkstra、Bellman-Ford等
• 最小生成树：Prim、Kruskal等算法
• 二分图：匹配、染色等问题
• 匈牙利算法：解决二分图最大匹配问题

数学知识

• 质数、约数：数论基础
• 欧拉函数：计算与n互质的数的个数
• 快速幂：高效计算幂运算
• 扩展欧几里得算法：求解不定方程
• 中国剩余定理：求解同余方程组
• 高斯消元：求解线性方程组
• 组合计数：排列组合、概率等
• 容斥原理：解决计数问题
• 简单博弈论：Nim游戏等

动态规划

• 背包问题：01背包、完全背包、多重背包等
• 线性DP：解决线性结构问题
• 区间DP：解决区间相关问题
• 计数类DP：解决计数问题
• 数位统计DP：解决与数位相关的DP问题
• 状态压缩DP：将状态压缩成二进制数进行DP
• 树形DP：在树上进行DP

其他

• 贪心算法
• 记忆化搜索