Posted on 2006-08-13 17:58
oyjpart 阅读(805)
评论(4) 编辑 收藏 引用
首先是理论学习 对ACM拿到概要性的把握
1、离散数学——作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。
2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这部分在竞赛中的比重并不大，但只要来上一道，也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识确定大概的过程之后，核心算法往往要涉及数论的内容。
3、计算几何——较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大，但也永远不会成为最弱的题。
4、线性代数——对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。
先说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的，至于树，我个人觉得需要建树的问题有但是并不多。（但是树往往是很重要的分析工具）除此之外，排序和查找并不需要对所有方式都能很熟练的掌握，但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案。说到时间复杂度，就又该说说哈希表了，竞赛时对时间的限制远远多于对空间的限制，这要求大家尽快掌握“以空间换时间”的原则策略，能用哈希表来存储的数据一定不要到时候再去查找，如果实在不能建哈希表，再看看能否建二叉查找树等等——这都是争取时间的策略，掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感性认识。
接着说说算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。
常用算法中的另一类是以“相似或相同子问题”为核心的，包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划，如何抽象出重复的子问题是很多题目的难点所在，笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法（比如Floyd-Warshall算法），并且多阅读一些定理的证明，这虽然不能有什么直接的帮助，但是长期坚持就会对思维很有帮助。
学到的最经典的话：
OI是好学生的游戏。
我对DP的提炼：
动态规划的性质：1。最优子结构--设计状态 2。无后效性--状态转移
动态规划的动机：1。利用递归的重叠子问题，进行记忆化求解。
2。把问题看作是多阶段决策过程，是动态规划的第二种情形。
个人对于DP中的阶段理解：
对于DP中的阶段 不仅仅存在与多阶段决策问题中， 比如矩阵链乘问题中 我们可以把d[i][j]中的j-i长度看成是阶段 这样就符合了阶段的存在性
如：
function matrix_chain_order(p)
{
for(i=1 to n) m[i,i]=0;
for(l=2 to n) //长度！
for(i=1 to n-l+1) //该长度下的首个matrix
{
j=i+l-1; //该长度下的末matrix
m[i,j]=无穷大; //求最小值设最大
for(k=i to j-1) //根据状态转移方程中的k来决定的
{
q=m[i,k]+m[k+1,j]+Pi-1PkPj //等与两子链的耗费加上此2子链乘之耗费
if(q<m[i,j])
{m[i,j]=q; s[i,k]=k;}
}
}
}
学习离散数学的理解
哈密顿回路:在图中找出一条包含所有结点的闭路，并且，出来起点和重点重合外，这条闭路所含结点是互不相同的 可以在多项式时间类判断一个回路是否是哈密顿回路 但目前没有算法直接解出哈密顿回路
欧拉回路，欧拉图：图G中包含其所有边的简单开路称为G的欧拉路径。图G中包含其所有边的简单闭路径称为欧拉有向图。这个其实就是我小学学的一笔划问题！我晕 ~
哈密顿回路,货郎担问题，集团问题，最小边覆盖问题（注意和路径覆盖的区别），等等很多问题都是NPC问题，NP完全问题（NPC问题，C代表complete）。NPC问题存在着一个令人惊讶的性质，即如果一个NPC 问题存在多项式时间的算法，则所有的NP问题都可以在多项式时间内求解，即P=NP成立！！
呵呵 记的起的就这么多啦~