xfstart07
Get busy living or get busy dying

ACM/ICPC要求的知识点

注:下划线表示已会。

时间复杂度(渐近时间复杂度的严格定义,NP问题,时间复杂度的分析方法,主定理)

排序算法(平方排序算法的应用,Shell排序,快速排序归并排序,时间复杂度下界,三种线性时间排序,外部排序)

数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理)

指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示)

按位运算(and,or,xor,shl,shr,一些应用)

图论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种算法,标号法,差分约束系统,验证二分图,Konig定理,匈牙利算法,KM算法,稳定婚姻系统,最大流算法,最小割最大流定理,最小费用最大流算法)

计算几何(平面解几及其应用,向量,点积及其应用,叉积及其应用,半平面相交,求点集的凸包,最近点对问题,凸多边形的交,离散化与扫描)

数据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,斜堆,二项堆,二叉查找树,AVL,Treap,Splay,静态二叉查找树,2-d树,线段树,二维线段树,矩形树,Trie树,块状链表)

组合数学(排列与组合,鸽笼原理,容斥原理,递推,Fibonacci数列,Catalan数列,Stirling数,差分序列,生成函数,置换,Polya原理)

概率论(简单概率,条件概率,Bayes定理,期望值)

矩阵(矩阵的概念和运算,二分求解线性递推方程,多米诺骨牌棋盘覆盖方案数,高斯消元)

字符串处理(KMP,后缀树,有限状态自动机,Huffman编码,简单密码学)

动态规划(单调队列,凸完全单调性,树型动规,多叉转二叉,状态压缩类动规,四边形不等式)

博奕论(Nim取子游戏,博弈树,Shannon开关游戏)

搜索(A*,ID,IDA*,随机调整,遗传算法)

微积分初步(极限思想,导数,积分,定积分,立体解析几何)

1. ACM/lCPC要求的数据结构知识点:

(1) 单双链表及循环链表;

(2) 树的表示与存储,二叉树(概念,遍历);

(3) 二叉树的应用(二叉排序树,判定树,博弈树,解答树等);

(4) 文件操作(从文本文件中读人数据,并输出到文本文件中;

(5) 图 (基本概念,存储结构,图的运算);

ACM/ICPC要求学生对这些知识点非常熟悉。

2. ACM/ICPC要求的基础数学知识点

离散数学知识的应用(如排列组合、简单图论、数理逻辑)、数论知识、线性代数、组合数学、计算几何。

3. ACM/ICPC要求的算法设计知识点

排序算法 (冒泡法、插入排序、归并排序、快速排序、堆排序)、
查找(顺序查找、二分法)、回溯算法、递归算法、分治思想、模拟法、贪心法、
简单搜索算法(深度优先,广度优先)、
搜索中的剪枝、A*算法、
动态规划的思想及基本算法、高精度运算。

转自互相网

posted on 2010-08-12 22:07 xfstart07 阅读(309) 评论(0)  编辑 收藏 引用 所属分类: MyLife算法学习

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理