2023年ACM知识点总结归纳分类1.pdf

《2023年ACM知识点总结归纳分类1.pdf》由会员分享，可在线阅读，更多相关《2023年ACM知识点总结归纳分类1.pdf（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习必备 欢迎下载 ACM 知识点分类 第一类：基础算法（1）基础算法：枚举，贪心，递归，分治，递推，构造，模拟（2）动态规划：背包问题，树形 dp，状态压缩 dp，单调性优化，插头 dp（3）搜索：dfs，bfs，记忆化搜索，优化与剪枝，双广，A*，IDA*，跳舞链 第二类：数据结构（1）简单数据结构：链表，栈和队列，串，树和二叉树，图，排序与检索（2）树形结构：线段树，树状数组，字典树，伸展树，左偏树，动态树，lca&rmq，划分树，SBT（3）字符串：kmp，AC 自动机，后缀数组，最小表示法（4）其他：并查集，散列表，块状链表，双向链表 第三类：图论（1）最短路：dijkstra,be

2、llman-ford(spfa优化),floyd,heap+dijkstra,差分约束，第 K 最短路（2）生成树：prim,kruskal,度限制最小生成树,最优比率生成树,次小生成树,最小树形图，生成树的计数，树的划分，树的枚举（3）匹配问题：二分图的最大匹配(匈牙利算法)，KM，2-SAT，同构（4）网络流：最大流，最小费用最大流，最小割模型、网络流规约（5）其他：拓扑排序，双连通分量，强连通分支及其缩点，图的割边与割点，无向图、有向图的最小环，欧拉路径，哈密顿路径，平面图，分层图思想，偶图 学习必备 欢迎下载 第四类：数学（1）数论：素数和整除问题，进位制，同余模算术，整数因子分解，G

3、CD，扩展欧几里得，求解模线性方程，中国余数定理，元素的幂，RSA 公钥加密（2）组合数学：加法和乘法原理，排列组合，递推关系和母函数，容斥原理，抽屉原理，置换群与 Polya 定理，MoBius反演，偏序关系理论（3）计算方法：二分法求解单调函数相关知识，三分法求解单峰(单谷)的极值，矩阵法，迭代逼近，高斯消元法，随机化算法，0/1 分数规划（4）高精度问题扩展：求倒数，求乘幂，求开方，求对数，二分快速方法，对指函数，三角函数，数值计算的优化（5）其他：博弈论，线性规划，整数规划，概率问题，多项式与快速傅里叶，数学思想与方法的综合运用（构造，猜想，归纳法，反证法）第五类：计算几何(1)判断线段相交，判断直线相交，判断点是否在多边形内，(2)凸多边形面积&重心计算，求外接圆与内接圆，(3)求凸包，最近点对问题，最远点对问题，(4)点集或图形集合的最小覆盖圆，点集或图形集合的最小覆盖矩形，(5)矩形的交与并（扫描法），(6)三角剖分，费尔马点的计算，Pick定理(7)常用几何公式 叉树图排序与检索树形结构线段树树状数组字典树伸展树左偏树动态树树次小生成树最小树形图生成树的计数树的划分树的枚举匹配问题二分环欧拉路径哈密顿路径平面图分层图思想偶图学习必备欢迎下载第四类