ACM新手入门指南

ACM/ICPC新手入门指南前言：这篇指南不对ACM/ICPC国际大学生程序设计竞赛进行介绍，计算机学子如果不了解的可以在百度上进行搜索查询，这里介绍的只是一个计算机学生想要在ACM/ICPC里进行发展的初学者。内容比较简单通俗，完全是给新接触的人看的，已经接触过的请飘过，该干嘛的干嘛去。语言关：要进行程序设计，也就必然要熟悉编程语言，只要掌握了一门语言，就可以进行ACM训练了。一般通用语言如C、C++、JAVA都可以，这三种语言都有自己的优势和缺点，C在效率方面比较好；但C++封装了输入输出流，方便了我们的操作也减少出错的可能性，而且C++提供了非常强大的标准模版库（STL）,使得很多在C上实现起来比较麻烦的代码，在C++上却非常方便；JAVA在大型工程和安全方面都有比较独特的优势，但在ACM里面却不是一种优秀的语言，因为JAVA的执行效率要比C、C++慢很多，如果题目限时比较紧的话，就不适合用JAVA当然JAVA为我们提供了很方便的高精度运算（大整数运算），所以个人认为，刚学完C的可以用纯C来写训练，在训练过程中可以学学C++，有时间的把STL也好好学学，这样可以减少很多不必要的劳动。初次接触ACM训练的同学经常会遇到问题，就是输入和输出问题，所以如果对语言的输入输出问题不是很熟悉的话，要抽几天时间重点看看,特别有些初学者在输出时总会输出冗余信息，可能认为有交互性吧，但这是ACM不允许的，它不需要任何交互性。不严格按照题目要求进行输入输出的程序是无法通过系统测试的。熟悉在线评测系统在线评测系统，英文叫OnlineJudge,（简称OJ）里面提供了很多题目给我们平时训练之用。这里以浙江大学的在线评测系统为例，网址是先在上面进行注册，注册完后就可以进行题目的训练了，点击主页上的“Problems”，就可以看到里面的题库，可以选任何一个题来做，里面的题目不是由易到难进行排列，而初学者要选择比较简单的题目来做。一般来讲，每道题目都有他做对的正确率和提交的总次数，那些正确率比较高并且提交次数比较多的就会比较简单。一旦确定了做某道题，在读懂题意以后，就可以进行构思和编码了，编码完成后再进行程序的调试。一般写完了的程序不一定就正确，这时可以用题目下方提供的一些数据进行测试，如果不能通过，还得要对代码进行修改，直到能通过所有的测试数据。这里要注意的是，很多新手会问这样的问题，我的程序通过了它的数据呀，为什么提交的时候不正确呢，这是因为OJ系统关于这题的测试数据远远不止这些，它还有许多你无法知道的数据，你的程序必须要能通过它所有的数据，才算是正确。下面我们挑出里面最简单的一个题（1001）进行讲解：A+BProblemTimelimit:1SecondsMemorylimit:32768KTotalSubmit:52075AcceptedSubmit:22355Calculatea+bInputTheinputwillconsistofaseriesofpairsofintegersaandb,separatedbyaspace,onepairofintegersperline.OutputForeachpairofinputintegersaandbyoushouldoutputthesumofaandbinoneline,andwithonelineofoutputforeachlineininput.SampleInput15SampleOutput6我们发现这是一个求两数和的题目，输入ab程序输出a+b的结果，于是我们可以编写如下代码(注意:”〃”是C++的注释)：//C#ineludevstdio.h>intmain(){inta,b;while(seanf(”％d%d",&a,&b)!=EOF)//直到没有数据输入退出，//ms-dos窗口方式下,etrl+z结束.printf("%d/n",a+b);}〃或者C++#includeviostream>usingnamespaeestd;intmain(){inta,b;while(ein>>a>>b)eout<<a+bvvendl;}在题目的下面，有一个“Submit”选项，点击出现提交界面，我们可以把我们的代码复制上去，输入自己的帐号和密码就可以进行提交，如下图：点击“submit”，出现如下界面我们就可以点击“status”，系统通过对我们的代码进行测评，然后会给我们返回一个提示信息，如下图，这个程序的返回结果是Aeeepted,表示正确.并不是所有提交上去的代码都是返回Aeeepted，只有仔正确的情况下才会返回Aeeepted，一般而言，系统返回的信息有以下几种情况：Aeeepted(AC):恭喜你，你的程序是正确的。PresentationError(PE)：虽然你的程序输出了正确结果，但是二哥结果的格式有点问题，这时要检查程序的输出是否多了或少了空格('’)、制表符(7t')或者换行符(7n')。WrongAnswer(WA)程序的输出结果不正确，可能是算法有问题，也可能是其他问题。RuntimeError(RE):运行时错误，例如访问非法内存，像指针，数组下标越界会造成，程序出现除数为0,栈溢出等等。TimeLimitExeeeded(TLE):程序运行的时间超过题目的时间限制。MemoryLimitExeeeded(MLE):程序运行的内存超过题目的内存限制。OutputLimitExceeded(OLE)程序输出的内容太多，超过题目的输出限制。除了Accepted信息外，其他信息都说明你程序有问题，还要进行修改然后提交，直到正确。对系统的介绍大概到此，如果有问题或者还有不明白的，可以提问进行补充。程序的输入和输出问题OJ一般只支持标准输入输出，提交的程序不允许操作文件，你的程序不能输出任何多余信息，包括提示信息，如对上面1001题的程序，可能会有些人这样写：#ineludevstdio.h>intmain（）{inta,b;while⑴{printf（"请输入a和b："）;〃此行是多余输出，不允许if（scanf（"%d%d",&a,&b）==EOF）return0;printf（"%d/n",a+b）;}}每个题目的测试数据测试完毕后，就会以一个标记结束输入，向1001是文件结束，有些程序是特定的数据作为输入的结束，选手要认清楚这点。几个网上测评系统对于初学者，在/上面有比较多的适合初学者的题目，联系题目链接在/listproblem.php?vol=1上。浙大上面也有不少比较简单的题目，地址是/,如果不能判断哪些题目比较简单的话，可以查看这里的链接：/forum/viewtopic.php?t=1060每个OJ系统的操作大同小异，应该不成什么问题，有问题群里问问。当然还有不少比较出名的OJ,但作为初学者，这两个OJ已经是非常不错了，多做题，多看书，不浮躁，不气馁，不懂要问，水平提高会很快的。新手要掌握的知识和一些入门题刚学完一门语言，对算法和数据结构还不懂的同学，可以做做一些简单的题目,如浙大的：1001103710481049105110671115115112011205121612401241124212511292133113341337133813501365138213831394140214051414149415141622171517301755176017631796181318791889190419151949200120222099210421082172217622012208232123452351237623882405241724332781278228072812285728512878288328862892上面题目都不怎么需要算法基础，都是新手可以做出来的,多做可以比较快入门，没学过算法和数据结构的，自己要自学一些算法和数据结构，在了解了一些重要的数据结构的术语如线性表，栈，队列，字串，树，图等等的前提下，可以掌握以下相关算法：二分查找，数制转换，表达式求值,KMP字符串匹配算法，二叉树遍历，哈夫曼编码，深度优先搜索,广度优先搜索，最短路径，拓扑排序，二叉排序树，哈希，排序（插入排序、冒泡排序、快速排序、归并排序、堆排序，虽然ACM不怎么直接考排序，但掌握了有好处），高精度（大整数）加减乘除,欧几里德算法，扩展的欧几里德算法，以上的相关算法都是比较基础的，要重点掌握，可以自己买一本数据结构，或者图书馆借，遇到有上面算法的要重点研究，也可以上网搜索这些知识（这个很重要）,看完某一算法，可以做做相关的题目,这样就对算法的了解有一个升华.相关知识的题目，包括一些数学方面的题目（不保证全部正确）：排序+二分查找:.cn/JudgeOnline/problem?id=1318最小公倍数：/show_problem.php?pid=1797数列的周期性：/show_problem.php?pid=2105数三角形：/show_problem.php?pid=1629高精度加法：/show_problem.php?pid=1292非10进制高精度加法：/show_problem.php?pid=1205高精度乘法：/show_problem.php?pid=1073高精度和数制转换：/show_problem.php?pid=1086高精度除法：/show_problem.php?pid=1210高精度加法，以及比较：/show_problem.php?pid=1962排序：/JudgeOnline/problem?id=2388.cn/JudgeOnline/problem?id=2299哈夫曼树:/JudgeOnline/problem?id=3253二分图最大匹配：/JudgeOnline/problem?id=3041.cn/JudgeOnline/problem?id=3022拓扑排序：/JudgeOnline/problem?id=1094最小生成树(prim,kruskal算法)：.cn/show_problem.php?pid=1406.cn/show_problem.php?pid=1372.cn/JudgeOnline/problem?id=1789.cn/JudgeOnline/problem?id=2485.cn/JudgeOnline/problem?id=1258.cn/JudgeOnline/problem?id=3026最短路径算法(dijkstra,floyd,bellman-ford,heap+dijstra):.cn/JudgeOnline/problem?id=1860.cn/JudgeOnline/problem?id=3259.cn/JudgeOnline/problem?id=1062.cn/JudgeOnline/problem?id=2253.cn/JudgeOnline/problem?id=1125.cn/JudgeOnline/problem?id=2240深度优先搜索(dfs):.cn/show_problem.php?pid=1091.cn/show_problem.php?pid=1649.cn/show_problem.php?pid=1005.cn/show_problem.php?pid=2416.cn/JudgeOnline/problem?id=2488.cn/JudgeOnline/problem?id=3083.cn/JudgeOnline/problem?id=3009.cn/JudgeOnline/problem?id=1321.cn/JudgeOnline/problem?id=2251广度优先搜索(bfs):.cn/JudgeOnline/problem?id=3278.cn/JudgeOnline/problem?id=1426.cn/JudgeOnline/problem?id=3126.cn/JudgeOnline/problem?id=3087.cn/JudgeOnline/problem?id=3414KMP字符串匹配算法：.cn/JudgeOnline/problem?id=1961.cn/JudgeOnline/problem?id=2406二叉树遍历：.cn/show_problem.php?pid=1700提高要掌握的有：搜索，动态规划，贪心，图论，数论，计算几何，组合数学，初等数论，博弈论,附上zoj题目分类：简单题(beginnerproblem)字符串处理：/forum/viewtopic.php?t=68匹配问题：/forum/viewtopic.php?t=62模拟类：/forum/viewtopic.php?t=70动态规划：/forum/viewtopic.php?t=69搜索：/forum/viewtopic.php?t=67数论：/forum/viewtopic.php?t=66几何：/forum/viewtopic.php?t=65树结构：/forum/viewtopic.php?t=64图论：/forum/viewtopic.php?t=63组合：/forum/viewtopic.php?t=61贪婪：/forum/viewtopic.php?t=60最短路径：/forum/viewtopic.php?t=59游戏理论：/forum/viewtopic.php?t=58扌由象结构：/forum/viewtopic.php?t=57最大流：/forum/viewtopic.php?t=56其他：/forum/viewtopic.php?t=55计算机算法》开始做DP类型，第一个就挂了。。。(POJ1018)»加入讨论[1]POJ动态规划题目列表容易：1050,1083,1088,1125,1143,1157,1163,1178,1179,1189,1208,1276,1322,1414,1456,1458,1609,1644,1664,1690,1699,1740,1742,1887,1926,1936,1952,1953,1958,1959,1962,1975,1989,2018,2029,,2063,2081,2082,2181,2184,2192,2231,2279,2329,2336,2346,2353,2355,2356,2385,2392,2424,不易：1037,1080,1112,1141,1170,1192,1239,1655,1695,1707,1733,1737,1837,1850,1920,1934,1937,1964,2039,2138,2151,2161,2178,推荐：1015,1635,1636,1671,1682,1692,1704,1717,1722,1726,1732,1770,1821,1853,1949,2019,2127,2176,2228,2287,2342,2374,2378,2384,24111015JuryCompromise1029FalsecoinGangstersAdecorativefenceBugsIntegrated,Inc.1042GoneFishing1050TotheMax1062昂贵的聘礼1074ParallelExpectations1080HumanGeneFunctions1088滑雪1093FormattingText1112TeamThemUp!1141BracketsSequence1143NumberGame1157LITTLESHOPOFFLOWERSPalindromePostOffice1163TheTriangle1170ShoppingOffersCamelotPolygonBatchScheduling1185炮兵阵地1187陨石的秘密1189钉子和小球1191棋盘分割1192最优连通子集1208TheBlocksProblemIncreasingSequencesPre-Post-erous!1276CashMachine1293DutyFreeShopChocolateGamePrediction1338UglyNumbers1390Blocks1414LifeLine1432DecodingMorseSequences1456Supermarket1458CommonSubsequence1475PushingBoxes1485FastFood1505CopyingBooks1513SchedulingLectures1579FunctionRunFun1609TilingUpBlocks1631Bridgingsignals2分+DPNLOGN1633GladiatorsSubwaytreesystemsPrisonrearrangement1644ToBetorNotToBet1649MarketPlace1651MultiplicationPuzzle1655BalancingAct1661HelpJimmy1664放苹果1671RhymeSchemes1682ClansontheThreeGorges(Your)((Term)((Project)))PaintingABoardCrossedMatchings1695MagazineDelivery1699BestSequenee1704GeorgiaandBob1707Sumofpowers1712FlyingStars1714TheCaveDominoesRiverCrossing1722SUBTRACT1726TangoTangoInsurrectionPhonenumbersParitygame1737ConnectedGraph1740ANewStoneGame1742CoinsP1745DivisibilitySpecialExperimentElevatorStoppingPlan1776TaskSequences1821Fence1837Balanee1848Tree1850Code1853Cat1874TradeonVerweggistan1887TestingtheCATCHER1889PackagePricing1920TowersofHanoi1926Pollution1934TripAllinAllBalaneedFoodCowCyclingRebuildingRoads1949ChoresBUYLOW,BUYLOWERWorldCupNoiseStrangeTowersofHanoiDarts1962CorporativeNetwork1964CityGame1975M