华师一附中OI组

标题: ACMer必备知识 [打印本页]

作者: admin 时间: 2018-5-13 23:47
标题: ACMer必备知识
作者：赵旭
链接：https://www.zhihu.com/question/19719698/answer/13638265
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

图论路径问题 0/1边权最短路径 BFS 非负边权最短路径（Dijkstra）可以用Dijkstra解决问题的特征负边权最短路径 Bellman-Ford Bellman-Ford的Yen-氏优化差分约束系统 Floyd 广义路径问题传递闭包极小极大距离 / 极大极小距离 Euler Path / Tour 圈套圈算法混合图的 Euler Path / Tour Hamilton Path / Tour 特殊图的Hamilton Path / Tour 构造生成树问题最小生成树第k小生成树最优比率生成树 0/1分数规划度限制生成树连通性问题强大的DFS算法无向图连通性割点割边二连通分支有向图连通性强连通分支 2-SAT 最小点基有向无环图拓扑排序有向无环图与动态规划的关系二分图匹配问题一般图问题与二分图问题的转换思路最大匹配有向图的最小路径覆盖 0 / 1矩阵的最小覆盖完备匹配最优匹配稳定婚姻网络流问题网络流模型的简单特征和与线性规划的关系最大流最小割定理最大流问题有上下界的最大流问题循环流最小费用最大流 / 最大费用最大流弦图的性质和判定组合数学解决组合数学问题时常用的思想逼近递推 / 动态规划概率问题 Polya定理计算几何 / 解析几何计算几何的核心：叉积 / 面积解析几何的主力：复数基本形点直线，线段多边形凸多边形 / 凸包凸包算法的引进，卷包裹法 Graham扫描法水平序的引进，共线凸包的补丁完美凸包算法相关判定两直线相交两线段相交点在任意多边形内的判定点在凸多边形内的判定经典问题最小外接圆近似O(n)的最小外接圆算法点集直径旋转卡壳，对踵点多边形的三角剖分数学 / 数论最大公约数 Euclid算法扩展的Euclid算法同余方程 / 二元一次不定方程同余方程组线性方程组高斯消元法解mod 2域上的线性方程组整系数方程组的精确解法矩阵行列式的计算利用矩阵乘法快速计算递推关系分数分数树连分数逼近数论计算求N的约数个数求phi(N) 求约数和快速数论变换 …… 素数问题概率判素算法概率因子分解数据结构组织结构二叉堆左偏树二项树胜者树跳跃表样式图标斜堆 reap 统计结构树状数组虚二叉树线段树矩形面积并圆形面积并关系结构 Hash表并查集路径压缩思想的应用 STL中的数据结构 vector deque set / map 动态规划 / 记忆化搜索动态规划和记忆化搜索在思考方式上的区别最长子序列系列问题最长不下降子序列最长公共子序列最长公共不下降子序列一类NP问题的动态规划解法树型动态规划背包问题动态规划的优化四边形不等式函数的凸凹性状态设计规划方向线性规划常用思想二分最小表示法串 KMP Trie结构后缀树/后缀数组 LCA/RMQ 有限状态自动机理论排序选择/冒泡快速排序堆排序归并排序基数排序拓扑排序排序网络

欢迎光临华师一附中OI组 (http://hsyit.cn/)