由著名的信息学奥林匹克竞赛金牌教练，国务院特殊津贴专家王建德老师，和ACM-ICPC中国赛区指导委员会成员吴永辉老师联合编写，本书的读者对象是参加奥林匹克信息学竞赛（ACM-ICPC）的选手及大学、中学的编程爱好者团体，旨在通过对多年的决赛试题进行详细分析及解答，使参赛选手迅速掌握比赛的思路要领，并帮助其迅速提高算法、编程的水平，在竞赛中获得优异的成绩。
本书是备战ACM-ICPC等各类程序设计竞赛的指导教材，也是大学计算机专业数据结构课程和算法课程的优秀参考书。
ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，ACM-ICPC）是由国际计算机协会（Association for Computing Machinery，ACM）主办的国际性大学生计算机学科竞赛，旨在向全世界大学生提供一个展示团队创新精神和历练编程解题能力的机会。参赛对象为本科一年级到硕士研究生二年级的学生。竞赛以大学为单位，3人一队，每年秋季先在各大洲进行各级预选赛，从中选拔优胜队参加第二年春季的世界总决赛。这项赛事受到全球大学的普遍重视。自1977年以来已经连续举办了36届，赛事规模增长迅速。在1996～1997赛季，ACM在上海举办第一场在中国大陆的亚洲区预赛，而那一年在全球只有560所大学的840支队伍参加了比赛；而到了2009～2010赛季，全球6大洲共82个国家和地区，1931所大学的7319支队伍参加了各级比赛。这些年来，ACM-ICPC在中国大陆的比赛规模逐年扩大，参加的学校和参赛的队伍逐年增加，影响也越来越大。1996～2001年上海大学连续主办了六届亚洲区域赛；2002～2004年中国大陆增加到两个赛区；2005～2006年增加到3个赛区；2007年增加到4个赛区；而从2008年起，中国大陆每年秋季有5个赛区进行预赛。现在ACM国际大学生程序设计竞赛已经成为全世界范围内历时长久、规模宏大、影响广泛的权威性的大学生程序设计竞赛。
自1996年ACM-ICPC竞赛进入中国大陆时，复旦大学每年都参加这项赛事，自2001年每年入围ACM-ICPC世界总决赛；且2006年至今每年为ACM-ICPC亚洲区预赛命题。
为了调研ACM-ICPC在大学生中的影响，我们特意关注了网上大学生们对ACM活动的议论，顿感一股清风扑面而来：有的学生一投入ACM活动就遁入“痴迷”状态，说自己开始了一场与ACM的“精神恋爱”；有的学生动情地说：有一种感动，叫做ACM，在这种感动中有坚持、有承受、有成长。甚至有的学生将ACM活动解读成“ACM精神”。我们非常赞同这些学生的说法，ACM活动确实培育了这样的一种精神：从寻求梦想、追随激情到精诚合作、永不言败的团队精神；从汇通中英文和相关知识到“真刀真枪做题”的实践精神；从浅尝辄止到深思熟虑、别出心裁、独具慧眼、研辨解题方法是非的创新精神。ACM赛事受到各国大学生的青睐，在ACM活动中，他们表现出关注、活跃、热心、痴情等积极主动的情绪体验，我们认为至少有两个原因：
1）ACM活动让大学生直面将来可能遇到的各种问题，对他们的未来生存能力是一种历练，需要他们动脑思考、动手操作，需要多感官参与、多种心理能力的投入，在活动中学，在做中学，主动地学，创造性地学。
2）用于培训和竞赛的试题，特别是世界总决赛的试题水平较高，这些试题知识基础面宽，涵盖了计算几何、数论、组合数学、搜索技术、动态规划、图论等方方面面。所有试题将知识“返璞归真”于问题背景，还原成现实生活中的事例，既有趣又新颖，要求解题者面对实际寻求一种合适的解决方法，而不在乎方法本身的难易程度如何。虽然解题需要依托一定的基础知识，但不能死套条条框框和现成模式。它要求解题者有思想和睿智、有方法和策略、有编程的经历和经验，能洞察其间隐藏着的规律，灵活机动地解题。各国、各地区的ACM-ICPC试题和测试数据竞相登录Internet，在全球各个角落，人们可以通过终端随时查询异国异地的竞赛资料，只要按动鼠标就可以置身于任何一场竞赛之中。众多试题在网络上共享，不仅为参与ACM活动的高校提供了取之不竭、用之不尽的培训信息，而且也可作为实例或考题供许多大学在进行程序设计课程教学时使用，极大地丰富了世界计算机教育的课程资源。
本书收录了连续八届全球总决赛（2004～2011年）的83道试题及其解析。建议读者按下述步骤阅读：
首先是阅读试题，但不要急于看下面的算法分析，先把自己置于“没路”和“只有荆棘”的情境之中，自己思考一下解题方法，培养“路是从没路的地方踩踏出来的，从只有荆棘的地方开辟出来的”的探索与开拓精神。有了想法后，再与书中的方法对照一下，看看是否正确，效率怎样。这样做既可以客观地衡量自己的能力，也能真正地从书中得到更多启示，汲取更多养分。
看完试题和解析之后可以进入第二步：如果你觉得其中一些试题有用且对它们感兴趣，愿意付出时间，就不妨试着做一下，但最好不要依葫芦画瓢。在正确的思想指导下可以多阅读一些程序范例，多上机解题，特别是多做大题和难题，使自己解决实际问题的能力有所提高。
最后一步是温习。回过头来复习一下试题所涉及的知识，温故知新，可以使自己对这些知识的内涵、适用范围和应用方法多一点切身感受，少一点陌生和困惑。
我们之所以建议读者这样做，是因为问题的表示往往比答案更重要。书中的解析和程序只不过是数学或实验的一种结果形式。解题的途径绝非书中所述的一种，书上大多数试题没有固定的模式可套，全靠解题者应“题”而行，相机而动。在看完书中的解题方法之后，不妨回到起点对问题重新定义，从某个新的角度重新思考，激发解题的动力和突破“盒子”思考问题的创造思想，组合学过的算法和数据结构知识，通过语言和编程技术使想法变成计算机的系统实现，在试题和编程解题之间架设一座真正属于自己的桥梁。
著名科学家爱因斯坦曾说过，“想象力比知识更重要，因为知识是有限的，而想象力囊括着世界上的一切，推动着进步，并且是知识的源泉”。虽然这本书可以帮助读者拓展知识面，但这并不是终极目的。“纸上得来终觉浅，绝知此事要躬行”，本书的目的是要培养读者在不同问题情景下的编程实践能力，提高读者自主思考、提出问题、拓展思路、探索新知的创造力。因为这些知识和能力才是我们在未来知识经济时代中最能体现“自我”的价值所在，一旦与社会需求融合，将形成一种任何生产资料都无法取代，并且能产生巨大效益的智力资源。
需要说明的是，本书是在复旦大学ACM集训队长期活动的基础上积累而成的，每道程序都通过了严格的测试验证，其中一些程序经多次修改，精益求精。本书主要由吴永辉、王建德编著，程序编写工作分配为：杨溢、李明韫编写了2004～2008年ACM-ICPC世界总决赛试题程序，张一博、王禹、何羿宏、于竟成等编写了2009～2011年ACM-ICPC世界总决赛的试题程序。还有不少人为本书的出版付诸了辛勤的劳动，做出了不可或缺的贡献。在此，向他们表示由衷的感谢。
由于时间和水平所限，书中难免存在缺点和错误，表述不当和笔误也在所难免，恳切希望学术界同仁或读者指正。如果你在阅读中发现了问题，请通过书信或电子邮件告诉我们，以便我们及时整理成勘误表放在本书的专门网站上，供广大读者查询更正。我们更期望读者对本书提出建设性意见，以便再版时改进。我们的联系方式是：
通信地址：上海市邯郸路220号复旦大学计算机科学技术学院 吴永辉
邮编：200433
E-mail：yhwu@fudan.edu.cn
王建德 吴永辉
2012年4月于上海
计算机\程序设计
勒口文字（后勒）
本书给出了从2004年到2011年连续8届的ACM-ICPC世界总决赛的全部试题的解题分析和带有详尽注解的解答程序。
勒口（前勒）
放作者简介。
封底文字
本书是备战ACM-ICPC等各类程序设计竞赛的指导教材，也是大学计算机专业数据结构课程和算法课程的优秀参考书。
本书特色
本书将试题解析按年度划分，每一年度的总决赛试题为一章，而每一道试题的解析作为一节。如果读者以总决赛试题作为套题进行队内对抗比赛，则可以基于本书进行深入的分析和总结，不仅可以有效地提高个人能力，还可以有效地提高团队的能力。
本书给出的试题解析详尽而细致，程序代码带有详尽的注解。这使得本书可以面向各个阶层的广大的读者，不仅可以让编程高手能从中受益，而且入门不久的同学也能比较轻松地学习，有效地提高通过编程解决问题的能力。
在本书中，所有的总决赛试题都给出中文的题面描述，便于读者在使用和训练中对试题的理解。
吴永辉 王建德 杨溢 李明韫 等编著：暂无简介
前言
第1章 2004 ACM-ICPC
世界总决赛试题解析 1
试题1-1 蚂蚁Carl（Carl the Ant） 1
试题1-2 直升机机场（Heliport） 5
试题1-3 六面视图
（Image Is Everything） 10
试题1-4 危险的布拉格城
（Insecure in Prague） 14
试题1-5 相交的时间段
（Intersecting Dates） 18
试题1-6 拼接地图
（Merging Maps） 21
试题1-7 导航（Navigation） 26
试题1-8 道路绿化
（Tree-Lined Streets） 30
试题1-9 悬吊！（Suspense!） 33
试题1-10 地面飞行控制中心
（Air Traffic Control） 37
第2章 2005 ACM-ICPC
世界总决赛试题解析 43
试题2-1 眼球弯曲
（Eyeball Benders） 43
试题2-2 GSM网络的简化模型
（Simplified GSM Network） 49
试题2-3 裁判员的旅行问题（The
Traveling Judges Problem） 53
试题2-4 纸牌戏法
（cNteSahruPfefrlefe） 57
试题2-5 阳光普照
（Lots of Sunlight） 60
试题2-6 交叉的街道
（Crossing Streets） 64
试题2-7 铺满平面
（Tiling the Plane） 68
试题2-8 长城游戏
（The Great Wall Game） 71
试题2-9 讨论会（Workshops） 74
试题2-10 通信服务区（Zones） 77
第3章 2006 ACM-ICPC
世界总决赛试题解析 81
试题3-1 最小费用的飞机旅行
（Low Cost Air Travel） 81
试题3-2 订购冰激凌薄饼片！
（Remember the A La Mode!） 84
试题3-3 稳态的雕塑
（Ars Longa） 88
试题3-4 二段数（Bipartite Numbers） 92
试题3-5 压缩二进制消息
（Bit Compressor） 94
试题3-6 构造一个时钟
（Building a Clock） 96
试题3-7 朝圣（Pilgrimage） 102
试题3-8 口袋数（Pockets） 106
试题3-9 隔离度
（Degrees of Separation） 113
试题3-10 通信路线（Routing） 115
第4章 2007 ACM-ICPC
世界总决赛试题解析 120
试题4-1 基因计算（Consanguine Calculations） 120
试题4-2 集装箱（Containers） 124
试题4-3 宏大的平面图
（Grand Pix） 126
试题4-4 提花电路
（Jacquard Circuits） 130
试题4-5 领取行李
（Collecting Luggage） 135
试题4-6 小球游戏
（Marble Game） 140
试题4-7 网络（Network） 147
试题4-8 可视的屋顶部分
（Raising the Roof） 150
试题4-9 水箱（Water Tanks） 156
试题4-10 隧道（Tunnels） 161
第5章 2008 ACM-ICPC
世界总决赛试题解析 165
试题5-1 空调机械公司（Air
Conditioning Machinery） 165
试题5-2 都是整数解（Always an Integer） 169
试题5-3 传送带（Conveyor Belt） 172
试题5-4 猎犬追兔游戏（The Hare
and the Hounds） 178
试题5-5 哈夫曼编码
（Huffman Codes） 183
试题5-6 Glenbow博物馆
（Glenbow Museum） 188
试题5-7 神经网络（Net Loss） 190
试题5-8 画家（Painter） 195
试题5-9 可疑的密码（Password Suspects） 201
试题5-10 天空是极限
（The Sky is the Limit） 206
试题5-11 蒸汽压路机
（Steam Roller） 210
第6章 2009 ACM-ICPC
世界总决赛试题解析 216
试题6-1 一个周全的调度
（A Careful Approach） 216
试题6-2 判别电路故障
（My Bad） 218
试题6-3 蚂蚁Carl又回来了
（The Return of Carl） 225
试题6-4 管道内径
（Conduit Packing） 229
试题6-5 运费稳定
（Fare and Balanced） 233
试题6-6 防鹿围栏
（Deer-Proof Fence） 238
试题6-7 纸牌的房屋
（House of Cards） 241
试题6-8 多数部长的投票（The
Ministers' Major Mess） 248
试题6-9 弹簧撑杆
（Struts and Springs） 252
试题6-10 地铁的时间估算
（Subway Timing） 256
试题6-11 后缀替换语法
（Suffix-Replacement
Grammars） 260
第7章 2010 ACM-ICPC
世界总决赛试题解析 263
试题7-1 求值apl表达式！
（APL Lives!） 263
试题7-2 条形码（Barcodes） 275
试题7-3 生物机器人的轨迹
（Tracking Bio-bots） 281
试题7-4 城堡（Castles） 284
试题7-5 渠道（Channel） 288
试题7-6 等高线地图
（Contour Mapping） 297
试题7-7 岛屿（The Islands） 302
试题7-8 下雨（Rain） 306
试题7-9 冰上机器人
（Robots on Ice） 311
试题7-10 分享巧克力
（Sharing Chocolate） 315
试题7-11 镇纸（Paperweight） 318
第8章 2011 ACM-ICPC
世界总决赛试题解析 325
试题8-1 加或乘
（To Add or to Multiply） 325
试题8-2 仿射的混乱
（Affine Mess） 329
试题8-3 古代的象形符号
（Ancient Messages） 334
试题8-4 芯片的难题
（Chips Challenge） 338
试题8-5 咖啡枢纽
（Coffee Central） 343
试题8-6 机器公司
（Machine Works） 346
试题8-7 魔杖（Magic Sticks） 351
试题8-8 你心爱的采矿业（Mining Your Own Business） 357
试题8-9 疯狂木乃伊
（Mummy Madness） 360
试题8-10 金字塔（Pyramids） 365
试题8-11 垃圾迁移
（Trash Removal） 368
