前言

ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM/ICPC）是由国际计算机界历史悠久、颇具权威性的组织ACM学会（Association for Computer Machinery）主办的，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该项竞赛从1970年举办至今已历34届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视，并受到全世界各著名IT企业的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事。ACM所颁发的获奖证书也为世界各知名大学、各著名IT企业所认可。该项竞赛分为区域预赛和世界决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的3—4月举行，而区域预赛安排在上一年的9—12月在各大洲举行。ACM/ICPC的区域预赛是规模很大，范围很广的赛事，以2010年为例，全世界有88个国家和地区、2070所大学、8305支参赛队在六大洲的37个赛站中争夺世界决赛的105个名额，其激烈程度可想而知。

与其他编程竞赛相比，ACM/ICPC题目难度更大，更强调算法的高效性，不仅要解决一个指定的命题，而且必须以最佳的方式解决指定的命题；它涉及的知识面广，与大学计算机系本科及研究生课程直接关联，如程序设计、离散数学、数据结构、人工智能、算法分析与设计等；课程对数学要求更高；由于采用英文命题，对英语要求较高；ACM/ICPC采用3人合作、公用一台电脑，所以它更强调团队协作精神；由于许多题目并无现成的算法，需要具备创新的精神，ACM/ICPC不仅强调学科的基础，更强调全面素质和能力的培养；由于ACM/ICPC是采用5小时全封闭式竞赛，参赛队员与外界完全隔离，独立完成，是参赛队员实际能力的真实表露，其成绩可信度甚高。ACM/ICPC又是一种“开卷考试”，可以带任何书籍、资料甚至源程序代码清单（但不能带电子媒体），不需要死背算法，而强调的是算法的灵活运用；与其他计算机竞赛（如软件设计，网站设计等）相比，ACM/ICPC有严谨而客观的评判规则（严格的数据测试），排除了因评委的主观因素而造成评审不公平的现象，所以，ACM/ICPC对成绩的争议较少。

中山大学自1997年首次参加ACM/ICPC亚洲区预赛以来的14年中，每年都派出多支队共参加过57次亚洲区预赛，成绩有48次在前6名（6次在前10名），其中26次进入三甲，夺得6次冠军（1999年台北，2002、2003年高雄，2007年岘港，2009年合肥，2010年成都）、9次亚军（2000年香港、筑波，2003年北京、广州，2006年河内，2007年首尔，2008年雅加达、首尔，2009年宁波）、11次季军（1998—2000年上海、2001年达卡、2002年北京，2003年高雄，2004年马尼拉，2005年台北、北京，2006年首尔，2007年成都）。中山大学的参赛队12次进入全球总决赛（1999—2001年、2003—2011年）：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届全球总决赛中获得世界第10名并再获铜牌；2011年在美国佛罗里达州奥兰多市举行的第35届全球总决赛中获得世界第13名。

为了有助于高等院校的大学生备战国际大学生程序设计竞赛，使其进一步提高程序设计水平和分析问题与解决问题的能力，我们编写了这套《国际大学生程序设计竞赛例题解》。本书是这套《国际大学生程序设计竞赛例题解》的第八册，编程所用的语言版本是Microsoft Visual C++。全书共分9章，本书收录了2007—2009年广东省青少年信息学奥林匹克竞赛（GDKOI、GDOI、GDSOI）的全部试题、完整的测试数据和答案。为了方便读者学习，本书对每个题目做了详尽的题目分析，并详细地讲解其算法实现的原理，同时提供了完善的参考程序及其程序分析，供读者参考。书中提供了基本测试数据，以方便读者测试自行完成上述题目的结果。随书附带的光盘备有所有例题中完整的测试数据，以便有更多需求的同学能利用规模更大的测试数据进行训练和学习。参与上述竞赛的命题的有：张子臻、吴毅、刘祖立、翁雨键、梁志荣、刘曦、涂德健、黄硕、熊鹰扬、张瑞文、周贤豪、陈宇恒、陈才斌、张钊毅、江泽斌、杨飞雕、赵浩泉等，他们大部分是硕士研究生，都是参加过世界决赛或亚洲多个赛站区域预赛并取得很好成绩的中山大学队的主力队员。

本书由中山大学郭嵩山教授和他指导的3位研究生撰写，郭嵩山老师是国际大学生程序设计竞赛中山大学队的主教练，3位研究生是参加过全球总决赛或亚洲多个赛站区域预赛并取得很好成绩的中山大学队的主力队员。作者期望能将自己的知识、经验、心得和体会，奉献给广大的程序设计爱好者，以便与大家共同探讨和交流。

本书所提供的题目全部为原创题，题目构思新颖、涉及的算法知识面广，基本上覆盖大学计算机类本科专业所学到的基本算法。本书可以作为高等院校大学生和研究生准备参加各级国际大学生程序设计竞赛活动的辅导教材及训练题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考书，并适于作为中学省级以上信息学奥林匹克优秀选手备战高层次程序设计竞赛的参考用书。

由于我们水平所限，书中难免有不足之处，欢迎读者批评指正，谢谢！

作者

2011年8月