本书收录了2005—2006年中山大学ICPC集训队内部选拔赛的全部试题、完整的测试数据和答案。为了方便读者学习，本书对每个题目做了详尽的题目分析并详细地讲解其算法实现的原理，同时提供了完善的标准程序及其程序分析。书中提供了基本测试数据，便于读者测试自行完成上述题目的结果。随书附带的光盘存放所有例题完整的测试数据，便于有更多需求的同学利用规模更大的测试数据进行训练和学习。 本书所提供的题目都是原创题，题目构思新颖，内容有趣。所涉及的算法知识面广，基本上覆盖大学计算机类本科专业的所学到的基本算法。 本书可以作为高等院校大学生和研究生准备参加各级国际大学生程序设计竞赛活动的辅导教材和训练题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考书，同时还可以作为中学省级及以上信息学奥林匹克优秀选手备战高层次程序设计竞赛的参考用书。

ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM/ICPC）是由国际计算机界历史悠久、颇具权威性的组织ACM学会（Association for Computer Machinery）主办的，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该项竞赛从1970年举办至今已历32届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视，并受到全世界各著名IT企业的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事。ACM所颁发的获奖证书也为世界各知名大学、各著名IT企业所认可。该项竞赛分为区域预赛和世界决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的3—4月举行，而区域预赛安排在上一年的9—12月在各大洲举行。ACM/ICPC的区域预赛是规模很大、范围很广的赛事。以2009年为例，全世界有82个国家和地区、1931所大学、7319支参赛队在六大洲的37个赛站中争夺世界决赛的103个名额，其激烈程度可想而知。 与其他编程竞赛相比，ACM/ICPC题目难度更大，更强调算法的高效性，不仅要解决一个指定的命题，而且必须以最佳的方式解决指定的命题。它涉及的知识面广，与大学计算机系本科及研究生的课程直接关联，如程序设计、离散数学、数据结构、人工智能、算法分析与设计等课程；对数学要求更高；由于采用英文命题，对英语要求较高；ACM/ICPC采用3人合作、公用一台电脑，所以它更强调团队协作精神；由于许多题目并无现成的算法，需要具备创新的精神，ACM/ICPC不仅强调学科的基础，更强调全面素质和能力的培养；由于ACM/ICPC是采用5小时全封闭式竞赛，参赛队员与外界完全隔离，独立完成，是参赛队员实际能力的真实表露，其成绩可信度甚高。ACM/ICPC又是一种“开卷考试”，可以带任何书籍、资料甚至源程序代码清单（但不能带电子媒体），不需要死背算法，而强调的是算法的灵活运用；与其他计算机竞赛（如软件设计，网站设计等）相比，ACM/ICPC有严谨而客观的评判规则（严格的数据测试），排除了因评委的主观因素而造成评审不公平的现象，所以，ACM/ICPC对成绩的争议较少。 中山大学自1997年首次参加ACM/ICPC亚洲区预赛以来的13年中，每年都派出多支队共参加过52次亚洲区预赛，成绩有45次排在前6名，6次排在前10名，1次排在前12名；其中有25次进入三甲，夺得5次冠军（1999年台北，2002、2003年高雄，2007年岘港，2009年合肥）、9次亚军（2000年香港、筑波，2003年北京、广州，2006年河内，2007年首尔，2008年雅加达、首尔，2009年宁波）、11次季军（1998—2000年上海、2001年达卡、2002年北京，2003年高雄，2004年马尼拉，2005年台北、北京，2006年首尔，2007年成都）；中山大学的参赛队11次进入全球总决赛（1999—2001年、2003—2008年）：2000年在美国佛罗里达州奥兰多市举行的第24届全球总决赛中取得了第11名的好成绩；2001年在加拿大温哥华市举行的第25届全球总决赛中首获铜牌（世界第14名）；2003年在美国洛杉矶市好莱坞举行的第27届全球总决赛中取得世界第8名并首获银牌的好成绩，跻身世界八强之列；2004年在捷克布拉格市举行的第28届全球总决赛中获得世界第11名并再获铜牌，且在中国内地高校中排名第一； 2005年在上海市举行的第29届全球总决赛中获得世界第17名；2006年在美国得克萨斯州圣安东尼奥市举行的第30届全球总决赛中获得世界第19名；2007年在日本东京市举行的第31届全球总决赛中获得世界第26名；2008年在加拿大班夫市举行的第32届全球总决赛中获得世界第23名；2009年在瑞典斯德哥尔摩市举行的第33届全球总决赛中获得世界第20名；并取得将在2010年举行的第34届全球总决赛的参赛资格。 为了帮助高等院校的大学生们备战国际大学生程序设计竞赛，帮助他们提高程序设计水平和培养更强的分析问题与解决问题的能力，我们编写了这套《国际大学生程序设计竞赛例题解》。本书是这套《国际大学生程序设计竞赛例题解》的第七册，编程所用的语言版本是Microsoft Visual C++6.0。全书共分10章，本书收录了2005—2006年中山大学ICPC集训队内部选拔赛的全部试题、完整的测试数据和答案。为了方便读者学习，本书对每个题目作了详尽的题目分析，并详细地讲解其算法实现的原理，同时提供了完善的参考程序及其程序分析，供读者参考。书中提供了基本测试数据，以方便读者测试自行完成上述题目的结果。随书附带的光盘中存放所有例题中完整的测试数据，以便于有更多需求的同学能利用规模更大的测试数据进行训练和学习。参与上述竞赛命题的有：蔡文志、黎俊瑜、莫瑜、关沛勇、林祺颖、梁锋等，他们均为硕士硕士研究生，都是参加过世界决赛或亚洲多个赛站区域预赛并取得很好成绩的中山大学队的主力队员。读者从附录A中可以看到，中山大学ACM/ICPC队13年来取得不俗的成绩。究其原因，除了有完善的选拔机制外，集训队内部个人选拔赛（俗称“4+2”）的作用也是十分重要的。本书再次公开了中山大学ICPC集训队内部选拔赛的题目和题解，以便加强与读者的交流。在附录B中，介绍了中山大学集训队选拔流程。不难看出，集训队是面向全校的，一年内每个同学都有多次机会参加集训队选拔，从而在校园里形成良好的学术氛围，这也是中山大学开展ICPC的活动成功的秘决。 本书由中山大学郭嵩山教授和他指导的3位研究生撰写，郭嵩山老师是国际大学生程序设计竞赛中山大学队的主教练，刘祖立、刘曦、涂德健是参加过全球总决赛或亚洲多个赛站区域预赛并取得很好成绩的中山大学队的主力队员。作者期望能将自己的知识、经验、心得和体会，奉献给广大的程序设计爱好者，以便与大家共同探讨和交流。 本书所提供的题目全部为原创题，题目构思新颖、涉及的算法知识面广，基本上覆盖大学计算机类本科专业所学到的基本算法。本书可以作为高等院校大学生和研究生准备参加各级国际大学生程序设计竞赛活动的辅导教材及训练题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考书，并适于作为中学省级及以上信息学奥林匹克优秀选手备战高层次程序设计竞赛的参考用书。 由于我们水平所限，书中难免有不足之处，欢迎读者批评指正，谢谢！ 作 者 2010年6月

