BYR Achieve · 镜像论坛

ACM的算法 (转载)

2007/11/22镜像同步1 回复

【以下文字转载自 ACM_ICPC 讨论区】发信人: namespace (dev c++), 信区: ACM_ICPC 标题: ACM的算法发信站: 北邮人论坛 (Tue Nov 20 19:34:48 2007), 站内鉴于论坛上一些同学的要求,现在我根据我个人的经验,整理了ACM入门大纲,这也可能会成为我们下学期校选拔的题目范围,但是主要目的是给大家指引一个方向,方便大家练习.同时由于我个人的能力有限,学习的知识面也不全,所以以下的分类会随时有所修整,还请大家多多包含.由于近期本人有各种考试各种作业各种实验三座大山的压迫,相应的题目只能在空闲的时候整理,但也会尽快贴出,可以先参考去年的五十题进行练习,同时希望练习的同学也自己勤于查资料,以更好的学习和掌握算法. 初期: 一.基本算法: (1)枚举. (2)贪心. (3)递归和分治法. (4)递推. 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd) (3)最小生成树算法(prim,kruskal) (4)拓扑排序 (5)二分图的最大匹配 (6)最大流的增广路算法. 三.数据结构. (1)串 (2)排序 (3)简单并查集的应用. (4)哈希表 (5)哈夫曼树 (6)堆 (7)trie树四.简单搜索 (1)深度优先搜索 (2)广度优先搜索 (3)简单搜索技巧和剪枝五.动态规划 (1)背包问题. (2)型如下表的简单DP(可参考lrj的书 page149): 1.E[j]=opt{D[i]+w(i,j)} 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 1.加法原理和乘法原理. 2.排列组合. 3.递推关系. (2)数论. 1.素数与整除问题 2.进制位. 3.同余模运算. (3)计算方法. 1.二分法求解单调函数相关知识. 七.计算几何学. (1)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (2)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) (3)凸包.

订阅后，新回复会通过你的通知中心匿名送达。