acm要学的内容(转载踏雪赤兔's BLOG)

//------------------------------
给我一年时间, 把你们都搞
定, 呵呵, 做个好梦先!~
------------------------------//

图论

路径问题

最短路径

0/1 边权最短路径

BFS

非负边权最短路径

Dijkstra

u 可以用Dijkstra解决的问题的特征

负边权最短路径

Bellman-Ford

u Bellman-Ford的Yen-氏优化

u 差分约束系统

Floyd

u 广义路径问题

u 传递闭包

u 极小极大距离 / 极大极小距离

Euler Path / Tour

圈套圈算法

混合图的 Euler Path / Tour

Hamilton Path / Tour

特殊图的Hamilton Path / Tour 构造

生成树问题

最小生成树

第k小生成树

最优比率生成树

u 0/1分数规划

度限制生成树

连通性问题

u 强大的DFS算法

无向图连通性

割点

割边

二连通分支

有向图连通性

强连通分支

u 2-SAT

u 最小点基

有向无环图

拓扑排序

u 有向无环图与动态规划的关系

二分图匹配问题

u 一般图问题与二分图问题的转换思路

最大匹配

u 有向图的最小路径覆盖

u 0 / 1矩阵的最小覆盖

完备匹配

最优匹配

网络流问题

u 网络流模型的简单特征和与线性规划的关系

最大流最小割定理

最大流问题

有上下界的最大流问题

u 循环流

最小费用最大流 / 最大费用最大流

弦图的性质和判定

组合数学

u 解决组合数学问题时常用的思想

u 逼近

u 递推 / 动态规划

概率问题

Polya 定理

计算几何 / 解析几何

u 计算几何的核心：叉积 / 面积

u 解析几何的主力：复数

基本形

点

直线，线段

多边形

凸多边形 / 凸包

u 凸包算法的引进，卷包裹法

Graham 扫描法

u 水平序的引进，共线凸包的补丁

完美凸包算法

相关判定

两直线相交

两线段相交

点在任意多边形内的判定

点在凸多边形内的判定

经典问题

最小外接圆

近似O(n)的最小外接圆算法

点集直径

旋转卡壳，对踵点

多边形的三角剖分

数学 / 数论

最大公约数

Euclid 算法

扩展的Euclid算法

同余方程 / 二元一次不定方程

同余方程组

线性方程组

高斯消元法

u 解mod 2域上的线性方程组

u 整系数方程组的精确解法

矩阵

行列式的计算

u 利用矩阵乘法快速计算递推关系

分数

分数树

连分数逼近

数论计算

求N的约数个数

求phi(N)

求约数和

……

素数问题

概率判素算法

概率因子分解

数据结构：

组织结构

二叉堆

左偏树

胜者树

Treap

统计结构

树状数组

虚二叉树

线段树

u 矩形面积并

u 圆形面积并

关系结构

Hash 表

并查集

u 路径压缩思想的应用

STL 中的数据结构

vector

deque

set / map

动态规划 / 记忆化搜索

u 动态规划和记忆化搜索在思考方式上的区别

最长子序列系列问题

最长不下降子序列

最长公共子序列

一类NP问题的动态规划解法

树型动态规划

背包问题

动态规划的优化

u 四边形不等式

u 状态设计

u 规划方向（？）

常用思想

二分

最小表示法

posted on 2006-08-17 23:44 豪阅读(1040) 评论(3) 编辑收藏引用所属分类: 算法&ACM

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 用stl打spfa短了1k代码，慢了200ms 三次样条插值龙贝格积分2457jlu 三分法求函数极值buaa1024 为了大作业报告好写点，重写了RBTree 扩展的欧拉函数 pku1091 连分数学习笔记中国剩余定理(同余方程组)小结解模线性方程小结好久没写了.

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