《ACM必须掌握的算法》
17页1、1. 最短路(Floyd、Dijstra,BellmanFord)2. 最小生成树(先写个prim,kruscal要用并查集,不好写)3. 大数(高精度)加减乘除4. 二分查找.(代码可在五行以内)5. 叉乘、判线段相交、然后写个凸包.6. BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简)7. 数学上的有:辗转相除(两行内),线段交点、多角形面积公式.8. 调用系统的qsort,技巧很多,慢慢掌握.9. 任意进制间的转换第二阶段:练习复杂一点,但也较常用的算法。:1.二分图匹配(匈牙利),最小路径覆盖 2.网络流,最小费用流。3.线段树.4.并查集。5.熟悉动态规划的各个典型:LCS最长 递增子串、三角剖分、记忆化 dp 6.博弈类算法。博弈树,二进制法 等。7.最大团,最大独立集。8.判断点在多边形内。9.差分约束 系统.10.双向广度搜索、A*算法,最小耗散优先.相关的知识图论:路径问题0/1边权最短路径BFS非负边权最短路径(Dijkstra )可以用Dijkstra 解决问题的特征负边权最短路径Bellman-Ford Bellman-Ford 的 Yen-氏优化差
2、分约束系统 Floyd 广义路径问题传递闭包极小极大距离/极大极小距离EulerPath / Tour圈套圈算法 混合图的Euler Path / TourHamilton Path / Tour特殊图的 Hamilton Path / Tour 构造生成树问题最小生成树第k小生成树最优比率生成树0/1分数规划 度限制生成树 连通性问题 强大的DF晦法 无向图连通性割点割边二连通分支有向图连通性强连通分支2-SAT最小点基 有向无环图拓扑排序有向无环图与动态规划的关系二分图匹配问题 一般图问题与二分图问题的转换思路最大匹配有向图的最小路径覆盖0 / 1 矩阵的最小覆盖完备匹配最优匹配稳定婚姻网络流问题网络流模型的简单特征和与线性规划的关系最大流最小割定理最大流问题有上下界的最大流问题循环流最小费用最大流/最大费用最大流弦图的性质和判定组合数学解决组合数学问题时常用的思想逼近递推/动态规划概率问题Polya定理计算几何/解析几何计算几何的核心:叉积/面积解析几何的主力:复数基本形点直线,线段多边形凸多边形/凸包凸包算法的引进,卷包裹法Graham扫描法水平序的引进,共线凸包的补丁完美凸包
3、算法相关判定两直线相交两线段相交点在任意多边形内的判定点在凸多边形内的判定经典问题最小外接圆近似O(n)的最小外接圆算法点集直径旋转卡壳,对踵点多边形的三角剖分数学/数论最大公约数Euclid 算法扩展的Euclid算法同余方程/二元一次不定方程 同余方程组线性方程组高斯消元法解mod 2域上的线性方程组整系数方程组的精确解法矩阵行列式的计算利用矩阵乘法快速计算递推关系分数分数树连分数逼近数论计算求N的约数个数求 phi(N)求约数和快速数论变换素数问题概率判素算法 概率因子分解数据结构组织结构二叉堆左偏树二项树胜者树跳跃表样式图标斜堆reap统计结构树状数组虚二叉树线段树矩形面积并圆形面积并关系结构Hash 表并查集路径压缩思想的应用STL中的数据结构vectordequeset / map动态规划/记忆化搜索动态规划和记忆化搜索在思考方式上的区别最长子序列系列I可题最长不下降子序列最长公共子序列最长公共不下降子序列一类NP问题的动态规划解法树型动态规划 背包问题动态规划的优化四边形不等式函数的凸凹性状态设计规划方向线性规划常用思想二分最小表示法串KMPTrie结构后缀树/后缀数组L
4、CA/RMQ有限状态白动机理论排序选择/冒泡快速排序堆排序归并排序基数排序拓扑排序排序网中级:一. 基本算法:(1) C+的标准模版库的应用.(poj3096,poj3007)(2) 较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)二. 图算法:(1) 差分约束系统的建立和求解.(poj1201,poj2983)(2) 最小费用最大流(poj2516,poj2516,poj2195)(3) 双连通分量(poj2942)(4) 强连通分支及其缩点.(poj2186)(5) 图的割边和割点(poj3352)(6) 最小割模型、网络流规约(poj3308,)三. 数据结构.(1) 线段树.(poj2528,poj2828,poj2777,poj2886,poj2750)(2) 静态二叉检索树.(poj2482,poj2352)(3) 树状树组(poj1195,poj3321)(4) RMQ. (poj3264,poj3368)(5) 并查集的高级应用.(poj1703,2492)(6) KMP 算法.(poj1961,poj2406)四
《《ACM必须掌握的算法》》由会员tang****xu6分享,可在线阅读,更多相关《《ACM必须掌握的算法》》请在金锄头文库上搜索。
学校安全宣传教育培训记录台帐
心肺复苏术常见并发症的预防与处理规范
教学培训工作反思总结范文_工作培训总结范文
应急预案(完成)(doc4页)
实施积极的财政政策促进经济社会平稳较快发展
幼儿园常规卫生保健内容
幼儿教师的职业道德规范标准[幼儿园教职工职业道德规范]
教师入职职业生涯规划范文(标准版)
小学数学教材中环境教育渗透分析
少先队规范化队室建设规范
学校领导班子工作总结范本_学校领导季度工作总结
小学万师访万家活动总结_万师访万家记录表范文
山西省煤矿建设工程施工管理规范
抗战电影《喋血孤城》观后感范文
小学生习作现状分析及策略
护理实习生实习总结报告(精编版)22611
教师继续教育培训学习总结_继续教育工作总结
幼儿园保健医生个人工作总结_医生个人工作总结
幼儿园保健医岗位职责(精编版)
家庭教育中良好习惯的养成
2024-04-18 4页
2024-04-18 2页
2024-04-18 2页
2024-04-18 2页
2024-04-18 5页
2024-04-18 2页
2024-04-18 4页
2024-04-18 3页
2024-04-18 2页
2024-04-18 2页