学海网

共234页。
前言
ACM 国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，
简称 ACM/ICPC） 是由国际计算机界历史最悠久、 颇具权威性的组织 ACM 学会 （Association for Computer Machinery）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计 竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。 该项竞 赛从 1970 年举办至今已历 25 届，因历届竞赛都荟萃了世界各大洲的精英， 云集了计算机界 的“希望之星” ，而受到国际各知名大学的重视，并受到全世界各著名计算机公司的高度关 注，成为世界各国大学生最具影响力的国际级计算机类的赛事，ACM 所颁发的获奖证书也 为世界各著名计算机公司、各知名大学所认可。该项竞赛分区域预赛和世界决赛两个阶段进 行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的 3~4 月举行，而 区域预赛安排在上一年的 9 月~12 月在各大洲举行。ACM/ICPC 的区域预赛是规模很大，范 围很广的赛事，近几年，全世界有 1000 多所大学，近 2000 支参赛队在六大洲的 28~30 个赛 站中争夺世界决赛的 60 个名额，其激烈程度可想而知。
与其他编程竞赛相比，ACM/ICPC 题目难度更大，更强调算法的高效性，不仅要解决
一个指定的命题，而且必需要以最佳的方式解决指定的命题；它涉及知识面广，与大学计算
机系本科以及研究生如程序设计、离散数学、数据结构、人工智能、算法分析与设计等相关
课程直接关联，对数学要求更高，由于采用英文命题，对英语要求较高，ACM/ICPC 采用 3
人合作、共用一台电脑，所以它更强调团队协作精神；由于许多题目并无现成的算法，需要
具备创新的精神，ACM/ICPC 不仅强调学科的基础，更强调全面素质和能力的培养；由于
ACM/ICPC 是采用 5 小时全封闭式竞赛，参赛队员与外界完全隔离，完全独立完成，没有任
何水份，是其实际能力的真实表露，其成绩可信度甚高；但 ACM/ICPC 又是一种“开卷考 试” ，可以带任何书籍、资料甚至源程序代码清单（但不能带软盘），不需要去死背算法，而 强调的是算法的灵活运用； 与其它计算机竞赛 （如软件设计， 网站设计等） 相比， ACM/ICPC 有严谨而客观的评判规则（严格的数据测试），排除了因评委的主观因素而造成评审不公平 的现象，所以，ACM/ICPC 对成绩的争议较少，大家比较心服口服。
综观近三年（1998~2000）中山大学共参加了 6 次地区预赛，成绩全部在三甲之列：连 续三年夺得上海站季军（1999~2000 年还连续两年夺得上海站第四名）、夺得台北站冠军、香港站亚军和日本站亚军；并连续三年争得了世界决赛权。并在第 24 届（2000 年）在美国 佛罗里达州奥兰多市举行世界决赛中夺得了第 11 名的好成绩，在第 25 届（2001）在加拿大 温哥华市举行的世界决赛中首获铜牌（世界第 14 名） 。
为了帮助高等院校的大学生们备战国际大学生程序设计竞赛， 帮助他们提高程序设计水 平和培养更强的分析问题和解决问题的能力，我们编写了这本辅导教材。本书所用的语言是 Pascal（Delphi）。全书共分六章，第 1 章先介绍 Delphi 的运行环境，以便于读者能更好地读 通后面各章的程序；第 2 章采用精讲的方式，简明扼要、深入浅出地介绍了在国际大学生程 序设计竞赛中经常用到的各种典型算法； 而在第 3 章中， 我们着重介绍了寻找最优解的算法， 诸如图论中的搜索算法和如何运用动态规划的思维来解决实际问题等方法； 在第 4 章中，我 们从 ACM/ICPC 世界决赛和区域预赛试题中精选了有代表性的 10 道例题， 通过对例题的详 细分析，力图让读者能更深刻地理解第 2、3 章中所介绍的基本算法；在第 5 章中，我们精 选了一批有代表性的试题作为习题，并为这些习题设计了严格的、有梯度的测试数据，以便 于读者检验自己编程的正确性；而在第 6 章中，我们给出了这些习题的详细分析和解答。为 便于读者们学习和理解，本书的全部例题和习题都给出了我们自己编写的参考程序， 而所有 参考程序都有详细的注释。
参加编写本书的 4 位作者，第一位是国际大学生程序设计竞赛中山大学队的教练，其余 3 位都是参加过多次世界决赛和亚洲多个赛站区域预赛的中山大学队的主力队员。他们都是 在校的研究生，我们期望能将自己的知识、经验、心得和体会，奉献给广大的程序设计爱好 者，以便与大家共同探讨和交流。
本书可以作为高等院校大学生和研究生们准备参加各级国际大学生程序设计竞赛活动 的辅导教材和试题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考 书，也可以作为省级及以上信息学奥林匹克优秀选手准备高层次程序设计竞赛的参考用书。 中山大学计算机科学系 97 级孔颖同学（也是参加过两次世界决赛和亚洲多个赛站区域
预赛的中山大学队的主力队员） 曾参与过本书的一些程序的编写工作， 在此表示衷心的感谢。
由于我们水平所限，书中难免有不足之处，欢迎读者批评指正，谢谢！
作者
2001 年 10 月
国际大学生程序设计竞赛辅导教程


目录
前言……………………………………………………1
第一章 Delphi 简介................................................1
第一节 Delphi 的运行环境................................1
第二节 Delphi 常量...........................................5
第三节 Delphi 变量...............................................5
第四节 Delphi 类型....................................................6
第五节 Delphi 的基本语句..................................11
第六节 Delphi 函数与过程...............................15
第七节 函数的递归...................................................17
第八节 面向对象 Object Pascal............................................18
第九节 Delphi 中使用嵌入汇编..............................19
第二章 基本算法介绍...........................................21
第一节 概述................................................21
第二节 常用数据结构在 Delphi 中的实现...21
第三节 枚举算法...................................................32
第四节 回溯算法................................................33
第五节 贪心算法.........................................................35
第六节 分治算法...................................................38
第七节 数值计算..........................................................39
第八节 计算几何....................................................47
第九节 模拟题解法.........................................................51
第三章 寻找最优解的算法............................................53
第一节 动态规划...................................................53
第二节 最短路问题................................................61
第三节 搜索算法.......................................................70
第四章 国际大学生程序设计竞赛（ACM/ICPC）试题及分析.............89
第一节 生成字符串...................................................89
第二节 模式识别的“中心”问题..................................94
第三节 划分凸多边形.................................................98
第四节 防卫导弹.....................................................100
第五节 邮票问题.....................................................104
第六节 骨牌矩阵.....................................................107
第七节 师生树....................................................113
第八节 旅游预算...............................................119
第九节 正整数竖式除法......................................127
第十节 移棋子...................................................131
第五章 习题........................................141
第一节 习题...............................................................141
第二节 部分习题测试数据及参考答案.................151
国际大学生程序设计竞赛辅导教程

第六章 习题解答.......................................................173
第一节 电子表格 ( Table ) ..........................................173
第二节 DEL 命令 (DEL)..............................................176
第三节 分割方格 (Divide) .........................................181
第四节 信息编码 (Decode)...........................................189
第五节 海上交通控制 ( Lane ) ......................................191
第六节 投递最佳路线(Best Deliver) .............................199
第七节 计算机网络连接(computer network).................206
第八节 联系圈(Circle) .......................................210
第九节 球钟(Ball Clock).........................213