Acm应掌握算法
6页1、第一阶段:练经典常用算法下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 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*算法,最小耗散优先. =
2、相关的知识 图论 路径问题 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矩阵的最小覆盖 完备匹配 最优匹配 稳定婚姻 网络流问题 网络流模型的简单特征和与线性规划的关系 最大流最小割定理 最大流问题 有上下界的最大流问题 循环流 最小费用最
《Acm应掌握算法》由会员世***分享,可在线阅读,更多相关《Acm应掌握算法》请在金锄头文库上搜索。
轻轻推开那扇门(想象作文)
苏教版语文《背影》说课稿
苏教版一年级道德与法治下册第六课 为你喝彩教案
粤教版活动课“少年情怀都是诗”说课稿
小班游戏公开课抢位教案
科学征文-科学让我们不再无知——读《天外探秘》有感
海我的目标(六年级下册作文)
高中第十一周国旗下讲话:自强不息做一名优秀的中学生
敬佩的一个人作文7篇
美丽的除夕夜(寒假作文)
学院开学典礼讲话--追求快乐放飞梦想
第六课第二框 学会调控情绪教学设计
电101班先进班集体事迹材料
送教下乡老师代表发言稿
读《猎犬暴雪》有感
雨夜的断章
珍惜资源爱我国土七年级作文600字
读郑杰的《一百条建议》的体会
暑假作文:吊兰
第三单元 第4课时《几和几》教学设计
2022-10-27 11页
2023-11-30 10页
2022-10-15 46页
2023-06-15 7页
2023-04-15 14页
2022-09-24 6页
2024-01-17 42页
2023-05-10 4页
2024-02-28 21页
2023-12-28 13页