ACM国际大学生程序设计竞赛题解
2010-6
电子工业
赵端阳//袁鹤
374
无
ACM国际大学生程序设计竞赛（ACM／ICPC：ACM International Collegiate Programming Contest）是由国际计算机界历史悠久、颇具权威性的组织ACM学会（Association for Computing Machinery，美国计算机协会）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。1970年在美国Texas a& m大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。该项竞赛从1970年举办至今已经历29届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事。此项赛事的举办目的不单是培养参赛选手的创造力、团队合作精神以及他们在软件程序开发过程中的创新意识，同时也是检测选手们在压力下进行开发活动的能力。因此，ACM国际大学生程序设计竞赛是参赛选手展示计算机才华的广阔舞台，是著名大学计算机教育成果的直接体现，是信息企业与世界顶尖计算机人才对话的最好机会。该项竞赛分区域预赛和国际决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的3～4月举行，而区域预赛安排在上一年的9～12月在各大洲举行。从1998年开始，IBM公司连续赞助该项赛事的世界决赛和区域预赛。这项比赛是以大学为单位组队（每支队伍由教练、3名正式队员，一名后备队员组成）参赛的。国际ACM比赛1996年才进入中国内地，上海交通大学作为我国内地高校最早的参赛队之一，曾7次进军总决赛，并于2002年将ACM金杯首次带到亚洲。打破了几十年来欧美国家对这一赛事绝对的统治地位，更震惊了世界。2005年4月6日，在上海举办的“第29届ACM.国际大学生程序设计竞赛”总决赛中，上海交通大学团队成功解答8道题，以一题领先的优势力克来自世界六大洲29个国家和地区的78支参赛队，捧获“世界上最聪明的人”的冠军奖杯。时隔三年，ACM全球总决赛冠军奖杯再次回到了上海交通大学，领队俞勇教授与队员们手举国旗和校旗走上最高领奖台，激动之泪夺眶而出。上海交通大学团队从招生选苗、选拔队员、日常训练、寒暑假集训、赛前封闭训练，日复一日，年复一年，凭着顽强的毅力、强大的凝聚力，一步一个脚印、一步一个台阶，不断积累，顽强拼搏，两次携手捧回世界杯。国际ACM比赛是世界上规模最大、历史最长、影响最深的全球性计算机专业竞赛，它要求每一名队员不仅具有扎实的数学功底，非凡的算法设计能力，娴熟的编程技巧，而且必须具备很好的协作精神、稳定的心理素质、快速的临场应变能力。为了帮助各个大专院校的大学生们了解国际大学生程序设计竞赛，了解其程序设计的方法，提高参与校级、省级和亚洲区赛国际大学生程序设计竞赛的兴趣，特编写这本题解。
随着各大专院校参加ACM/ICPC热情的高涨，迫切需要有关介绍ACM国际大学生程序设计竞赛题解的书籍。本书根据浙江大学在线题库的前80题，进行了解答（个别特别简单或者特别复杂的题目未选择），比较详细地分析和深入浅出地讲解了解题的方法和用到的算法。题目的类型包括基础编程、模拟、字符串处理、搜索、动态规划、贪心、图论、几何和数学题。 本书可以作为高等院校有关专业的本科和大专学生参加国际大学生程序设计竞赛的辅导教材，或者作为高等院校数据结构、C/C++程序设计或算法设计与分析等相关课程的教学参考书。
第一章 基础编程题 ZJU1037-Gridland ZJU1045-HangOver ZJU1049-I Think I Need a Houseboat ZJU1058-Currency Exchange ZJU1067-Color Me Less ZJU1078-Palindrom Numbers 第二章 模拟算法题 ZJU1003-Crashing Balloon ZJU1006-Do the Untwist ZJU1005-Jugs ZJU1009-Enigma ZJU1016-Parencodings ZJU1021-The Willy Memorial Program ZJU1024-Calendar Game ZJU1036-Enigma 2 ZJU1039-Number Game ZJU1042-W s Cipher ZJU1051-A New Growth Industry ZJU1052-Algernon s Noxious Emissions ZJU1056-The Worm Turns ZJU1057-Undercut ZJU1063-Space Station Shielding ZJU1066-Square Ice ZJU1071-Follow My Logic ZJU1072-Microprocessor Simulation ZJU1073-Round and Round We Go 第三章 字符串处理题 ZJU1014-Operand ZJU1038-T9 ZJU1044-Index Generation ZJU1046-Double Vision ZJU1050-Start Up the Startup ZJU1068-P,MTHBGWB 第四章 基本数据结构题 ZJU1004-Anagrams by Stack ZJU1011-NTA ZJU1062-Trees Made to Order ZJU1061-Web Navigation 第五章 搜索算法题 ZJU1002-Fire Net ZJU1008-Gnome Tetravex ZJU1019-Illusive Chase ZJU1047-Image Perimeters ZJU1054-For the Porsche ZJU1055-Oh, Those Achin Feet ZJU1069-Plato s Blocks ZJU1075-Set Me ZJU1079-Robotic Jigsaw ZJU1080-Direct Subtraction 第六章 动态规划算法题 ZJU1013-Great Equipment ZJU1027-Human Gene Functions ZJU1074-To the Max 第七章 贪心算法题 ZJU1012-Mainframe ZJU1025-Wooden Sticks ZJU1029-Moving Tables ZJU1076-Gene Assembly 第八章 图论算法题 ZJU1015-Fishing Net ZJU1053-FDNY to the Rescue! ZJU1059-What s In a Name ZJU1060-Sorting It All Out ZJU1064-Roads Scholar 第九章 几何和数学题 ZJU1007-Numerical Summation of a Series ZJU1010-Area ZJU1026-Modular multiplication of polynomials ZJU1028-Flip and Shift ZJU1030-Farmland ZJU1032-Area 2 ZJU1034-Cog-Wheels ZJU1041-Transmitters 参考文献 索引
插图：
《ACM国际大学生程序设计竞赛题解(1)》是由电子工业出版社出版的。
无
对于学习ACM算法的非常有帮助！
这本书还不错，适合初学ACM的学生
希望多一些这样的书籍，不仅参赛选手可以用这样的书，一般的大学生也可以读读，里面的算法思想可以借鉴。
书内容很不错，拿到手就开始看了，很适合入门acm
很适合做ACM的选手用来训练提高
此书纸张质量很不错，书里面讲的也很详细，适合大学生喜欢编程的童鞋使用。
选了一些比较经典的题目，值得一看~
读者过瘾，有深度，有思想，题新颖典型，很好很好！！！编程者的福音！！！
这本书封面很好看，分析很透彻，感觉很好，是一本值得参考的教材书
一般般，分析问题不顾透彻
深入浅出，很有用
本书都讲了一些很实用的实例，表示我很喜欢，推荐购买的说~
考研用的着的一本书
很好，看看很好
哎呀，好不错哦！
书的内容还没看，质量挺不错的！！！
真的很好，发货太快了
发货速度很快，赞一个。
书质量很好，价格很实惠，性价比很高。
钻研只用
发货速度一流 ，，，书本陈述了中英文题目和详细的程序，对ACM初学者如我简直是如获至宝
该书集成了近几年大学生程序设计大赛的精华，是本不错的编程书，值得推荐。
嗯。不错的书。学习算法看看。
内容非常好。但是，在“内容简介”中提到的下载地址上查不到这本书。
没事了，看看。熏陶下。
书还可以，不过要是能把题目的档次在多一点会更好
偶尔翻翻的
这是一次很不愉快的购物，邮到书的外包装无任何损坏，而里面的书却破损严重，显然是把原已破损的书打包发出，我对你们的工作态度十分不满，这对消费者来说太不负责人了，我又急用，等换货已来不及了，而我又要整天捧着一本破损的书在看，心情十分不好，所以我只能给差评了。
首先，它是用C/C++写的。其次，它是基于ZOJ上的题目的，这样看完书上的解释后，再在ZOJ上submit一下，看能否AC，可以检验自己对算法的理解程度。然后，它并没有选择过分简单的题目，就算是第一章的基础题部分，都是那些比较有技巧的题目（当然，如果有经验，一上午AC掉整个第一章没问题）。后面的模拟、搜索，题目选得比较有难度，很好。而且，最难得可贵的是，它不是列出题目后就是代码的堆砌，而是有个解题分析部分，分析得很好，体现了作者的用心。我是选着看的，看了第一章，第二章和第五章后，给的评论。希望能够多点这样的书，为ACMer指条明路。
刚开始编程，看了这本书之后，不再像以前不知道从何入手了。
这本书用来练习，可以学到很多东西，毕竟编程这东西需要经常锻炼，多编
不过书很好看，这是确实的，如果能够对题目有更详细的解释，那就更好了
书质量很好，送货也比较快
rt！书的印刷质量极差
纸张太烂了，薄的厉害，都能透过纸看到背面一页的字了！明显的盗版书
不是为了acm 只是为了考研复习备用的
很不错的书，因为最近刷ZOJ题库买的，解析的还不错~~
送货快，正品行货
非常好看的一本书，值得拥有