acm算法大赛

A. acm竞赛的算法总共有那些范围 求大牛概括......

初级:
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书 page149):
1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)

B. 关于ACM竞赛

ACM考的是算法设计,编程,理解能力.
基本上ACM的题目都是英文的,所以你的英文要到火候,这个lz
应该没问题吧.

还有最主要的就是算法了,你可以去肯"算法导论"这本牛书.

第三就是编程能力,ACM竞赛中,时间也是一项衡量指标,怎样在最快的时间内解决问题,编译通过,并且运行正确.

最后,我觉得考虑问题的全面性也是很重要的,ACM的题目,很多都会有临界情况,如何让你的程序能够通过这些临界值的检验,很考察一个人思考问题的全面性的.

C. acm算法竞赛对网络安全帮助大吗

有帮助的。
数论等知识对网络安全方面有一些帮助。同时，ACM竞赛也可以帮助你提升代码能力。
算法对网络安全与其说重要，不如说必要，诚然不研究算法也能实战网络安全，但是要真正做到改变些什么而不是拾人牙慧必须要精于算法（其实算法对其他领域也是这样），如果要触及顶峰还必须要在实践的基础上有一套完善的思维体系，ACM刷题是否能触及这个顶峰我不知道，但是若有一天你刷得不觉得自己水平一般了，眼界里有了国际赛事了，甚至有一枚金牌了，一定不会觉得迷茫。

D. 你最难忘的一次ACM/OI比赛经历是什么

ACM打了四年比赛，去了两年final，区域赛冠军拿过，final金牌拿过，AK过，力挽狂澜过，也不知所措5小时过。要说难忘的经历，实际上太多了，final拿一血，290+分钟出题，封board前AK，其实有很多，但是硬要说最难忘的，算是2013年南京赛区的一道几何题吧。题目我已经记不太清了，大概是一个最后是三维空间射线和三角形判断交叉的问题。当时我拒绝了叉姐给我的一道状态压缩DP题目，在仅仅开赛一小时来写这道全场就4队通过的题目。算法其实很简单，但是，写完之后，发现有特殊情况，于是我下机考虑，然后上机改，又发现有特殊情况，又下机考虑，这么循环往复，在两个多小时的时候提交。因为结果返回的很慢，我在结果返回前就打印了代码，然后一次AC了，我当时就没有看代码。结果，后来在颁奖的时候无聊，看了看这题的代码，发现，卧槽，少考虑一种情况，居然过了。然后在路上，发现，卧槽，又少考虑一种情况，居然过了。然后和出题人交流的时候，发现，他们考虑的特殊情况，还没我第一次交的代码考虑的全面。

E. ACM动态规划问题（算法竞赛入门经典）

递归就不说了，明显是需要栈的逻辑结构维护的。简单说说对递推和DP的个人见解，只供参考。

DP=状态+状态转移方程
状态的关键特点是无后效性，简单地举例：奥运会某项目淘汰赛1/N决赛，成绩只跟以后的比赛有关，之前的成绩不带入（只考虑赛制）。如果你发现一个状态后面阶段决策需要用到前面阶段的状态信息，那么这就不是一个标准的DP。比如：
A - B1 - C1 - D
\-- EX ------/
如果将EX归为B段或C段，那么EX-D或者A-EX就跨越了跳跃了一个阶段，对于这个阶段来说他后面的阶段就用到了前面阶段的状态信息
当然这并不意味着不能采用DP算法，对于上面的例子，可以将EX本身拆为B2 - C2就可以满足DP条件了，对于连续状态的DP，类似的调整更多。

状态转移方程是状态到状态的决策
简单地说，就是贪心的那一部分，多条路你选择一条路的过程

很多时候，递推和DP难以区分，一般情况，状态转移决策明显是“选择”的时候，会当做DP，而如果计算比重较大，会当做递推；状态调整比较多时，可能认为是递推；连续状态可以归为DP。
例：M*N的的带权格子，从左上走到右下，每次只能向右或下移动一格，求权值加和最大（小）的路径条数。

还有一个相关词叫做“递推规划”，有兴趣的话可以自己看下相关资料

解释之后答案很明显：DP要有状态转移方程。甚至可以说DP的关键就是状态转移方程。
你的第一个问题，希望你把书名报一下，我貌似没有白皮的

F. 怎么搞好acm竞赛

