ACMer需要掌握的算法讲解 (2).docx

ACM算法讲解 本文将对ACM主要算法进行讲解，涵盖了基本算法、图算法、数据结构、搜索、计算几何学、动态规划和综合题等多方面的知识点。 一、基本算法 * 枚举算法：POJ1753、POJ2965 * 贪心算法：POJ1328、POJ2109、POJ2586 * 递归和分治法 * 递推算法 * 构造法：POJ3295、POJ3259、POJ1062、POJ2253、POJ1125、POJ2240 * 最小生成树算法：prim、kruskal、POJ1789、POJ2485、POJ1258、POJ3026 * 拓扑排序：POJ1094 * 串算法：POJ1035、POJ3080、POJ1936 * 哈希表和二分查找等高效查找法：POJ3349、POJ3274、POJ2151、POJ1840、POJ2002、POJ2503 * 哈夫曼树：POJ3253 * 背包问题：POJ1837、POJ1276 * DP算法：POJ3267、POJ1836、POJ1260、POJ2533 二、图算法 * 度限制最小生成树和第K最短路：POJ1639、POJ3216、POJ2446 * 最优比率生成树：POJ2728 * 最小树形图：POJ3164 * 次小生成树 * 无向图、有向图的最小环 三、数据结构 * RMQ：POJ3264、POJ3368 * 并查集的高级应用：POJ1703、POJ2492 * KMP算法：POJ1961、POJ2406 * 左偏树（可合并堆） 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划：POJ1191、POJ1054、POJ3280、POJ2029、POJ2948、POJ1925、POJ3034 * 记录状态的动态规划：POJ3254、POJ2411、POJ1185 * 树型动态规划：POJ2057、POJ1947、POJ2486、POJ3140 五、计算几何学 * 坐标离散化：POJ3429 * 代码快速写成，精简但不失风格：POJ2525、POJ1684、POJ1421、POJ1048、POJ2050、POJ3306 * 保证正确性和高效性：POJ3434 六、动态规划 * 需要用数据结构优化的动态规划：POJ2754、POJ3378、POJ3017 * 四边形不等式理论 * 组合数学 * 博奕论 * 对踵点：POJ2079 七、综合题 * POJ3109、POJ1478、POJ1462、POJ2729、POJ2048、POJ3336、POJ3315、POJ2148、POJ1263 八、附录 * ACM算法列表 + 哈希表、哈希数组 + 堆、优先队列 + 双端队列可并堆左偏堆 + Treap伸展树并查集 + 集合计数问题 + 二分图的识别 + 平衡二叉树 + 二叉排序树 + 线段树 + 一维线段树二维线段树树状数组 + 字典树 + 后缀数组、后缀树 + 块状链表 + 哈夫曼树