国际大学生程序设计竞赛例题解

出版时间：2008-11  出版社：郭嵩山、张子臻、 王磊 电子工业出版社 (2008-11出版)  作者：郭嵩山 等 著  页数：276  
Tag标签：无  

前言

ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM／ICPC）是由国际计算机界历史悠久、颇具权威性的组织ACM学会（Associationfor Computer Machinery）主办的，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该项竞赛从1970年举办至今已历32届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视，并受到全世界各著名IT企业的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事。ACM所颁发的获奖证书也为世界各知名大学、各著名IT企业所认可。该项竞赛分为区域预赛和世界决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的3～4月举行，而区域预赛安排在上一年的9～12月在各大洲举行。ACM／ICPC的区域预赛是规模很大、范围很广的赛事。以2007年为例，全世界有83个国家和地区、182l所大学、超过6700支参赛队在六大洲的37个赛站中争夺世界决赛的100个名额，其激烈程度可想而知。与其他编程竞赛相比，ACM／ICPC题目难度更大，更强调算法的高效性，不仅要解决一个指定的命题，而且必须以最佳的方式解决指定的命题。它涉及的知识面广，与大学计算机系本科及研究生的课程直接关联，如程序设计、离散数学、数据结构、人工智能、算法分析与设计等课程；对数学要求更高；由于采用英文命题，对英语要求较高；ACM／ICPC采用3人合作、共用一台电脑，所以它更强调团队协作精神；由于许多题目并无现成的算法，需要具备创新的精神，ACM／ICPC不仅强调学科的基础，更强调全面素质和能力的培养；由于ACM／ICPC是采用5小时全封闭式竞赛，参赛队员与外界完全隔离，独立完成，是参赛队员实际能力的真实表露，其成绩可信度甚高。.ACM／ICPC又是一种“开卷考试”，可以带任何书籍、资料甚至源程序代码清单（但不能带电子媒体），不需要死背算法，而强调的是算法的灵活运用；与其他计算机竞赛（如软件设计，网站设计等）相比，ACM／ICPC有严谨而客观的评判规则（严格的数据测试），排除了因评委的主观因素而造成评审不公平的现象，所以，ACM／ICPC对成绩的争议较少。

内容概要

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

作者简介

郭嵩山，男，1945年4月出生，1967年毕业于上海交通大学无线电技术专业，中山大学信息科学与技术学院计算机科学系教授，主要从事计算机操作系统的教学和研究。主要著作有电子工业出版社出版的《BIO结构分析教程》、《DOS内核结构分析教程》、《COMMAND结构分析教程》、《Windows 98 IO结构分析教程》、《国际大学生程序设计竞赛例题解（一）——数论、计算几何、搜索算法专集》、《国际大学生程序设计竞赛例题解（二）——广东省大学生程序设计竞赛试题解（2003-2005年）》、《国际大学生程序设计竞赛例题解（三）——图论、动态规划算法、综合题专集》、《国际大学生程序设计竞赛例题解（四）——广东省信息学奥林匹克竞赛试题选解（2003-2006年）》，2008年2月，人民邮电出版社出版的《数据结构及其应用》，中山大学出版社出版的《青少年信息学奥林匹克竞赛广东试题及解答（1986一1994）》，北京大学出版社出版的《国际大学生程序设计竞赛辅导教程》等。郭嵩山主持广东省信息学奥林匹克竞赛20余年，制定了公开、公正、公平的，科学化、规范化的广东省信息学奥林匹克竞赛条例，广东省一直被公认为是信息学奥林匹克竞赛全国普及活动开展最好的省份之一，也是全国竞赛水平最好的省份之一。近10年来，郭嵩山担任ACM国际大学生程序设计竞赛中山大学队主教练，中山大学队在1999-2001、2003-2008年9次获得全球总决赛的决赛权，并在全球总决赛中取得好成绩。近几年，郭嵩山担任ACM国际大学生程序设计竞赛（ACM／ICPC）广东省赛区执行主席，主持2003-2008年连续6届的ACM／ICPC广东省赛。在科研方面，郭嵩山指导多名硕士研究生在人工智能算法研究方面取得较好的成果。张子臻，男，1984年8月出生，2003年9月被保送入中山大学计算机科学系攻读学士学位，2007年9月被保送入中山大学计算机科学系攻读硕士学位。在学期间，曾多次代表中山大学参加ACM国际大学生程序设计竞赛（ACM／ICPC）。荣获：2004年第29届ACM／ICPC亚洲台北赛区第6名，北京赛区第8名（银牌）；2006年第31届ACM／ICPC亚洲河内赛区亚军（金牌）；2007年第31届ACM／ICPC全球总决赛（东京）第26名；2007年第32届ACM／ICPC亚洲首尔赛区亚军，北京赛区第5名（金牌）。王磊，男，1984年3月出生，2003年9月考入中山大学计算机科学系攻读学士学位，2007年9月被保送入中山大学计算机科学系攻读硕士学位。在学期间，曾多次代表中山大学参加ACM国际大学生程序设计竞赛（ACM／ICPC）。荣获：2005年第30届ACM／ICPC亚洲台北赛区第7名，北京赛区第5名（金牌）；2006年第31届ACM／ICPC亚洲河内赛区亚军（金牌）；2007年第3l届ACM／ICPC全球总决赛（东京）第26名；2007年第32届ACM／ICPC亚洲砚港赛区冠军；2008年第32届ACM／ICPC全球总决赛（班夫）第23名。汤振东，男，1984年2月出生，2003年9月考入中山大学计算机科学系攻读学士学位，2007年9月被保送入中山大学计算机科学系攻读硕士学位。在学期间，曾多次代表中山大学参加ACM国际大学生程序设计竞赛（ACM／ICPC）。荣获：2006年第31届ACM／ICPC亚洲北京赛区银牌；2007年第32届ACM／ICPC亚洲南京赛区金牌；2007年第32届ACM／ICPC亚洲北京赛区银牌。