想搞好ACM竞赛不大容易，首先你需要学会C/C++/java中的一个作为工具语言。因为这种竞赛不是在考察你的语法，而是考察你的算法功底。ACM涉及的算法很多，比赛考察内容也比较杂。因此如果你要出成绩就必须付出很多努力。做题是ACM中非常重要的，你必须坚持刷题。先从非常简单的题目做起，起到一个入门的作用。如果不知道那些题是入门题可以找一个人带你。先刷这些入门题，直到对编程和ACM熟悉了就可以往下学习。数据结构是ACM中很重要的，以后很多比较有难度的知识都离不开数据结构。再往后要学习各种算法，《算法导论》是一本经典的书。我们学校集训队人手一本。这本书其实并不是非常易懂，其实学算法本来就是需要下功夫的。搞ACM你大概需要了解下面这些知识:动态规划、数论、图论、网络流、计算几何、KMP、搜索技术等，每一部分还有很多知识点，因此样样精通是根本不可能的。如果想拿点成绩那么你必须在绝大多数方面都有些了解，而且自己应该还有些强项。我在我们学校集训队就是主要搞计算几何的。努力是必须的，如果想拿到好成绩是要看你的水平和队友的水平还有合作是否默契等。

G. 怎么样才能参加ACM 竞赛啊

算法，数据结构是关键，另外还有组合数学，特别是集合与图论，概率论也重要。推荐买一本《算法导论》，那本书行，看起来超爽！！！基本掌握语法还不行啊，语法的超熟练掌握，不然出了错误很难调试的！！！最重要的是超牛皮的头脑啦，分析能力，逻辑推理能力很重要。ACM很好玩啦，祝你成功！！！

acm是3人一组的，以学校为单位报名的，也就是说要得到学校同意，还要有2个一起搞的。其实可能是你不知道你们学校搞acm的地方，建议你好好询问下你们学校管科技创新方面的人。建议你找几个兴趣相同的一起做，互相探讨效果好多了，团队合作也是acm要求的3大能力之一。
数据结构远远不够的，建议你看算法导论，黑书，oj的话个人觉得还是poj好，有水题有好题，而且做的人多，要解题报告什么的也好找。我们就是一些做acm的学生一起搞，也没老师，这样肯定能行的。

基础的话是语言，然后数据结构，然后算法。
ACM有三个方向：算法，数学，实现
要求三种能力：英文，自学，团队协作
简单的说，你要能读懂英文的题意描述，要有一门acm能使用的编程语言，要会数据结构，有一点数学基础，一点编程方面天赋，要有兴趣和毅力（最重要），就具有做ACM的基本条件了。

做acm我推荐c，c++也可以，java在某些情况下好用，但是大多数情况的效率和代码量都不大好，所以建议主用c++，有些题目用java

还有什么问题，可以问我啊。

不好意思，没见过用java描述的acm书籍，大多数是用伪命令，其他有的用的c，c++，老一些的用pascal。java只是用来做高精度的一些题的，个人觉得不用专门看这方面的书，java的基本部分学好就够用了。所以我还是推荐主用c++，在高精度和个别题再用java。你可以找找java描述的算法设计与分析，这个好像有
数据结构：C语言版 清华大学出版社 严蔚敏 《数据结构》

算法：清华大学出版社 王晓东 《算法设计与分析》
麻省理工大学 中译本：机械工业出版社 《算法导论》

基本上这三本书就已经足够了，建议一般水平的人先不要看算法导论，待另外两本书看的差不多的时候，再看算法导论加深理解。
另外还有很多针对性更强的书籍，不过针对性太强，这里就不多介绍了。

以上一些都是些算法方面的书，最好的方式就是做题与看书相结合，很多在线做题的网站，PKU，ZOJ很多，推荐PKU，题目比较多，参与的人比较多。做一段时间的题，然后看书，研究算法，再做题，这样进步比较快。

还有关于ACM竞赛，我有自己的一点话说。
首先说下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算法），并且多阅读一些定理的证明，这虽然不能有什么直接的帮助，但是长期坚持就会对思维很有帮助。

四、团队配合

通过以上的介绍大家也可以看出，信息学竞赛对于知识面覆盖的非常广，想凭一己之力全部消化这些东西实在是相当困难的，这就要求我们尽可能地发挥团队协作的精神。同组成员之间的熟练配合和默契的形成需要时间，具体的情况因成员的组成不同而不同，这里我就不再多说了。

五、练习、练习、再练习

