随着各大专院校参加ACM/ICPC热情的高涨，迫切需要有关介绍ACM国际大学生程序设计竞赛题解的书籍。本书根据浙江大学在线题库的前80题，进行了解答（个别特别简单或者特别复杂的题目未选择），比较详细地分析和深入浅出地讲解了解题的方法和用到的算法。题目的类型包括基础编程、模拟、字符串处理、搜索、动态规划、贪心、图论、几何和数学题。 本书可以作为高等院校有关专业的本科和大专学生参加国际大学生程序设计竞赛的辅导教材，或者作为高等院校数据结构、C/C++程序设计或算法设计与分析等相关课程的教学参考书。 书中各题目的源代码及相关资料可在 http://www.hxedu.com.cn下载。

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比赛是世界上规模最大、历史最长、影响最深的全球性计算机专业竞赛，它要求每一名队员不仅具有扎实的数学功底，非凡的算法设计能力，娴熟的编程技巧，而且必须具备很好的协作精神、稳定的心理素质、快速的临场应变能力。 为了帮助各个大专院校的大学生们了解国际大学生程序设计竞赛，了解其程序设计的方法，提高参与校级、省级和亚洲区赛国际大学生程序设计竞赛的兴趣，特编写这本题解。 全书共分9章：第一章，基础编程题。主要是比较容易的题目，也称简单题，尤其适合刚刚开始熟悉ACM大学生程序设计竞赛做题的同学。通过这些题目的练习，主要是熟悉数据的输入、输出格式，基本编程方法，在线提交系统的使用，常见错误及其对策。第二章，模拟算法题。根据题目的要求逐步实现目标，虽然没有经典的算法可以使用，正确理解题目是关键的要素。例如题目Enigma、Enigma2和Microprocessor Simulation等。第三章，字符串处理题。主要是字符串的处理，这也是考察参赛者细心的一类题目，需要对各种情况进行仔细的分析，予以正确的处理。例如题目Operand和P,MTHBGWB等。第四章，基本数据结构题。常见的有二叉树、堆栈和列表等，如Trees Made to Order等。第五章，搜索算法题。这是一个最常见的类型，通常有深度优先搜索和广度优先搜索算法。例如题目Fire Net和Robotic Jigsaw等。第六章，动态规划算法题。这些题目使用动态规划算法，会获得较快的运行时间和效率，例如题目Great Equipment等。第七章，贪心算法题。这些题目使用贪心算法，会获得较快的运行时间和效率，例如题目Mainframe和Gene Assembly等。第八章，图论题。主要包含拓朴排序、Floyd算法和二分图等，例如题目FDNY to the Rescue!和Roads Scholar等。第九章，几何和数学题。主要是几何题和一些数学计算题目，例如题目Farmland和Transmitters等。 本部分通过大量的实例介绍了竞赛中常用的算法，并对如何灵活地应用这些算法进行了比较详细地分析和深入浅出地讲解。 本书所用的语言是C/C++，并在MinGW Developer Studio中调试通过。在运行时间和内存占用的性能方面，C++并不比C语言优越多少，只是C++有丰富的模板库函数，输入/输出语句简单，编写的代码看起来格式更工整而已。在有大量输入/输出数据的题目中，书中会特别提醒读者需要使用C语言的输入/输出。 显然，“Accepted”是我们的目标，算法是我们不断探索的道路，好的算法让我们容易达到目标。本书中的算法，虽然作者经过反复斟酌，不断优化和简化，仍然不能认为是最优的。因为对算法的探索，正如金庸笔下的大侠们苦练武功一样，是没有止境的。 本书中虽然描述的是“ACM国际大学生程序设计竞赛”中最基本的算法，但它也已经超出了一般本科教科书所讲授的范围。清华大学计算机科学与技术系博士生导师、国际信息学奥林匹克中国队总教练吴文虎教授认为算法的确是艺术，“艺术与科学是相通的，都会给人以美的享受。”并感叹道：“体味思维艺术之美，我以为这可能是更高层次的享受”[1]。希望读者能从本书中体会到这一点。 本书可以作为高等院校有关专业的本科和大专学生参加国际大学生程序设计竞赛的辅导教材，或者作为高等院校数据结构、C/C++程序设计或算法设计与分析等相关课程的教学参考书，旨在培养和提高学生参加ACM国际大学生程序设计竞赛的兴趣。 本书在编写过程中得到了浙江大学在线裁判系统管理员的大力支持，在此表示非常感谢。 感谢沈仙桥、郑丹同学翻译了大部分的题目。 同时也得到了ACM参赛队员戚勇、林刚、王海江、沈懿华、郑彦良、戴俊、周智栋、应建伟等同学的热情帮助。 由于作者水平所限，书中难免有不足之处，恳请广大读者批评指正。作者电子邮件地址：727946579@qq.com和hzyuanhe@163.com。 编著者 2010年4月于杭州

第一章 基础编程题 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 参考文献 索引

http://www.hxedu.com.cn/hxedu/fg/book/bookinfo.html?code=TP110630