书籍目录

本书试题涉及知识点的说明第1章 第9届中山大学程序设计竞赛预选赛（2006年）试题分析1.1 信息泛滥（难度：★★★☆☆）1.1.1 试题1.1.2 题目分析与算法实现1.1.3 参考程序与程序分析1.1.4 部分测试数据与输出结果1.2 求和（难度：★★★★☆）1.2.1 试题1.2.2 题目分析与算法实现1.2.3 参考程序与程序分析1.2.4 部分测试数据与输出结果1.3 冲突（难度：★★★★★）1.3.1 试题1.3.2 题目分析与算法实现1.3.3 参考程序与程序分析1.3.4 部分测试数据与输出结果1.4 旅馆（难度：★★★☆☆）1.4.1 试题1.4.2 题目分析与算法实现1.4.3 参考程序与程序分析1.4.4 部分测试数据与输出结果1.5 字符串子串（难度：★★☆☆☆）1.5.1 试题1.5.2 题目分析与算法实现1.5.3 参考程序与程序分析1.5.4 部分测试数据与输出结果1.6 最大公约数（难度：★★★★☆）1.6.1 试题1.6.2 题目分析与算法实现1.6.3 参考程序与程序分析1.6.4 部分测试数据与输出结果1.7 木棒（难度：★☆☆☆☆）1.7.1 试题1.7.2 题目分析与算法实现1.7.3 参考程序与程序分析1.7.4 部分测试数据与输出结果1.8 总体题目分析与比赛情况1.8.1 题目总结分析1.8.2 比赛情况第2章 第4届广东省大学生程序设计竞赛暨第9届中山大学程序设计竞赛（2006年）试题分析2.1 过剩数（难度：★☆☆☆☆）2.1.1 试题2.1.2 题目分析与算法实现2.1.3 参考程序与程序分析2.1.4 部分测试数据与输出结果2.2 L形覆盖（难度：★★☆☆☆）2.2.1 试题2.2.2 题目分析与算法实现2.2.3 参考程序与程序分析2.2.4 部分测试数据与输出结果2.3 立方块（难度：★★★★☆）2.3.1 试题2.3.2 题目分析与算法实现2.3.3 参考程序与程序分析2.3.4 部分测试数据与输出结果2.4 螺旋方阵（难度：★★☆☆☆）2.4.1 试题2.4.2 题目分析与算法实现2.4.3 参考程序与程序分析2.4.4 部分测试数据与输出结果2.5 电子书狂热者（难度：★★★★☆）2.5.1 试题2.5.2 题目分析与算法实现2.5.3 参考程序与程序分析2.5.4 部分测试数据与输出结果2.6 栅格网络流（难度：★★★★★）2.6.1 试题2.6.2 题目分析与算法实现2.6.3 参考程序及程序分析2.6.4 部分测试数据与输出结果2.7 连续边长多边形（难度：★★★☆☆）2.7.1 试题2.7.2 题目分析与算法实现2.7.3 参考程序与程序分析2.7.4 部分测试数据与输出结果2.8 饥饿的母牛（难度：★★★☆☆）2.8.1 试题2.8.2 题目分析与算法实现2.8.3 参考程序与程序分析2.8.4 部分测试数据与输出结果2.9 解析程序（难度：★★★★☆）2.9.1 试题2.9.2 题目分析与算法实现2.9.3 参考程序与程序分析2.9.4 部分测试数据与输出结果2.10 网络探测（难度：★★★☆☆）^2.10.1 试题2.10.2 题目分析与算法实现2.10.3 参考程序与程序分析2.10.4 部分测试数据与输出结果2.11总体题目分析与比赛情况2.11.1 题目总结分析2.11.2 比赛情况第3章 第10届中山大学程序设计竞赛预选赛（2007年）试题分析3.1 圣诞节（难度：★★★☆☆）3.1.1 试题3.1.2 题目分析与算法实现3.1.3 参考程序与程序分析3.1.4 部分测试数据与输出结果3.2 导弹（难度：★★☆☆☆）3.2.1 试题3.2.2 题目分析与算法实现3.2.3 参考程序与程序分析3.2.4 部分测试数据与输出结果3.3 儿童节快乐（难度：★★★★☆）3.3.1 试题3.3.2 题目分析与算法实现3.3.3 参考程序与程序分析3.3.4 部分测试数据与输出结果3.4 排列（难度：★★★☆☆）3.4.1 试题3.4.2 题目分析与算法实现3.4.3 参考程序与程序分析3.4.4 部分测试数据与输出结果3.5 兵排队（难度：★★☆☆☆）3.5.1 试试题3.5.2 题目分析与算法实现3.5.3 参考程序与程序分析3.5.4.部分测试数据与输出结果3.6 我的总结（难度：★☆☆☆☆）3.6.1 试题3.6.2 题目分析与算法实现3.6.3 参考程序与程序分析3.6.4.部分测试数据与输出结果3.7 准备工作（难度：★★★★★）3.7.1 试题3.7.2 题目分析与算法实现3.7.3 参考程序与程序分析3.7.4 部分测试数据与输出结果3.8 总体题目分析与比赛情况3.8.1 题目总结分析3.8.2 赛情况第4章 第5届广东省大学生程序设计竞赛暨第lO届中山大学程序设计竞赛（2007年）试题分析4.1 遥远的距离（难度：★★★★☆）4.1.1 试题4.1.2 题目分析与算法实现4.1.3 参考程序与程序分析4.1.4 部分测试数据与输出结果4.2 分数（难度：★☆☆☆☆）4.2.1 试题4.2.2 题目分析与算法实现4.2.3 参考程序与程序分析4.2.4 部分测试数据与输出结果4.3 并行（难度：★★★☆☆）4.3.1 试题4.3.2 题目分析与算法实现4.3.3 参考程序与程序分析第5章 中山大学集训队内部选拔赛（2004年）试题分析附录A 中国内地高校举办ACM/CPC亚洲区预赛的情况附录B 中国内地高校参加ACM/CPC全球总决赛的成绩附录C 中山大学队参加ACM/CPC亚洲区域赛历年成绩表（1997－2007年）附录D 中山大学队参加ACM/CPC总决赛历年成绩表（1999——2008年）参考文献作者简介

章节摘录

插图：

编辑推荐

《国际大学生程序设计竞赛例题解5:广东省大学生程序设计竞赛试题(2006-2007年)》所提供的题目都是原创题，题目构思新颖，内容有趣。所涉及到的算法知识面广，基本上覆盖大学计算机类本科专业所学到的基本算法。《国际大学生程序设计竞赛例题解5:广东省大学生程序设计竞赛试题(2006-2007年)》可以作为高等院校有关专业的研究生和本科学生参加国际大学生程序设计竞赛的辅导教材，也可作为高等院校有关专业相关课程的教学参考书与例题集，也特别适用于作为中学青少年信息学奥林匹克竞赛省级及省级以上优秀选手备战信息学奥林匹克竞赛的培训教材及训练题集。

用户评论 (总计2条)

•   主要是讲解广东省赛ACM题目
•   2年的省赛题的解题报告。建议搞ACM的人看看。