国际大学生程序设计竞赛中山大学内部选拔真题解

第1章 2007年中山大学内部选拔赛第一试试题分析

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 部分测试数据和输出结果

第2章 2007年中山大学内部选拔赛第二试试题分析

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 部分测试数据和输出结果

第3章 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 部分测试数据和输出结果

第4章 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 参考程序

4.3.4 部分测试数据和输出结果

4.4 质数和式（难度：★★☆☆☆）

4.4.1 问题描述

4.4.2 算法分析

4.4.3 参考程序

4.4.4 部分测试数据和输出结果

4.5 树（难度：★★★☆☆）

4.5.1 问题描述

4.5.2 算法分析

4.5.3 参考程序

4.5.4 部分测试数据和输出结果

第5章 2007年中山大学内部选拔赛第五试试题分析

5.1 水池（难度：★★☆☆☆）

5.1.1 问题描述

5.1.2 算法分析

5.1.3 参考程序

5.1.4 部分测试数据和输出结果

5.2 数字排序（难度：★★★☆☆）

5.2.1 问题描述

5.2.2 算法分析

5.2.3 参考程序

5.2.4 部分测试数据和输出结果

5.3 移动（难度：★★★★★）

5.3.1 问题描述

5.3.2 算法分析

5.3.3 参考程序

5.3.4 部分测试数据和输出结果

5.4 球星（难度：★★★☆☆）

5.4.1 问题描述

5.4.2 算法分析

5.4.3 参考程序

5.4.4 部分测试数据和输出结果

5.5 不幸运数（难度：★★★☆☆）

5.5.1 问题描述

5.5.2 算法分析

5.5.3 参考程序

5.5.4 部分测试数据和输出结果

第6章 2007年中山大学内部选拔赛第六试试题分析

6.1 树的计数（难度：★★★★☆）

6.1.1 问题描述

6.1.2 算法分析

6.1.3 参考程序

6.1.4 部分测试数据和输出结果

6.2 九数码（难度：★★☆☆☆）

6.2.1 问题描述

6.2.2 算法分析

6.2.3 参考程序

6.2.4 部分测试数据和输出结果

6.3 数列（难度：★★★☆☆）

6.3.1 问题描述

6.3.2 算法分析

6.3.3 参考程序

6.3.4 部分测试数据和输出结果

6.4 国王（难度：★★★☆☆）

6.4.1 问题描述

6.4.2 算法分析

6.4.3 参考程序

6.4.4 部分测试数据和输出结果

6.5 面积（难度：★★★☆☆）

6.5.1 问题描述

6.5.2 算法分析

6.5.3 参考程序

6.5.4 部分测试数据和输出结果

第7章 2008年中山大学内部选拔赛第一试试题分析

7.1 PPMM（难度：★★★☆☆）

7.1.1 问题描述

7.1.2 算法分析

7.1.3 参考程序

7.1.4 部分测试数据和输出结果

7.2 三角形计算（难度：★★★★☆）

7.2.1 问题描述

7.2.2 算法分析

7.2.3 参考程序

7.2.4 部分测试数据和输出结果

7.3 生成字符串（难度：★★★☆☆）

7.3.1 问题描述

7.3.2 算法分析

7.3.3 参考程序

7.3.4 部分测试数据和输出结果

7.4 翻硬币（难度：★★★☆☆）

7.4.1 问题描述

7.4.2 算法分析

7.4.3 参考程序

7.4.4 部分测试数据和输出结果

7.5 又是C（n， m）（难度：★★☆☆☆）

7.5.1 问题描述

7.5.2 算法分析

7.5.3 参考程序

7.5.4 部分测试数据和输出结果

第8章 2008年中山大学内部选拔赛第二试试题分析

8.1 次小生成树（难度：★★★★★）

8.1.1 问题描述

8.1.2 算法分析

8.1.3 参考程序

8.1.4 部分测试数据和输出结果

8.2 分宝藏（难度：★★★☆☆）

8.2.1 问题描述

8.2.2 算法分析

8.2.3 参考程序

8.2.4 部分测试数据和输出结果

8.3 探照灯（难度：★★☆☆☆）

8.3.1 问题描述

8.3.2 算法分析

8.3.3 参考程序

8.3.4 部分测试数据和输出结果

8.4 数字识别系统（难度：★★★☆☆）

8.4.1 问题描述

8.4.2 算法分析

8.4.3 参考程序

8.4.4 部分测试数据和输出结果

8.5 开灯（难度：★★☆☆☆）

8.5.1 问题描述

8.5.2 算法分析

8.5.3 参考程序

8.5.4 部分测试数据和输出结果

第9章 2008年中山大学内部选拔赛第三试试题分析

9.1 最大对称子数列（难度：★★★★★）

9.1.1 问题描述

9.1.2 算法分析

9.1.3 参考程序

9.1.4 部分测试数据和输出结果

9.2 寻宝（难度：★★★★☆）

9.2.1 问题描述

9.2.2 算法分析

9.2.3 参考程序

9.2.4 部分测试数据和输出结果

9.3 大明王朝（难度：★★☆☆☆）

9.3.1 问题描述

