马牛的acm学习（第一天）－我找资源，我找～ - Manio - CSDN博客
我的图书馆
马牛的acm学习（第一天）－我找资源，我找～ - Manio - CSDN博客
我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛——ACM/ICPC。从这学期开始，学院计划有组织地进行训练和讲座，以帮助大家在有限的时间内尽可能多地提高自己的能力，这对有兴趣投入数据结构与算法研究的同学来说无疑是一件好事。但是，刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。
一、语言是最重要的基本功
无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不但需要花费更多的时间去编写代码，也会降低程序的执行效率。
接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。
而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。
C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法；另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。
通过以上的分析，我们可以看出仅就信息学竞赛而言，对语言的掌握并不要求十分全面，但是对于经常用到的部分，必须十分熟练，不允许有半点不清楚的地方，下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍，都有可能酿成错误：
在去年清华的赛区上，有一个队在做F题的时候使用了cout和printf的混合输出，由于一个带缓冲一个不带，所以输出一长就混乱了。只是因为当时 judge team中负责F题的人眼睛尖，看出答案没错只是顺序不对（答案有一页多，是所有题目中最长的一个输出），又看了看程序发现只是输出问题就给了个 Presentation error（格式错）。如果审题的人不是这样而是直接给一个 Wrong Answer，相信这个队是很难查到自己错在什么地方的。
现在我们转入第二个方面的讨论，基础学科知识的积累。
二、以数学为主的基础知识十分重要
虽然被定性为程序设计竞赛，但是参赛选手所遇到的问题更多的是没有解决问题的思路，而不是有了思路却死活不能实现，这就是平时积累的基础知识不够。今年 World Final的总冠军是波兰华沙大学，其成员出自于数学系而非计算机系，这就是一个鲜活的例子。竞赛中对于基础学科的涉及主要集中于数学，此外对于物理、电路等等也可能有一定应用，但是不多。因此，大一的同学也不必为自己还没学数据结构而感到不知从何入手提高，把数学捡起来吧！下面我来谈谈在竞赛中应用的数学的主要分支。
1、离散数学——作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。
图论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许多算法的基本思想，较多用到的知识包括连通性判断、DFS和BFS，关节点和关键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大，但是往往也是竞赛中的难题所在，如果有初学者对于这部分的某些具体内容暂时感到力不从心，也不必着急，可以慢慢积累。
竞赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于图论要简单一些，很多知识对于小学上过奥校的同学来说已经十分熟悉，但是也有一些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现，但是如果积累不够，任何一道这方面的题目却都有可能成为难题。
2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这部分在竞赛中的比重并不大，但只要来上一道，也足以使知识不足的人冥思苦想上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识确定大概的过程之后，核心算法往往要涉及数论的内容。
3、计算几何——计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大，但也永远不会成为最弱的题。
4、线性代数——对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。
5、概率论——竞赛是以黑箱来判卷的，这就是说你几乎不能动使用概率算法的念头，但这也并不是说概率就没有用。关于这一点，只有通过一定的练习才能体会。
6、初等数学与解析几何——这主要就是中学的知识了，用的不多，但是至少比高等数学多，我觉得熟悉一下数学手册上的相关内容，至少要知道在哪儿能查到，还是必要的。
7、高等数学——纯粹运用高等数学来解决的题目我接触的只有一道，但是一些题目的叙述背景往往需要和这部分有一定联系，掌握得牢固一些总归没有坏处。
以上就是竞赛所涉及的数学领域，可以说范围是相当广的。我认识的许多人去搞信息学的竞赛就是为了逼着自己多学一点数学，因为数学是一切一切的基础。
三、数据结构与算法是真正的核心
虽然数学十分十分重要，但是如果让三个只会数学的人参加比赛，我相信多数情况下会比三个只会数据结构与算法的人得到更为悲惨的结局。
先说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的，至于树，我个人觉得需要建树的问题有但是并不多。（但是树往往是很重要的分析工具）除此之外，排序和查找并不需要对所有方式都能很熟练的掌握，但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案。说到时间复杂度，就又该说说哈希表了，竞赛时对时间的限制远远多于对空间的限制，这要求大家尽快掌握“以空间换时间”的原则策略，能用哈希表来存储的数据一定不要到时候再去查找，如果实在不能建哈希表，再看看能否建二叉查找树等等——这都是争取时间的策略，掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感性认识。
接着说说算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。
常用算法中的另一类是以“相似或相同子问题”为核心的，包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划，如何抽象出重复的子问题是很多题目的难点所在，笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法（比如Floyd-Warshall算法），并且多阅读一些定理的证明，这虽然不能有什么直接的帮助，但是长期坚持就会对思维很有帮助。
四、团队配合
通过以上的介绍大家也可以看出，信息学竞赛对于知识面覆盖的非常广，想凭一己之力全部消化这些东西实在是相当困难的，这就要求我们尽可能地发挥团队协作的精神。同组成员之间的熟练配合和默契的形成需要时间，具体的情况因成员的组成不同而不同，这里我就不再多说了。
五、练习、练习、再练习
知识的积累固然重要，但是信息学终究不是看出来的，而是练出来的，这是多少前人最深的一点体会，只有通过具体题目的分析和实践，才能真正掌握数学的使用和算法的应用，并在不断的练习中增加编程经验和技巧，提高对时间复杂度的感性认识，优化时间的分配，加强团队的配合。总之，在这里光有纸上谈兵是绝对不行的，必须要通过实战来锻炼自己。
大家一定要问，我们去哪里找题做，又如何检验程序是否正确呢？这大可不必担心，现在已经有了很多网上做题的站点，这些站点提供了大量的题库并支持在线判卷，你只需要把程序源码提交上去，马上就可以知道自己的程序是否正确，运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点，笔者不建议大家在所有这些站点上做题，选择一个就可以了，因为每个站点的题都有一定的难易比例，系统地做一套题库可以使你对各种难度、各种类型的题都有所认识。
Ural是中国学生对俄罗斯的Ural州立大学的简称 ，那里设立了一个Ural Online Problem Set，并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强，得到了国内广大学生的厚爱。根据“信息学初学者之家”网站的统计，Ural的题目类型大概呈如下的分布：
题型 搜索 动态规划 贪心 构造 图论 计算几何 纯数学问题 数据结构 其它 所占比例 约10% 约15% 约5% 约5% 约10% 约5% 约20% 约5% 约25%
这和实际比赛中的题型分布也是大体相当的。有兴趣的朋友可以去看看。
UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ，并且支持ONLINE JUDGE，形式和Ural大学的题库类似。不过和Ural不同的是，UVA题目多的多，而且比较杂，而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从，要么难以找到合适的题目，要么Wrong Answer了很多次以后仍然不知道错在那里。如果说做Ural题目主要是为了训练算法，那么UVA题目可以训练全方位的基本功和一些必要的编程素质。UVA和许多世界知名大学联合办有同步网上比赛，因此那里强人无数，不过你先要使自己具有听懂他们在说什么的素质：）
ZOJ是浙江大学建立的ONLINE JUDGE，是中国大学建立的第一个同类站点，也是最好和人气最高的一个，笔者和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站，但是这里的中国学生比较多，因此让人觉得很亲切。这里目前有500多道题目，难易分配适中，且涵盖了各大洲的题目类型并配有索引，除此之外，ZOJ的JUDGE 系统是几个网站中表现得比较好的一个，很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛，只要是注册的用户都可以参加。
说起中国的ONLINE JUDGE，去年才开始参加ACM竞赛的北京大学现在也建立了自己的提交系统；而我们学校也是去年开始参加比赛，现在也有可能推出自己的提交系统，如果能够做成，到时候大家就可以去上面做题了。同类网站的飞速发展标志着有越来越多的同学有兴趣进入信息学的领域探索，这是一件好事，同时也意味着更激烈的竞争，希望大家都能通过竞争锻炼自己、提高自己，并争取成为胜利者。　
版权声明：编程爱好者网站为此BLOG服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！ &
原文地址：
===========================================================================
学习网站：
===========================================================================
黄岩中学解题报告：福建信息学奥林匹克：EXACT STRING MATCHING ALGORITHMS：Game Theory Text ：icpc meets fau:rmatik.uni-erlangen.de/ICPC/rankings/sorted.xml?language=deIOI'2003 中国国家集训队训练:/ioi2003/信息学初学者之家：大榕树（荐！）：Jnu ACMer BBS 解题报告：USACO译题ShanTou University :: Online Contest Judgehttp://acm./index.htmlOI爱好者：极光炫影杭电题站 huicpc11http://acm./listproblem.php?vol=1online judgeTongji Online Judge Solutions 浙江大学ACM在线答题湖南大学ACM站北京大学ACM在线答题吉林大学的 Online Judge - 四川大学的 Online Judge -http://cs./acm汕头大学的 Online Judge -http://acm./中科大的 Online Judge -http://acm./index.php哈工大的 Online Judge -http://acm./acm.php西班牙的 Universidad de Valladolid -http://acm.uva.es/俄罗斯乌拉尔大学 -http://acm.timus.ru/
以下转自Myheimu's Blog==========================================================
Kogle.Net 信息学奥林匹克论坛 &&&
大榕树学生论坛 &&&
衡阳市八中信息学奥赛论坛&zju译题站 &&&
趣题之家 &&&
温州中学信息学奥赛基地 &&&
哈工大·纯Ｃ论坛 &&&
FZOI信息学论坛 &&&
fairfox问题征解论坛
水木风沙网论坛
合肥一中信息技术园 & 南通中学信息学奥林匹克
信息技术在线 -- 首页
中国教育曙光网--奥赛
算法与数据结构
中山纪念中学信息学竞赛教程
Kogle.Net 信息学奥林匹克总站
汕头信息学竞赛 & 巴蜀中学信息教育网
信息学资源
数据结构---学习网站
oibh.ioiforum.org
晋江市青少年计算机奥林匹克竞赛
、oi信息学奥赛网 & Dictionary of Algorithms and Data Structures
全国青少年科技创新活动服务平台xiaoxiaotong & The ACM Portal & 信息学奥赛[学生科技网] & 信息学奥赛试题集—http--www.oipc.net &&&& Pi to 1,000,000 places
高级编程&&&&& &&&
唯C世界 &&& & 问专家-编程 &&&
C 语言之家 &&&
CSDN.NET - 中国最大的开发者网络 &&&
VB新势力 &&&
c语言论坛 &&&
Delphi园地 &&&
Delphi开发者 &&& & Delphi K.Top討論區 &&&
编程先锋 VB-VB.NET,VC,C++,Delphi, 电子书籍 &&&
编程爱好者网站 &&&
编程中国-中国最大的编程网站 &&&
中国DOS联盟 &&&
漠寒楼-原创免费绿色软件+编程探讨 &&&
软硕网=中国软件工程硕士 官方性&&&
中国计算机学会 &&&
信息学奥林匹克 &&&
南京信息教研网 &&&
全国青少年科技创新活动服务平台 &&&
NOI2004官方网站 &&&
NOI2005 &网络题库&&& & TjU Problems.Programming Steps &&& & Pku Online Judge &&&
URAL题目翻译－厦门一中学生论坛 &&&
ACM-ICPC International Collegiate Programming Contest &&& & URAL Online Judge &&&
USACO Training Program Gateway &&&
USACO Translate译题 &&&
USACO译题 &&&
SGU& Saratov State University &&&
UVA PROBLEM SET ARCHIVE &&&
USACO讨论－衡阳市第八中学信息学奥赛论坛&zju译题站 &&&
ZJU Online Judge &&& & UVA讨论区--衡阳市第八中学信息学奥赛论坛 &&& & ZJU译题-衡阳市第八中学信息学奥赛论坛 &&&
哈工大的Online Judge
本文来自CSDN博客，转载请标明出处：
TA的最新馆藏[转]&[转]&[转]&[转]&[转]&[转]&
喜欢该文的人也喜欢2013年3月 C/C++大版内专家分月排行榜第三
2013年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第七
2012年1月 其他开发语言大版内专家分月排行榜第二2011年5月 其他开发语言大版内专家分月排行榜第二2010年12月 其他开发语言大版内专家分月排行榜第二2009年2月 其他开发语言大版内专家分月排行榜第二2008年9月 其他开发语言大版内专家分月排行榜第二2008年8月 其他开发语言大版内专家分月排行榜第二2008年5月 其他开发语言大版内专家分月排行榜第二2007年11月 其他开发语言大版内专家分月排行榜第二
2011年4月 其他开发语言大版内专家分月排行榜第三2011年1月 其他开发语言大版内专家分月排行榜第三2009年6月 其他开发语言大版内专家分月排行榜第三2009年4月 其他开发语言大版内专家分月排行榜第三2009年1月 其他开发语言大版内专家分月排行榜第三2008年11月 其他开发语言大版内专家分月排行榜第三2008年7月 其他开发语言大版内专家分月排行榜第三2008年6月 其他开发语言大版内专家分月排行榜第三2006年9月 其他开发语言大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。&&&&C语言程序设计——零基础ACM/ICPC竞赛实战指南&清华开发者书库
自营订单满39元（含）免运费
不足金额订单收取运费5元起
邀请好友参加吧
版 次：1页 数：字 数：印刷时间：日开 本：16开纸 张：胶版纸包 装：平装是否套装：否国际标准书号ISBN：2所属分类：&&&
下载免费当当读书APP
品味海量优质电子书，尊享优雅的阅读体验，只差手机下载一个当当读书APP
本商品暂无详情。
当当价：为商品的销售价，具体的成交价可能因会员使用优惠券、积分等发生变化，最终以订单结算页价格为准。
划线价：划线价格可能是图书封底定价、商品吊牌价、品牌专柜价或由品牌供应商提供的正品零售价（如厂商指导价、建议零售价等）或该商品曾经展示过的销售价等，由于地区、时间的差异化和市场行情波动，商品吊牌价、品牌专柜价等可能会与您购物时展示的不一致，该价格仅供您参考。
折扣：折扣指在划线价（图书定价、商品吊牌价、品牌专柜价、厂商指导价等）某一价格基础上计算出的优惠比例或优惠金额。如有疑问，您可在购买前联系客服咨询。
异常问题：如您发现活动商品销售价或促销信息有异常，请立即联系我们补正，以便您能顺利购物。
当当购物客户端手机端1元秒
当当读书客户端万本电子书免费读推荐这篇日记的豆列
&&&&&&&&&&&&谢邀，本弱ACM已经退役多时，只能凭借记忆分享一点浅薄的经验。：）&br&&br&&b&参考资料篇：&/b&&br&重点推荐刘汝佳三件套：&br&&b&算法竞赛入门经典&/b&&br&&figure&&img src=&/v2-bad_b.jpg& data-rawwidth=&300& data-rawheight=&300& class=&content_image& width=&300&&&/figure&&br&&b&算法竞赛训练指南&/b&&br&&figure&&img src=&/v2-eb38d12ce9e9abeeb7b72d9_b.jpg& data-rawwidth=&280& data-rawheight=&280& class=&content_image& width=&280&&&/figure&&br&&b&算法竞赛与信息学艺术&/b&&br&&figure&&img src=&/v2-d9ef4cbfb2047ffc4713f2_b.jpg& data-rawwidth=&212& data-rawheight=&300& class=&content_image& width=&212&&&/figure&&br&难度依次递增，紫书最先看，白书重点看，黑书可看可不看。&br&&br&&br&接下来是watashi大神鼎力推荐的&br&&h1&挑战程序设计竞赛&/h1&&figure&&img src=&/v2-4303dbaf81_b.jpg& data-rawwidth=&292& data-rawheight=&341& class=&content_image& width=&292&&&/figure&这本比较通俗易懂，但是代码风格比较另类。&br&&br&&br&至于Thomas H.Cormen、Charles E.Leiserson等合著的这本《&b&算法导论&/b&》对于初学者不推荐，但如果想要从最底层的数学原理上理解算法的话可以翻翻这部书。&br&&figure&&img src=&/v2-1bfb565b98bc3d488adcb542_b.jpg& data-rawwidth=&289& data-rawheight=&354& class=&content_image& width=&289&&&/figure&&br&&br&然后推荐几个比较好的blog：&br&&a href=&///?target=http%3A///& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&& - Home&i class=&icon-external&&&/i&&/a&
主要是关于OI的题解，非常全面&br&&a href=&///?target=http%3A///kuangbin/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&kuangbin - 博客园&i class=&icon-external&&&/i&&/a&&br&&a href=&///?target=http%3A//www.kuangbin.org/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&kuangbin博客 | TBD&i class=&icon-external&&&/i&&/a&&br&主要是关于ACM的题解，非常全面&br&&a href=&///?target=https%3A///& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&BYVoid&i class=&icon-external&&&/i&&/a&
郭家宝大神关于图论的博文都是不错的，不过最近画风好像转向旅游方面了。。&br&&a href=&///?target=http%3A///blog/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Matrix67: The Aha Moments&i class=&icon-external&&&/i&&/a& 关于数学方面&br&想到再补充。。。&br&&br&Online Judge：&br&关于ACM的：&br&杭电 &a href=&///?target=http%3A//acm./& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Welcome to Hangzhou Dianzi University Online Judge&i class=&icon-external&&&/i&&/a&&br&北大&a href=&///?target=http%3A//poj.org/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&& Welcome To PKU JudgeOnline&i class=&icon-external&&&/i&&/a&&br&浙大
&a href=&///?target=http%3A//acm./onlinejudge/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&ZOJ :: Home&i class=&icon-external&&&/i&&/a&&br&华科
&a href=&///?target=http%3A//acm./& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&HUSTOJ&i class=&icon-external&&&/i&&/a&&br&SPOJ
&a href=&///?target=http%3A///info/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&Sphere Online Judge (SPOJ)&i class=&icon-external&&&/i&&/a&&br&UVA
&a href=&///?target=https%3A//uva.onlinejudge.org/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&UVa Online Judge - Home&i class=&icon-external&&&/i&&/a&&br&SGU
&a href=&///?target=http%3A//acm.sgu.ru/& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://&/span&&span class=&visible&&acm.sgu.ru/&/span&&span class=&invisible&&&/span&&i class=&icon-external&&&/i&&/a&&br&关于OI的：&br&衡阳八中
&a href=&///?target=http%3A///JudgeOnline/wttl/thread.php%3Ftid%3D1294& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&大视野在线测评-欢迎您&i class=&icon-external&&&/i&&/a&&br&VIJOS
&a href=&///?target=https%3A//vijos.org/& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&首页 - Vijos&i class=&icon-external&&&/i&&/a&&br&RQNOJ
&a href=&///?target=http%3A///& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&&首页 - RQNOJ&i class=&icon-external&&&/i&&/a&&br&&br&&br&&br&&b&知识体系篇：&/b&&br&C语言+STL+数据结构+算法&br&C语言+STL略去不表，重点谈谈需要掌握的数据结构&&算法&br&参照hzwer巨巨的博文：&a href=&///?target=http%3A///& class=& wrap external& target=&_blank& rel=&nofollow noreferrer&& - Home&i class=&icon-external&&&/i&&/a&&br&我按照竞赛中考查的频率及重要性，暂且将对列出的知识点的掌握程度的要求分成熟练掌握、基本掌握、一般掌握、一般了解、可看可不看这五个等级。&blockquote&&p&简单列了一点&/p&
&p&1.1 基本数据结构&/p&
&p&1. 数组（熟练掌握）&/p&
&p&2. 链表，双向链表（熟练掌握）&/p&
&p&3. 队列，单调队列，双端队列（熟练掌握）&/p&
&p&4. 栈，单调栈（熟练掌握）&/p&
&p&1.2 中级数据结构&/p&
&p&1. 堆（熟练掌握）&/p&
&p&2. 并查集与带权并查集（熟练掌握）&/p&
&p&3. hash 表（基本掌握）&/p&
自然溢出&/p&
双hash&/p&
&p&1.3 高级数据结构&/p&
&p&1. 树状数组（基本掌握）&/p&
&p&2. 线段树，线段树合并（基本掌握）&/p&
&p&3. 平衡树（一般掌握&&一般了解）&/p&
Treap 随机平衡二叉树&/p&
Splay 伸展树&/p&
* Scapegoat Tree 替罪羊树&/p&
&p&4. 块状数组，块状链表（一般掌握）&/p&
&p&5.* 树套树（一般了解）&/p&
线段树套线段树&/p&
线段树套平衡树&/p&
* 平衡树套线段树&/p&
&p&6.可并堆（一般了解）&/p&
左偏树&/p&
*配对堆&/p&
&p&7. *KDtree，*四分树（一般了解）&/p&
&p&1.4 可持久化数据结构&/p&
&p&1. 可持久化线段树（一般了解）&/p&
主席树&/p&
&p&2. * 可持久化平衡树（一般了解）&/p&
&p&3. * 可持久化块状数组（一般了解）&/p&
&p&1.5 字符串相关算法及数据结构&/p&
&p&1. KMP（基本掌握）&/p&
&p&2. AC 自动机（基本掌握）&/p&
&p&3. 后缀数组（一般了解）&/p&
&p&4. *后缀树（一般了解）&/p&
&p&5. *后缀自动机（一般了解）&/p&
&p&6. 字典树 Trie（基本掌握）&/p&
&p&7. manacher（一般了解）&/p&
&p&1.6 图论相关&/p&
&p&1. 最小生成树（基本掌握）&/p&
kruskal&/p&
&p&2. 最短路，次短路，K短路（基本掌握）&/p&
dijkstra&/p&
&p&3. 图的连通（一般掌握）&/p&
连通分量&/p&
割点，割边&/p&
&p&4. 网络流（一般掌握）&/p&
最大流&/p&
最小割&/p&
费用流&/p&
分数规划&/p&
&p&5. 树相关（一般了解）&/p&
树上倍增，公共祖先&/p&
树链剖分&/p&
树的分治算法（点分治，边分治，*动态？树分治）&/p&
动态树 （LCT，*树分块）&/p&
*prufer编码&/p&
&p&7. 拓扑排序（熟练掌握）&/p&
&p&8. 欧拉图（一般掌握）&/p&
&p&9. 二分图（一般掌握）&/p&
*KM算法&/p&
匈牙利算法&/p&
&p&1.7 数学相关&/p&
&p&1. （扩展）欧几里得算法，筛法，快速幂（基本掌握）&/p&
斐蜀定理&/p&
更相减损术&/p&
&p&2. 欧拉函数与*降幂大法（一般掌握）&/p&
&p&3. 费马小定理（一般掌握）&/p&
&p&4. 排列组合（一般掌握）&/p&
lucas定理&/p&
&p&5. 乘法逆元（一般掌握）&/p&
&p&6. 矩阵乘法（基本掌握）&/p&
&p&7. 数学期望与概率（基本掌握）&/p&
&p&8. 博弈论（一般掌握）&/p&
sg函数&/p&
树上删边游戏&/p&
&p&9. *拉格朗日乘子法（可看可不看）&/p&
&p&10. 中国剩余定理（一般掌握）&/p&
&p&11. 线性规划与网络流（一般掌握）&/p&
&p&12. 单纯型线性规划（一般了解）&/p&
&p&13. 辛普森积分（一般了解）&/p&
&p&14. 模线性方程组（一般掌握）&/p&
&p&15. 容斥原理与莫比乌斯反演（一般了解）&/p&
&p&16. 置换群（一般了解）&/p&
&p&17. 快速傅里叶变换（一般了解）&/p&
&p&18. *大步小步法（BSGS），扩展BSGS（可看可不看）&/p&
&p&1.8 动态规划&/p&
&p&1. 一般，背包，状压，区间，环形，树形，数位动态规划（基本掌握）&/p&
记忆化搜索&/p&
斯坦纳树&/p&
背包九讲&/p&
&p&2. 斜率优化与* 四边形不等式优化（一般了解）&/p&
&p&3. 环 + 外向树上的动态规划（一般了解）&/p&
&p&4. *插头动态规划（一般了解）&/p&
&p&1.9 计算几何&/p&
&p&1. 计算几何基础（基本掌握）&/p&
&p&2. 三维计算几何初步（一般掌握）&/p&
&p&3. *梯形剖分与*三角形剖分（一般了解）&/p&
&p&4. 旋转卡壳（一般了解）&/p&
&p&5. 半平面交（一般了解）&/p&
&p&6. pick定理（一般了解）&/p&
&p&7. 扫描线（一般了解）&/p&
&p&1.10 搜索相关&/p&
&p&1. bfs，dfs（熟练掌握）&/p&
&p&2. A* 算法（基本掌握）&/p&
&p&3. 迭代加深搜索，双向广搜（基本掌握）&/p&
&p&1.11 特殊算法&/p&
&p&1. 莫队算法，*树上莫队（一般了解）&/p&
&p&2. 模拟退火（可看可不看）&/p&
&p&3. 爬山算法（可看可不看）&/p&
&p&4. 随机增量法（可看可不看）&/p&
&p&1.12 其它重要工具与方法&/p&
&p&1.模拟与贪心（熟练掌握）&/p&
&p&2. 二分，三分法（求偏导）（熟练掌握）&/p&
&p&3. 分治，CDQ分治（一般了解）&/p&
&p&4. 高精度（基本掌握）&/p&
&p&5. 离线（熟练掌握）&/p&
&p&6. ST表（一般掌握）&/p&
&p&1.13 STL&/p&
&p&1. map（熟练掌握）&/p&
&p&2. priority_queue（熟练掌握）&/p&
&p&3. set（熟练掌握）&/p&
&p&4. bitset（熟练掌握）&/p&
&p&5. rope（一般掌握）&/p&
&p&1.14 非常见算法&/p&
&p&1. *朱刘算法（可看可不看）&/p&
&p&2. *弦图与区间图（可看可不看）&/p&
&/blockquote&&br&&br&&br&&b&经验心得篇：&br&&/b&1. 队友很重要！队友很重要！队友很重要！&br&
队友的知识结构最好能互补，一个理想的队伍里要有一个手速狗、一个智商流、一个数学家。&br&2. 多刷题！&br&
1k，2k题是基本功，但也要保证题的质量，多刷水题有害健康！&br&3. 暴力大法好！&br&
拿到题先用暴力！暴力搜索，打表找规律，闭眼造公式，乃业界三大神器。&br&4. 除非你是大神或者你对自己特别自信，否则最好跟榜，但卡壳时也不能吊死在一颗树上。&br&5. 一定要确保模板100%的准确性，否则后果很严重！&br&想到再补充。。。&br&&br&以上。
谢邀，本弱ACM已经退役多时，只能凭借记忆分享一点浅薄的经验。：） 参考资料篇： 重点推荐刘汝佳三件套： 算法竞赛入门经典 算法竞赛训练指南 算法竞赛与信息学艺术 难度依次递增，紫书最先看，白书重点看，黑书可看可不看。 接下来是watashi大神鼎力推荐…
同非重点计算机专业毕业，毕业8年，计算机行业从业。&br&如果让我回到大一，我会这么安排。&br&1. 买台电脑，学会安装使用Linux，你可以使用虚拟机装一个。推荐 Ubuntu ，因为社区成熟，学习 bash 和各种命令行命令。学会使用vim。&br&2. 学习C语言，c programming language，Linux 编译。&br&3. 学习 Unix programming environment 这本书，在Linux环境下实践，学会使用版本控制工具git，将代码记录在GitHub上，搞清楚Linux下编译是怎么回事，学会使用make文件。&br&4. 进一步 学习APUE 实践方法同上。&br&5. 进一步 Unix网络编程两卷 实践方法同上。&br&6.读一读 code complete。&br&7. 读一读ESR的homepage:&a href=&///?target=http%3A//www.catb.org& class=& external& target=&_blank& rel=&nofollow noreferrer&&&span class=&invisible&&http://www.&/span&&span class=&visible&&catb.org&/span&&span class=&invisible&&&/span&&i class=&icon-external&&&/i&&/a& 。里面信息量非常大，关于黑客的来源和历史，关于如何成为编程大师。还有他的书Unix编程艺术，大教堂与集市。&br&8.读一下黑客与画家。&br&9.前面你都完成了，可以看Linux代码了。&br&10.学习网络的整体概况，有本书叫计算机网络 自顶向下的方法。不需要精通，能了解大概就好，最好读英文版。&br&11. 了解浏览器里面的工具是怎么呈现的，了解w3c，知道HTML，CSS，Js是怎么回事，会使用浏览器的调试工具。&br&12. 深入学习下TCP IP，学会使用一些常用命令行查看相关状态，学习怎么抓包，学会用工具分析包。&br&13.深入学习下HTTP协议，读一下相关的 RFC如鉴权相关的，建一个HTTP server，知道怎么用工具查看HTTP数据。&br&14. 尝试下lamp或类似的组合，写点有趣的东西。&br&15.到此你可能已经了解了计算机的一些基础，认真选择一个平台或领域，向纵深发展。&br&比如：Android平台。&br&16.加两个国内比较好的技术相关博客，cool shell 和阮一峰的博客，里面有给你启发的东西。&br&&br&说一下理由：先博而后渊，先全面了解基础然后选择一个领域持续发展。
同非重点计算机专业毕业，毕业8年，计算机行业从业。 如果让我回到大一，我会这么安排。 1. 买台电脑，学会安装使用Linux，你可以使用虚拟机装一个。推荐 Ubuntu ，因为社区成熟，学习 bash 和各种命令行命令。学会使用vim。 2. 学习C语言，c programming l…
已有帐号？
无法登录？
社交帐号登录
31050 人关注
2118 条内容
110 人关注
373 人关注
430 条内容