知识的积累固然重要，但是信息学终究不是看出来的，而是练出来的，这是多少前人最深的一点体会，只有通过具体题目的分析和实践，才能真正掌握数学的使用和算法的应用，并在不断的练习中增加编程经验和技巧，提高对时间复杂度的感性认识，优化时间的分配，加强团队的配合。总之，在这里光有纸上谈兵是绝对不行的，必须要通过实战来锻炼自己。

大家一定要问，我们去哪里找题做，又如何检验程序是否正确呢？这大可不必担心，现在已经有了很多网上做题的站点，这些站点提供了大量的题库并支持在线判卷，你只需要把程序源码提交上去，马上就可以知道自己的程序是否正确，运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点，笔者不建议大家在所有这些站点上做题，选择一个就可以了，因为每个站点的题都有一定的难易比例，系统地做一套题库可以使你对各种难度、各种类型的题都有所认识。

1、Ural：

Ural是中国学生对俄罗斯的Ural州立大学的简称 ，那里设立了一个Ural Online Problem Set，并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强，得到了国内广大学生的厚爱。根据“信息学初学者之家”网站的统计，Ural的题目类型大概呈如下的分布：

题型
搜索
动态规划
贪心
构造
图论
计算几何
纯数学问题
数据结构
其它

所占比例
约10%
约15%
约5%
约5%
约10%
约5%
约20%
约5%
约25%

这和实际比赛中的题型分布也是大体相当的。有兴趣的朋友可以去看看。

2、UVA：

UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ，并且支持ONLINE JUDGE，形式和Ural大学的题库类似。不过和Ural不同的是，UVA题目多的多，而且比较杂，而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从，要么难以找到合适的题目，要么Wrong Answer了很多次以后仍然不知道错在那里。 如果说做Ural题目主要是为了训练算法，那么UVA题目可以训练全方位的基本功和一些必要的编程素质。UVA和许多世界知名大学联合办有同步网上比赛，因此那里强人无数，不过你先要使自己具有听懂他们在说什么的素质：）

3、ZOJ：

ZOJ是浙江大学建立的ONLINE JUDGE，是中国大学建立的第一个同类站点，也是最好和人气最高的一个，笔者和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站，但是这里的中国学生比较多，因此让人觉得很亲切。这里目前有500多道题目，难易分配适中，且涵盖了各大洲的题目类型并配有索引，除此之外，ZOJ的JUDGE系统是几个网站中表现得比较好的一个，很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛，只要是注册的用户都可以参加。

说起中国的ONLINE JUDGE，去年才开始参加ACM竞赛的北京大学现在也建立了自己的提交系统；而我们学校也是去年开始参加比赛，现在也有可能推出自己的提交系统，如果能够做成，到时候大家就可以去上面做题了。同类网站的飞速发展标志着有越来越多的同学有兴趣进入信息学的领域探索，这是一件好事，同时也意味着更激烈的竞争。

H. 有哪些含金量高的算法大赛可以参加

作为中兴的老员工，这个时候我必须站中兴了，咱们有最丰厚的奖金，最专业的评委，你，值得拥有！

I. 怎么准备ACM程序大赛

原创哦~
我的观点：
第一阶段：先刷水题，水题，就是几乎不牵扯算法。需要自己想方法解决。
这样的题，一是锻炼 逻辑思维和思维的严谨，二是锻炼代码能力（写的代码越来越长而错误越来越少，看别人很长的代码很快就能看明白对方的思路，这些都是代码能力）
代码能力不够直接学习算法 会非常吃力了。。
在各大OJ刷200道水题，这样算是入门了吧。。：（推荐去HDOJ因为这上面的水题比较多，适合新手入门，第11页，第16很多中文水题）。越到实在是做不出来的题就放放。。

第二阶段：渐渐的学一些简单的算法。。
HDOJ的论坛上有的课件，水题刷的差不多了，看着课件（课件有些得放写的不是很详细，可以去网络 这方面的资料），学一些基础算法，继续刷题。。。。。
第二阶段刷到400.。

第三阶段： 在第二阶段的基础上继续纠结算法。 这时候可以看算法导论了。学习数据结构。继续刷题。。
刷到600.。

算法导论看完之后楼主可以去看看 刘汝佳的黑书（算法艺术与信息学竞赛）。
如果楼主能坚持到这时候，那算是一个牛了。。
之后楼主应该就知道该怎么走了。。