ACM_1!-ACM必须掌握的算法
17页1、ACM 必须的算法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 解决问题的特征 负边权最
2、短路径 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
3、定理计算几何 / 解析几何计算几何的核心:叉积 / 面积 解析几何的主力:复数基本形 点 直线,线段 多边形凸多边形 / 凸包 凸包算法的引进,卷包裹法 Graham 扫描法 水平序的引进,共线凸包的补丁完美凸包算法相关判定 两直线相交 两线段相交 点在任意多边形内的判定 点在凸多边形内的判定经典问题 最小外接圆 近似 O(n)的最小外接圆算法 点集直径 旋转卡壳,对踵点 多边形的三角剖分数学 / 数论最大公约数 Euclid 算法 扩展的 Euclid 算法 同余方程 / 二元一次不定方程 同余方程组线性方程组 高斯消元法 解 mod 2 域上的线性方程组 整系数方程组的精确解法矩阵 行列式的计算 利用矩阵乘法快速计算递推关系分数 分数树 连分数逼近数论计算 求 N 的约数个数 求 phi(N) 求约数和 快速数论变换 素数问题 概率判素算法 概率因子分解数据结构组织结构 二叉堆 左偏树 二项树 胜者树 跳跃表 样式图标 斜堆 reap统计结构 树状数组 虚二叉树 线段树 矩形面积并 圆形面积并 关系结构 Hash 表 并查集 路径压缩思想的应用STL 中的数据 结构 vector
4、deque set / map动态规划 / 记忆化搜索动态规划和记忆化搜索在思考方式上的区别最长子序列系列问题 最长不下降子序列 最长公共子序列 最长公共不下降子序列一类 NP 问题的动态规划解法树型动态规划背包问题 动态规划的优化 四边形不等式 函数的凸凹性 状态设计 规划方向线性规划常用思想二分 最小表示法串KMP Trie 结构 后缀树/后缀数组 LCA/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)最小割模型、网络流规约(poj330
《ACM_1!-ACM必须掌握的算法》由会员壹****1分享,可在线阅读,更多相关《ACM_1!-ACM必须掌握的算法》请在金锄头文库上搜索。
水泥生产线DCS培训仿真系统-熟料配料环节
基站代维服务方案
2020{酒类营销}公司聘用合同书
关于员工大会发言稿9篇
电气工程1kv及以下工程规范分析
前几天学习了关于教师人文素养培育与研究方面的文章
市场部规章制度范文
《六安市优化营商环境条例(征求意见稿)》
消防工程施工技术交底16269
2017版高考化学一轮复习真题专训第七章化学反应速率和化学平衡基次时1化学反应速率及其影响因素新人教版
2014年重庆市开县丰乐中学小升初数学试卷
《古建筑修缮工程施工规程》(DOC 38页)
客服试用期转正述职报告.doc
政治理论学习心得体会
孩子的表扬信范文五篇
社区医生2023年个人工作总结范本.doc
关于劳动合同汇总十篇
基坑土石方开挖作业安全技术措施
2023年保险公司员工辞职报告范文
邮政职工五四青年节演讲稿与部队军官建军节演讲稿
2024-04-30 11页
2024-04-30 8页
2024-04-28 3页
2024-04-28 7页
2024-04-28 8页
2024-04-28 5页
2024-04-28 3页
2024-04-28 4页
2024-04-28 4页
2024-04-25 30页