本书试题涉及知识点的说明 1 第1章 2005年中山大学内部选拔赛第一试试题分析3 1.1 原子核研究（难度：★★★☆☆） 3 1.1.1 试题 3 1.1.2 题目分析与算法实现 4 1.1.3 参考程序与程序分析 6 1.1.4 部分测试数据与输出结果 8 1.2 脑力游戏（难度：★★★★☆） 9 1.2.1 试题 9 1.2.2 题目分析与算法实现 10 1.2.3 参考程序与程序分析 11 1.2.4 部分测试数据与输出结果 13 1.3 循环序列（难度：★★☆☆☆） 14 1.3.1 试题 14 1.3.2 题目分析与算法实现 15 1.3.3 参考程序与程序分析 16 1.3.4 部分测试数据与输出结果 17 1.4 舞王之王（难度：★★★★★） 18 1.4.1 试题 18 1.4.2 题目分析与算法实现 19 1.4.3 参考程序与程序分析 21 1.4.4 部分测试数据与输出结果 28 1.5 Torus大逃亡（难度：★★☆☆☆） 29 1.5.1 试题 29 1.5.2 题目分析与算法实现 30 1.5.3 参考程序与程序分析 31 1.5.4 部分测试数据与输出结果 32 第2章 2005年中山大学内部选拔赛第二试试题分析 33 2.1 主题医院（难度：★★★☆☆） 33 2.1.1 试题 33 2.1.2 题目分析与算法实现 34 2.1.3 参考程序与程序分析 35 2.1.4 部分测试数据与输出结果 37 2.2 带分数问题（难度：★★★☆☆） 38 2.2.1 试题 38 2.2.2 题目分析与算法实现 39 2.2.3 参考程序与程序分析 39 2.2.4 部分测试数据与输出结果 42 2.3 三角形（难度：★★☆☆☆） 43 2.3.1 试题 43 2.3.2 题目分析与算法实现 44 2.3.3 参考程序与程序分析 44 2.3.4 部分测试数据与输出结果 45 2.4 布料相交（难度：★★★★★） 46 2.4.1 试题 46 2.4.2 题目分析与算法实现 48 2.4.3 参考程序与程序分析 48 2.4.4 部分测试数据与输出结果 54 2.5 掘金（难度：★★★★☆） 56 2.5.1 试题 56 2.5.2 题目分析与算法实现 57 2.5.3 参考程序与程序分析 57 2.5.4 部分测试数据与输出结果 61 第3章 2005年中山大学内部选拔赛第三试试题分析 63 3.1 最小差值生成树（难度：★★★☆☆） 63 3.1.1 试题 63 3.1.2 题目分析与算法实现 64 3.1.3 参考程序与程序分析 64 3.1.4 部分测试数据与输出结果 67 3.2 Alice和Bob（难度：★★★☆☆） 67 3.2.1 试题 67 3.2.2 题目分析与算法实现 69 3.2.3 参考程序与程序分析 70 3.2.4 部分测试数据与输出结果 70 3.3 Collatz难题（难度：★★★☆☆） 71 3.3.1 试题 71 3.3.2 题目分析与算法实现 72 3.3.3 参考程序与程序分析 73 3.3.4 部分测试数据与输出结果 76 3.4 直接做吧（难度：★★☆☆☆） 77 3.4.1 试题 77 3.4.2 题目分析与算法实现 78 3.4.3 参考程序与程序分析 78 3.4.4 部分测试数据与输出结果 79 3.5 又是欧几里德（难度：★★★☆☆） 80 3.5.1 试题 80 3.5.2 题目分析与算法实现 81 3.5.3 参考程序与程序分析 81 3.5.4 部分测试数据与输出结果 82 3.6 未来的火车网络建设（难度：★★★★☆） 83 3.6.1 试题83 3.6.2 题目分析与算法实现 84 3.6.3 参考程序与程序分析 85 3.6.4 部分测试数据与输出结果 88 第4章 2005年中山大学内部选拔赛第四试试题分析 89 4.1 Max的岛屿（难度：★★★☆☆） 89 4.1.1 试题 89 4.1.2 题目分析与算法实现 90 4.1.3 参考程序与程序分析 92 4.1.4 部分测试数据与输出结果 94 4.2 再次是球（难度：★★★☆☆） 96 4.2.1 试题 96 4.2.2 题目分析与算法实现 97 4.2.3 参考程序与程序分析 97 4.2.4 部分测试数据与输出结果 100 4.3 Max的游戏（难度：★★☆☆☆） 100 4.3.1 试题 100 4.3.2 题目分析与算法实现 101 4.3.3 参考程序与程序分析 102 4.3.4 部分测试数据与输出结果 104 4.4 Max的王国（难度：★☆☆☆☆） 105 4.4.1 试题 105 4.4.2 题目分析与算法实现 106 4.4.3 参考程序与程序分析 106 4.4.4 部分测试数据与输出结果 107 4.5 Max的点（难度：★★☆☆☆） 108 4.5.1 试题 108 4.5.2 题目分析与算法实现 109 4.5.3 参考程序与程序分析 110 4.5.4 部分测试数据与输出结果 111 4.6 盗墓者（难度：★★★★☆） 112 4.6.1 试题 112 4.6.2 题目分析与算法实现 115 4.6.3 参考程序与程序分析 116 4.6.4 部分测试数据与输出结果 118 第5章 2006年中山大学内部选拔赛第一试试题分析 119 5.1 数组（难度：★★☆☆☆） 119 5.1.1 试题 119 5.1.2 题目分析与算法实现 120 5.1.3 参考程序与程序分析 120 5.1.4 部分测试数据与输出结果 121 5.2 有趣的游戏（难度：★★☆☆☆） 121 5.2.1 试题 121 5.2.2 题目分析与算法实现 122 5.2.3 参考程序与程序分析 123 5.2.4 部分测试数据与输出结果 123 5.3 乡村公路（难度：★★★☆☆） 124 5.3.1 试题 124 5.3.2 题目分析与算法实现 125 5.3.3 参考程序与程序分析 126 5.3.4 部分测试数据与输出结果 128 5.4 调试（难度：★★★☆☆） 128 5.4.1 试题 128 5.4.2 题目分析与算法实现 129 5.4.3 参考程序与程序分析 131 5.4.4 部分测试数据与输出结果 132 5.5 世界杯2006（难度：★★★☆☆） 133 5.5.1 试题 133 5.5.2 题目分析与算法实现 134 5.5.3 参考程序与程序分析 135 5.5.4 部分测试数据与输出结果 136 第6章 2006年中山大学内部选拔赛第二试试题分析 137 6.1 车（象棋）（难度：★★★☆☆） 137 6.1.1 试题 137 6.1.2 题目分析与算法实现 138 6.1.3 参考程序与程序分析 139 6.1.4 部分测试数据与输出结果 141 6.2 序列（难度：★★☆☆☆） 142 6.2.1 试题 142 6.2.2 题目分析与算法实现 143 6.2.3 参考程序与程序分析 143 6.2.4 部分测试数据与输出结果 145 6.3 树（难度：★★★☆☆） 145 6.3.1 试题 145 6.3.2 题目分析与算法实现 146 6.3.3 参考程序与程序分析 147 6.3.4 部分测试数据与输出结果 148 6.4 虎胆龙威4（难度：★★☆☆☆） 150 6.4.1 试题 150 6.4.2 题目分析与算法实现 151 6.4.3 参考程序与程序分析 151 6.4.4 部分测试数据与输出结果 152 6.5 Alice和Bob（难度：★☆☆☆☆） 153 6.5.1 试题 153 6.5.2 题目分析与算法实现 153 6.5.3 参考程序与程序分析 154 6.5.4 部分测试数据与输出结果 155 第7章 2006年中山大学内部选拔赛第三试试题分析 156 7.1 幻灯片（难度：★★☆☆☆） 156 7.1.1 试题 156 7.1.2 题目分析与算法实现 157 7.1.3 参考程序与程序分析 158 7.1.4 部分测试数据与输出结果 160 7.2 医院规划（难度：★★★★★） 161 7.2.1 试题 161 7.2.2 题目分析与算法实现 162 7.2.3 参考程序与程序分析 163 7.2.4 部分测试数据与输出结果 165 7.3 讨厌转弯的机器人（难度：★★★☆☆） 166 7.3.1 试题 166 7.3.2 题目分析与算法实现 168 7.3.3 参考程序与程序分析 169 7.3.4 部分测试数据与输出结果 171 7.4 导弹发射（难度：★★★★☆） 173 7.4.1 试题 173 7.4.2 题目分析与算法实现 174 7.4.3 参考程序与程序分析 175 7.4.4 部分测试数据与输出结果 177 7.5 最大公约数与最小公倍数（难度：★★★☆☆） 178 7.5.1 试题 178 7.5.2 题目分析与算法实现 179 7.5.3 参考程序与程序分析 180 7.5.4 部分测试数据与输出结果 181 第8章 2006年中山大学内部选拔赛第四试试题分析 183 8.1 两直线的距离（难度：★★★☆☆） 183 8.1.1 试题 183 8.1.2 题目分析与算法实现 184 8.1.3 参考程序与程序分析 186 8.1.4 部分测试数据与输出结果 188 8.2 一次同余方程（难度：★★★☆☆） 189 8.2.1 试题 189 8.2.2 题目分析与算法实现 190 8.2.3 参考程序与程序分析 190 8.2.4 部分测试数据与输出结果 191 8.3 游泳（难度：★☆☆☆☆） 193 8.3.1 试题 193 8.3.2 题目分析与算法实现 194 8.3.3 参考程序与程序分析 195 8.3.4 部分测试数据与输出结果 195 8.4 城市漫步（难度：★★★★☆） 198 8.4.1 试题 198 8.4.2 题目分析与算法实现 199 8.4.3 参考程序与程序分析 200 8.4.4 部分测试数据与输出结果 202 8.5 先序遍历（难度：★★☆☆☆） 204 8.5.1 试题 204 8.5.2 题目分析与算法实现 205 8.5.3 参考程序与程序分析 207 8.5.4 部分测试数据与输出结果 209 第9章 2006年中山大学内部选拔赛第五试试题分析 211 9.1 又是主题医院（难度：★★★★☆） 211 9.1.1 试题 211 9.1.2 题目分析与算法实现 212 9.1.3 参考程序与程序分析 214 9.1.4 部分测试数据与输出结果 215 9.2 卖票（难度：★★☆☆☆） 218 9.2.1 试题 218 9.2.2 题目分析与算法实现 219 9.2.3 参考程序与程序分析 219 9.2.4 部分测试数据与输出结果 220 9.3 碰碰球（难度：★★★☆☆） 222 9.3.1 试题 222 9.3.2 题目分析与算法实现 223 9.3.3 参考程序与程序分析 224 9.3.4 部分测试数据与输出结果 226 9.4 灌水VS抽水（难度：★★☆☆☆） 230 9.4.1 试题 230 9.4.2 题目分析与算法实现 230 9.4.3 参考程序与程序分析 231 9.4.4 部分测试数据与输出结果 233 9.5 下载（难度：★★★☆☆） 235 9.5.1 试题 235 9.5.2 题目分析与算法实现 236 9.5.3 参考程序与程序分析 237 9.5.4 部分测试数据与输出结果 239 第10章 2006年中山大学内部选拔赛第六试试题分析 241 10.1 黑白树（难度：★★★★☆） 241 10.1.1 试题 241 10.1.2 题目分析与算法实现 242 10.1.3 参考程序与程序分析 242 10.1.4 部分测试数据与输出结果 245 10.2 括号表达式（难度：★★★★★） 246 10.2.1 试题 246 10.2.2 题目分析与算法实现 247 10.2.3 参考程序与程序分析 249 10.2.4 部分测试数据与输出结果250 10.3 跳格游戏（难度：★★★☆☆） 252 10.3.1 试题 252 10.3.2 题目分析与算法实现 253 10.3.3 参考程序与程序分析 254 10.3.4 部分测试数据与输出结果 256 10.4 达芬奇密码（难度：★★★☆☆） 257 10.4.1 试题 257 10.4.2 题目分析与算法实现 258 10.4.3 参考程序与程序分析 259 10.4.4 部分测试数据与输出结果 262 10.5 城堡（难度：★★★★★） 264 10.5.1 试题264 10.5.2 题目分析与算法实现 265 10.5.3 参考程序与程序分析 266 10.5.4 部分测试数据与输出结果 272 附录A 中国内地高校参加ACM/ICPC全球总决赛成绩 （1997-2010年） 274 附录B 中山大学ACM/ICPC集训队选拔流程图 275 参考文献 276 作者简介 277