9.3.2 算法分析

9.3.3 参考程序

9.3.4 部分测试数据和输出结果

9.4 重建长城（难度：★★★☆☆）

9.4.1 问题描述

9.4.2 算法分析

9.4.3 参考程序

9.4.4 部分测试数据和输出结果

9.5 斯诺克（难度：★★★★★）

9.5.1 问题描述

9.5.2 算法分析

9.5.3 参考程序

9.5.4 部分测试数据和输出结果

第10章 2008年中山大学内部选拔赛第四试试题分析

10.1 度限制生成树（难度：★★★☆☆）

10.1.1 问题描述

10.1.2 算法分析

10.1.3 参考程序

10.1.4 部分测试数据和输出结果

10.2 重新分工（难度：★★★★☆）

10.2.1 问题描述

10.2.2 算法分析

10.2.3 参考程序

10.2.4 部分测试数据和输出结果

10.3 桩（难度：★★★★☆）

10.3.1 问题描述

10.3.2 算法分析

10.3.3 参考程序

10.3.4 部分测试数据和输出结果

10.4 旅行方案（难度：★★★★☆）

10.4.1 问题描述

10.4.2 算法分析

10.4.3 参考程序

10.4.4 部分测试数据和输出结果

10.5 最大最短距离（难度：★★★☆☆）

10.5.1 问题描述

10.5.2 算法分析

10.5.3 参考程序

10.5.4 部分测试数据和输出结果

第11章 2008年中山大学内部选拔赛第五试试题分析

11.1 菱形（难度：★★★☆☆）

11.1.1 问题描述

11.1.2 算法分析

11.1.3 参考程序

11.1.4 部分测试数据和输出结果

11.2 傻瓜式函数（难度：★★☆☆☆）

11.2.1 问题描述

11.2.2 算法分析

11.2.3 参考程序

11.2.4 部分测试数据和输出结果

11.3 最大公约数（难度：★★★☆☆）

11.3.1 问题描述

11.3.2 算法分析

11.3.3 参考程序

11.3.4 部分测试数据和输出结果

11.4 数列（难度：★★☆☆☆）

11.4.1 问题描述

11.4.2 算法分析

11.4.3 参考程序

11.4.4 部分测试数据和输出结果

11.5 间距（难度：★★★☆☆）

11.5.1 问题描述

11.5.2 算法分析

11.5.3 参考程序

11.5.4 部分测试数据和输出结果

第12章 2008年中山大学内部选拔赛第六试试题分析

12.1 猜答案（难度：★★★★☆）

12.1.1 问题描述

12.1.2 算法分析

12.1.3 参考程序

12.1.4 部分测试数据和输出结果

12.2 A+B问题（难度：★★★☆☆）

12.2.1 问题描述

12.2.2 算法分析

12.2.3 参考程序

12.2.4 部分测试数据和输出结果

12.3 时间流逝（难度：★★★☆☆）

12.3.1 问题描述

12.3.2 算法分析

12.3.3 参考程序

12.3.4 部分测试数据和输出结果

12.4 裸题（难度：★★☆☆☆）

12.4.1 问题描述

12.4.2 算法分析

12.4.3 参考程序

12.4.4 部分测试数据和输出结果

12.5 谜题（难度：★★★☆☆）

12.5.1 问题描述

12.5.2 算法分析

12.5.3 参考程序

12.5.4 部分测试数据和输出结果

附录1 中山大学集训队选拔流程图

附录2 中国内地高校参加ACM/ICPC全球总决赛的成绩（1997～2012）

附录3 中山大学队2008～2011年在亚洲区成绩

附录4 中山大学队1999～2012年在全球总决赛成绩

作者简介

参考文献

《国际大学生程序设计竞赛中山大学内部选拔真题解（1）》收录了2007—2008年中山大学ICPC（国际大学生程序设计竞赛）集训队内部选拔赛的全部试题、完整的测试数据和答案。为了方便读者学习，《国际大学生程序设计竞赛中山大学内部选拔真题解（一）》对每道题目做了详尽的题目分析并详细地讲解其算法实现的原理，同时提供了完善的标准程序及其程序分析供读者参考。我们在书中还提供了基本测试数据以方便读者测试自行完成上述题目的结果。随书还附带光盘，存放所有例题中完整的测试数据，以便于对自己有更高、更严格要求的同学能利用规模更大的测试数据进行训练和学习用。本书对试题难易程度进行了星级标注，并在本书知识点分类及说明中列出了本书试题所涉及的算法分类和所用的数据结构类型，以便读者有选择性地学习。
《国际大学生程序设计竞赛中山大学内部选拔真题解（1）》所提供的题目都是原创题，题目构思新颖，内容有趣。所涉及的算法知识面广，其涉及的算法知识基本上覆盖大学计算机类本科专业所学到的基本算法。
《国际大学生程序设计竞赛中山大学内部选拔真题解（1）》可以作为高等院校大学生和研究生准备参加各级国际大学生程序设计竞赛活动的辅导教材和训练题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考书，同时也可以作为中学省级及以上信息学奥林匹克优秀选手准备高层次程序设计竞赛的参考用书。