基本信息
内容简介
书籍
计算机书籍
本书收录了2008—2009年广东省大学生程序设计竞赛(GDCPC2008—2009，即ACM／ICPC广东省赛)及第33届ACM／ICPC亚洲成都赛区预选赛的全部试题、完整的测试数据和答案。为了方便读者学习，本书对每个题目作了详尽的题目分析，并详细地讲解其算法实现的原理，同时提供了完善的参考程序及其程序分析，供读者参考。书中提供了基本测试数据，以方便读者测试自行完成上述题目的结果。随书附带的光盘存放了所有例题中完整的测试数据，以便于有更高、更严格要求的同学能利用规模更大的测试数据进行训练和学习。
本书所提供的题目都是原创题，题目构思新颖，内容有趣。所涉及的算法知识面广，基本上覆盖大学计算机类本科专业所学到的基本算法。本书可以作为高等院校大学生和研究生准备参加各级国际大学生程序设计竞赛活动的辅导教材和训练题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考书，同时还可以作为中学省级及以上信息学奥林匹克优秀选手备战高层次程序设计竞赛的参考用书。
计算机书籍
本书收录了2008—2009年广东省大学生程序设计竞赛(GDCPC2008—2009，即ACM／ICPC广东省赛)及第33届ACM／ICPC亚洲成都赛区预选赛的全部试题、完整的测试数据和答案。为了方便读者学习，本书对每个题目作了详尽的题目分析，并详细地讲解其算法实现的原理，同时提供了完善的参考程序及其程序分析，供读者参考。书中提供了基本测试数据，以方便读者测试自行完成上述题目的结果。随书附带的光盘存放了所有例题中完整的测试数据，以便于有更高、更严格要求的同学能利用规模更大的测试数据进行训练和学习。
本书所提供的题目都是原创题，题目构思新颖，内容有趣。所涉及的算法知识面广，基本上覆盖大学计算机类本科专业所学到的基本算法。本书可以作为高等院校大学生和研究生准备参加各级国际大学生程序设计竞赛活动的辅导教材和训练题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考书，同时还可以作为中学省级及以上信息学奥林匹克优秀选手备战高层次程序设计竞赛的参考用书。
作译者
郭嵩山，男，1945年4月出生，1967年毕业于上海交通大学无线电技术专业，中山大学信息科学与技术学院计算机科学系教授，主要从事计算机操作系统的教学和研究。主要著作有电子工业出版社出版的(BIO结构分析教程》、《DOS内核结构分析教程》、《COMMAND结构分析教程》、(Windows9810结构分析教程》、《国际大学生程序设计竞赛例题解(一)——数论、计算几何、搜索算法专集》、《国际大学生程序设计竞赛例题解(二)——广东省大学生程序设计竞赛试题(2003—2005年)》、《国际大学生程序设计竞赛例题解(三)——图论、动态规划算法、综合题专集》、国际大学生程序设计竞赛例题解(四)——广东省信息学奥林匹克竞赛试题(2003—2006年)》、《国际大学生程序设计竞赛例题解(五)--V东省大学生程序设计竞赛试题(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年第3l届ACM／ICPC亚洲上海赛区银奖。
2008年第32届ACM／ICPC亚洲南京赛区第7名(金牌)，北京赛区银奖。
2009年第33届ACM／ICPC亚洲哈尔滨赛区第6名(金牌)。
2009年第33届ACM／ICPC亚洲吉隆坡赛区第4名。
吴毅，男，1985年3月出生，2004年9月被保送入中山大学计算机科学系攻读学士学位。2008年9月被保送入中山大学计算机科学系攻读硕士学位。在校期间，曾多次代表中山大学参加ACM国际大学生程序设计竞赛(ACM／ICPC)。荣获：
2005年第30届ACM／ICPC亚洲北京赛区第5名(金牌)。
2006年第31届ACM／ICPC亚洲河内赛区亚军。
2007年第31届ACM／ICPC全球总决赛并列第26名。
2007年第32届ACM／ICPC亚洲首尔赛区亚军。
2008年第33届ACM／ICPC亚洲首尔赛区并列第2名。
2009年第33届ACM／ICPC全球总决赛并列第20名。
郭嵩山主持广东省信息学奥林匹克竞赛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年第3l届ACM／ICPC亚洲上海赛区银奖。
2008年第32届ACM／ICPC亚洲南京赛区第7名(金牌)，北京赛区银奖。
2009年第33届ACM／ICPC亚洲哈尔滨赛区第6名(金牌)。
2009年第33届ACM／ICPC亚洲吉隆坡赛区第4名。
吴毅，男，1985年3月出生，2004年9月被保送入中山大学计算机科学系攻读学士学位。2008年9月被保送入中山大学计算机科学系攻读硕士学位。在校期间，曾多次代表中山大学参加ACM国际大学生程序设计竞赛(ACM／ICPC)。荣获：
2005年第30届ACM／ICPC亚洲北京赛区第5名(金牌)。
2006年第31届ACM／ICPC亚洲河内赛区亚军。
2007年第31届ACM／ICPC全球总决赛并列第26名。
2007年第32届ACM／ICPC亚洲首尔赛区亚军。
2008年第33届ACM／ICPC亚洲首尔赛区并列第2名。
2009年第33届ACM／ICPC全球总决赛并列第20名。
目录
本书试题涉及知识点的说明1
第1章第11届中山大学程序设计竞赛预选赛（2008年）试题分析3
1.1 矩阵归零（难度：★★☆☆☆）3
1.1.1试题3
1.1.2题目分析与算法实现4
1.1.3参考程序与程序分析5
1.1.4部分测试数据与输出结果5
1.2 基因（难度：★★★☆☆）6
1.2.1试题6
1.2.2题目分析与算法实现7
1.2.3参考程序与程序分析8
1.2.4部分测试数据与输出结果11
1.3 旅行（难度：★★★☆☆）12
1.3.1试题12
1.3.2题目分析与算法实现13
1.3.3参考程序与程序分析14
1.3.4部分测试数据与输出结果16
1.4 单词缩写（难度：★☆☆☆☆）16
1.4.1试题16
1.4.2题目分析与算法实现17
第1章第11届中山大学程序设计竞赛预选赛（2008年）试题分析3
1.1 矩阵归零（难度：★★☆☆☆）3
1.1.1试题3
1.1.2题目分析与算法实现4
1.1.3参考程序与程序分析5
1.1.4部分测试数据与输出结果5
1.2 基因（难度：★★★☆☆）6
1.2.1试题6
1.2.2题目分析与算法实现7
1.2.3参考程序与程序分析8
1.2.4部分测试数据与输出结果11
1.3 旅行（难度：★★★☆☆）12
1.3.1试题12
1.3.2题目分析与算法实现13
1.3.3参考程序与程序分析14
1.3.4部分测试数据与输出结果16
1.4 单词缩写（难度：★☆☆☆☆）16
1.4.1试题16
1.4.2题目分析与算法实现17
