国际大学生程序设计竞赛例题解(6):广东省大学生程序设计竞赛试题解(2008-2009年) (平装) 9787121107276

《国际大学生程序设计竞赛例题解(6):广东省大学生程序设计竞赛试题解(2008-2009年)》收录了2008-2009年广东省大学生程序设计竞赛（GDCPC 2008-2009,既ACM/ICPC）广东省赛及第33届ACM/ICPC亚洲成都赛区预选赛的全部试题、完整的测试教学数据和答案。为了方便读者学习，《国际大学生程序设计竞赛例题解(6):广东省大学生程序设计竞赛试题解(2008-2009年)》对每个题目作了详尽的题目分析，并详细地讲解其算法实现的原理，同时提供了完善的参考程序及其程序分析，供读者参考。书中提供了基本测试数据，以方便读者测试自行完成上述题目的结果。随书附带的光盘存放了所有例题中完整的测试数据，以便于有更高、更严格要求的同学能利用规模更大的测试数据进行训练和学习。 《国际大学生程序设计竞赛例题解(6):广东省大学生程序设计竞赛试题解(2008-2009年)》是由电子工业出版社出版的。 郭嵩山，男，1945年4月出生，1967年毕业于上海交通大学无线电技术专业，中山大学信息科学与技术学院计算机科学系教授，主要从事计算机操作系统的教学和研究。主要著作有电子工业出版社出版的《BIO结构分析教程》、《DOS内核结构分析教程》、《COMMAND结构分析教程》、《Windows98IO结构分析教程》、《国际大学生程序设计竞赛例题解（一）——数论、计算几何、搜索算法专集》、《国际大学生程序设计竞赛例题解（二）——广东省大学生程序设计竞赛试题（2003-2005年）》、《国际大学生程序设计竞赛例题解（三）——图论、动态规划算法、综合题专集》、国际大学生程序设计竞赛例题解（四）——广东省信息学奥林匹克竞赛试题（2003-2006年）》、《国际大学生程序设计竞赛例题解（五）——广东省大学生程序设计竞赛试题（2006-2007年）》，人民邮电出版社出版的《数据结构及其应用》，中山大学出版社出版的《青少年信息学奥林匹克竞赛广东试题及解答（1986-1994）》，北京大学出版社出版的《国际大学生程序设计竞赛辅导教程》等。 郭嵩山主持广东省信息学奥林匹克竞赛20余年，制定了公开、公正、公平的，科学化、规范化的广东省信息学奥林匹克竞赛条例，广东省一直被公认为是信息学奥林匹克竞赛全国普及活动开展最好的省份之一，也是全国竞赛水平最高的省份之一。近12年来，郭嵩山担任ACM国际大学生程序设计竞赛中山大学队主教练，中山大学队在1999-2001、2003-2009年10次获得全球总决赛的决赛权，并在全球总决赛中取得好成绩。近几年，郭嵩山担任ACM国际大学生程序设计竞赛（ACM／ICPC）广东省赛区执行主席，主持7届ACM／ICPC广东省赛。在科研方面，郭嵩山指导多名硕士研究生在人工智能算法研究及应用方面取得较好的成果。 翁雨键，男，1986年2月出生，2004年9月考入中山大学计算机科学系攻读学士学位，2008年9月被保送入中山大学计算机科学系攻读硕士学位。在校期间，曾多次代表中山大学参加ACM国际大学生程序设计竞赛（ACM／ICPC）。荣获：2006年第31届ACM／ICPC亚洲上海赛区银奖。2007年第32届ACM／ICPC亚洲南京赛区第7名（金牌），北京赛区银奖。2008年第33届ACM／ICPC亚洲雅加达赛区并列第2名（金牌），杭州赛区银奖。在2009年广东省第7届大学生程序设计竞赛（GDCPC2009）担任命题组负责人。 梁志荣，男，1984年8月出生，2004.年9月考入中山大学计算机科学系攻读学士学位，2008年9月被保送入中山大学计算机科学系攻读硕士学位。在校期间，曾多次代表中山大学参加ACM国际大学生程序设计竞赛（ACM／ICPC）。荣获：2005年第30届ACM／ICPC亚洲杭州赛区银奖。2006年第31届ACM／ICPC亚洲上海赛区银奖。 本书试题涉及知识点的说明 第1章 第11届中山大学程序设计竞赛预选赛（2008年）试题分析 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 DNA重组 1.7.1 试题 1.7.2 题目分析与算法实现 1.7.3 参考程序与程序分析 1.7.4 部分测试数据与输出结果 1.8 小实的问题 1.8.1 试题 1.8.2 题目分析与算法实现 1.8.3 参考程序与程序分析 1.8.4 部分测试数据与输出结果 1.9 总体题目分析与比赛情况 1.9.1 题目分析 1.9.2 比赛情况 第2章 第6届广东省大学生程序设计竞赛暨第11届中山大学程序设计竞赛（2008）试题分析 2.1 表面积 2.1.1 试题 2.1.2 题目分析与算法实现 2.1.3 参考程序与程序分析 2.1.4 部分测试数据与输出结果 2.2 读书 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章 第12届中山大学程序设计竞赛预选赛（2009年）试题分析 3.1 SZ斐波拉契数列 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 N皇后问题 3.6.1 试题 3.6.2 题目分析与算法实现 3.6.3 参考程序与程序分析 3.6.4 参考程序与程序分析 3.7 MAX——-SAT 3.7.1 试题 3.7.2 题目分析与算法实现 3.7.3 参考程序与程序分析 3.7.4 部分测试数据与输出结果 3.8 平方数 3.8.1 试题 3.8.2 题目分析与算法实现 3.8.3 参考程序与程序分析 3.8.4 部分测试数据与输出结果 3.9 总体题目分析与比赛情况 3.9.1 题目分析 3.9.2 比赛情况 第4章 第7届广东省大学生程序设计竞赛暨第12届中山大学程序设计竞赛（2009）试题分析 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 部分测试数据与输出结果 …… 第5章 第33届国际大学生程序设计竞赛亚洲成都赛区网络预赛试题分析 第6章 第33届国际大学生程序设计竞赛亚洲成都赛区现场赛试题分析 参考文献 作者简介 ACM国际大学生程序设计竞赛（ACM International Collegiate Programming Contest，简称ACM／ICPC）是由国际计算机界历史悠久、颇具权威性的组织ACM学会（ASSOCiation forComputer Machinery）主办的，是世界上公认的规模最大、水平最高的国际大学生程序设竞赛，其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该项竞赛从1970年举办至今已历32届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视，并受到全世界各著名Ⅱ企业的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事。 ACM所颁发的获奖证书也为世界各知名大学、各著名IT企业所认可。该项竞赛分为区域预赛和世界决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的3-4月举行，而区域预赛安排在上一年的9-12月在各大洲举行。ACM／ICPC的区域预赛是规模很大、范围很广的赛事。以2008年为例，全世界有88个国家和地区、1838所大学、超过7100支参赛队在六大洲的37个赛站中争夺世界决赛的100个名额，其激烈程度可想而知。与其他编程竞赛相比，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名。 插图：