本书从ACM-ICPC程序设计竞赛等各种程序设计竞赛的试题进行了分析和整理，并精选出典型试题进行分类解析，既可用于高校算法、程序设计课程的实验和教学，也可以用于竞赛选手的系统训练。
适用于ACM-ICPC、IOI等各类
程序设计竞赛的训练
精析典型赛题，并给出有详细注释的参考程序
系统、高效地训练思维能力和编程能力
本书是“大学程序设计课程与竞赛训练教材”系列著作中的第2部。我们编著这一系列著作的指导思想如下。
（1）程序设计竞赛是“通过编程解决问题”的竞赛。国际大学生程序设计竞赛（Inter-national Collegiate Programming Contest，ICPC）和中学生国际信息学奥赛（International Olympiad in Informatics，IOI）在20世纪80年代中后期走向成熟，30多年来，累积了海量的试题。这些来自全球各地、凝聚了无数命题者的心血和智慧的试题，不仅可以用于程序设计竞赛选手的训练，而且可以用于教学，以系统、全面地提高学生编程解决问题的能力。
（2）我们认为，评价一个人的专业能力，要看这个人的两个方面：1）知识体系，即他能用哪些知识去解决问题，或者说，他所真正掌握并能应用的知识，而不仅仅是他学过的知识；2）思维方式，即他在面对问题（特别是不太标准化的问题）的时候，解决问题的策略是什么？对于程序设计竞赛选手所要求的知识体系，可以概括为1984年图灵奖得主Niklaus Wirth提出的著名公式“算法+数据结构=程序”，这也是计算机学科知识体系的核心部分，因此本系列的前两部著作分别是《数据结构编程实验》和《算法设计编程实验》。对于需要采用某些策略进行求解的程序设计试题，比如，不采用常用的数据结构或者需要优化解题的算法，我们进行分析整理，编写了本系列的第3部著作《程序设计解题策略》。
（3）从本质上说，程序设计是技术，所以，首先牢记学习编程要不断“Practice, Practice,
Practice”!本系列选用程序设计竞赛的大量试题，以案例教学的方式进行教学实验并安排学生进行解题训练。其次，“Practice in a systematic way”。本系列的编写基于传统的教学大纲，以系统、全面地提高学生编程解决问题的能力为目标，以程序设计竞赛的试题及详细的解析、带注释的程序作为实验，在每一章的结束部分给出相关题库及解题提示，并对大部分试题给出官方的测试数据。
2013年，我们在机械工业出版社出版了《算法设计编程实验：大学程序设计课程与竞赛训练教材》。2018年，我们在CRC Press出版了该书的英文版《Algorithm Design Practice: for Collegiate Programming Contest and Education》。此外，我们还在中国台湾地区出版了繁体中文版。
本书的第1版是在复旦大学程序设计集训队长期活动的基础上编写而成的，共分8章，主要内容如下：
第1章“求解Ad Hoc类问题的编程实验”：介绍了机理分析法和统计分析法，引导读者在没有经典和模式化算法可对应的情况下，学会自创简单的算法。
第2章“模拟法的编程实验”：引导读者按照题意设计数学模型的各种参数，观察变更这些参数所引起的过程状态的变化，在此基础上展开算法设计。
第3章“数论的编程实验”和第4章“组合分析的编程实验”：这两章凸显了数论和组合分析知识在算法中的应用。其中，第3章围绕初等数论中的素数运算、求解不定方程和同余方程、应用积性函数等问题展开实验。第4章介绍在编程求解组合类问题时如何计算具有某种特性的对象个数，如何将它们完全列举出来，如何使用抽屉原理解决存在性问题，如何使用容斥原理计算多个集合并的元素数，如何使用Pólya定理对一个问题的各种不同的组合状态计数。
第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”：在求解具备最优子结构特征的问题时，这两种方法是最常用、最经典的思想方法，但适用场合不同，既有相同点又有区别之处。
第7章“高级数据结构的编程实验”：选择在一般数据结构教材中没有出现但很有用的一些知识，例如后缀数组、线段树、欧拉图、哈密顿图、最大独立集、割点、桥和双连通分支等内容展开编程实验。
第8章“计算几何的编程实验”：计算几何学是算法体系中一个重要的组成部分，也是先前算法教材中最薄弱的环节。该章开展点线面运算、扫描线算法、计算半平面交、凸包计算和旋转卡壳算法等实验。
近来年，我们使用本书第1版的中、英文版在全球高校进行教学，根据读者和学生的反馈，我们对本书第1版的内容进行了修订，形成了第2版。我们除了修正第1版中的小错误，以及改进一些表述之外，还做了如下较大改进：
对于第3章“数论的编程实验”和第4章“组合分析的编程实验”的内容和结构，基于数论、组合数学的知识体系，进行全面的加强和改进。其中，第3章从素数运算、求解不定方程和同余方程、特殊的同余式、积性函数的应用、高斯素数5个方面展开实验；而第4章从排列的生成、排列和组合的计数、容斥原理与鸽笼原理、Pólya计数公式、生成函数与递推关系、快速傅里叶变换（FFT）6个方面展开实验。对于数论、组合分析所涉及的知识点，都采用程序设计竞赛的试题作为实验范例，也就是说，基于数论、组合分析的知识体系，实验范例“鱼鳞状”分布在各个知识点中。同时，将数学证明能力和编程解决问题能力的训练相结合，这也是数学类试题的特征。
对于第5章“贪心法的编程实验”和第6章“动态规划方法的编程实验”，则增加了经典问题的实验。在第5章中，增加了背包问题、任务调度、区间调度等经典贪心问题的实验；在第6章中，则以“背包九讲”为基础，增加0-1背包问题的实验。这样改进的目的，是使读者能够更好地体验贪心和动态规划的方法。
本书可以用于大学的算法及相关数学课程的教学和实验，也可以用于程序设计竞赛选手的系统训练。对于本书，我们的使用建议是：书中每章的实验范例可以用于算法和数学课程的教学、实验和上机作业，以及程序设计竞赛选手掌握相关知识点的入门训练；而每章最后给出的相关题库中的试题则可以作为程序设计竞赛选手的专项训练试题，以及学生进一步提高编程能力的练习题。
我们对浩如烟海的ACM-ICPC预赛和总决赛、各种大学生程序设计竞赛、在线程序设计竞赛及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出314道试题作为本书的试题。其中157道试题作为实验范例试题，每道试题不仅有详尽的解析，还给出标有详细注释的参考程序；另外的157道试题为题库试题，所有试题都有清晰的提示。
本书提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序，有需要者可登录华章网站（http://www.hzbook.com）下载。
感谢Stony Brook University的Steven Skiena教授和Rezaul Chowdhury教授，Texas State University的C. Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授，German University of Technology in Oman的Rudolf Fleischer教授，North South University的Abul L. Haque教授和Shazzad Hosain教授，International Islamic University Malaysia的Normaziah Abdul Aziz教授，以及香港理工大学的曹建农教授，他们为本书英文版书稿的试用和改进提供了以英语为母语或官方语言的平台。感谢Georgia Institute of Technology的Jiaqi Chen同学审阅英文版书稿的部分章节。
感谢巴黎第十一大学博士生张一博同学、香港中文大学博士生王禹同学和复旦大学已故教授朱洪先生，他们对于第2版的编写提出了建设性的意见。
感谢组织程序设计训练营集训并邀请我使用本书书稿讲学的香港理工大学曹建农教授，台湾“东华大学”彭胜龙教授，西北工业大学姜学峰教授和刘君瑞教授，宁夏理工学院副校长俞经善教授，中国矿业大学毕方明教授，以及中国矿业大学徐海学院刘昆教授等。
感谢指出书稿中错误的西安电子科技大学朱微、张恩溶和中国矿业大学徐海学院贺小梅等同学。
特别感谢和我一起创建ACM-ICPC亚洲训练联盟的国内同仁，他们不仅为本书书稿，也为我的系列著作及其课程建设提供了一个实践的平台。这些年，我们并肩作战，风雨同舟，如莎士比亚《亨利五世》的台词：“今日谁与我共同浴血，他就是我的兄弟！”
由于时间和水平所限，书中肯定夹杂了一些缺点和错误，表述不当和笔误也在所难免，热忱欢迎学术界同仁和读者赐正。如果你在阅读中发现了问题，请通过电子邮件告诉我们，以便我们在课程建设和中、英文版再版时改进。我们的联系方式如下：
通信地址：上海市邯郸路220号复旦大学计算机科学技术学院 吴永辉（邮编：200433）
电子邮件：yhwu@fudan.edu.cn
吴永辉 王建德
2019年10月30日于上海
注：本书试题的在线测试地址如下：
在线评测系统 简称 网址
北京大学在线评测系统 POJ http://poj.org/
浙江大学在线评测系统 ZOJ http://acm.zju.edu.cn/onlinejudge/
http://zoj.pintia.cn/home
UVA在线评测系统 UVA http://uva.onlinejudge.org/
http://livearchive.onlinejudge.org/
Ural在线评测系统 Ural http://acm.timus.ru/
HDOJ在线评测系统 HDOJ http://acm.hdu.edu.cn/
计算机\程序设计
本书基于作者20余年来总结的编程知识体系和行之有效的编程能力训练方法，以ACM-ICPC、IOI等各类大型程序设计竞赛的经典试题为素材编写而成，通过启发式、案例化的教学，系统、全面地培养读者编程解决问题的能力。本书不仅可以作为ACM-ICPC、IOI等程序设计竞赛的训练教程，亦可作为高校程序设计相关课程的实践教材以及对编程感兴趣的读者的自学读物。
本书特色
从ACM-ICPC、IOI等各类国内外程序设计竞赛中精选300余道典型赛题，并归为Ad Hoc、模拟、数论、组合分析、贪心、动态规划、高级数据结构、计算几何八类，使读者掌握各类经典问题的思考方法和解题策略。
将150余道试题作为范例试题，每道试题不仅有详尽的试题解析，还给出有详细注释的参考程序；其他试题为题库试题，每道试题给出清晰的提示，使读者进一步训练解题策略。
与上一版相比，数论、组合分析两章通过程序设计竞赛试题及其解析对相关知识点进行了全覆盖，贪心、动态规划两章则加强了对经典问题的解析。
本书给出所有试题的英文原版以及大部分试题的官方测试数据和解答程序，读者可登录华章网站下载。
前 言
第1章 求解Ad Hoc类问题的编程实验 1
1.1 机理分析法的实验范例 1
1.2 统计分析法的实验范例 5
1.3 相关题库 9
第2章 模拟法的编程实验 31
2.1 直叙式模拟的实验范例 31
2.2 筛选法模拟的实验范例 46
2.3 构造法模拟的实验范例 56
2.4 相关题库 60
第3章 数论的编程实验 72
3.1 素数运算的实验范例 72
3.1.1 使用筛法生成素数 72
3.1.2 测试大素数 79
3.2 求解不定方程和同余的实验范例 82
3.2.1 计算最大公约数和不定方程 82
3.2.2 计算同余方程和同余方程组 89
3.2.3 计算多项式同余方程 99
3.3 特殊的同余式的实验范例 102
3.3.1 威尔逊定理和费马小定理 102
3.3.2 伪素数 105
3.3.3 欧拉定理 112
3.4 积性函数的实验范例 116
3.4.1 欧拉φ函数φ(n) 116
3.4.2 莫比乌斯函数μ(n) 121
3.4.3 完全数和梅森素数 124
3.5 高斯素数的实验范例 129
3.6 相关题库 135
第4章 组合分析的编程实验 152
4.1 生成排列的实验范例 152
4.1.1 按字典序思想生成下一个排列 152
4.1.2 按字典序思想生成所有排列 154
4.2 排列组合计数的实验范例 156
4.2.1 一般的排列组合计数公式 156
4.2.2 两种特殊的排列组合计数公式 167
4.2.3 多重集的排列数和组合数 174
4.3 鸽笼原理与容斥原理的实验范例 178
4.3.1 利用鸽笼原理求解存在性问题 178
4.3.2 容斥原理应用实验 180
4.3.3 Ramsey定理的应用 188
4.4 Pólya计数公式的实验范例 190
4.5 生成函数与递推关系的实验范例 201
4.5.1 幂级数型生成函数 201
4.5.2 指数型生成函数 204
4.5.3 递推关系 207
4.6 快速傅里叶变换的实验范例 211
4.7 相关题库 216
第5章 贪心法的编程实验 229
5.1 体验贪心法内涵的实验范例 229
5.1.1 贪心法的经典问题 229
5.1.2 体验贪心法内涵 236
5.2 利用数据有序化进行贪心选择的实验范例 241
5.3 在综合性的P类问题中使用贪心法的实验范例 249
5.4 相关题库 255
第6章 动态规划方法的编程实验 265
6.1 线性DP的实验范例 266
6.1.1 初步体验线性DP问题 266
6.1.2 子集和问题 270
6.1.3 最长公共子序列问题 271
6.1.4 最长递增子序列问题 273
6.2 0-1背包问题 280
6.2.1 基本的0-1背包问题 280
6.2.2 完全背包 281
6.2.3 多重背包 285
6.2.4 混合背包 287
6.2.5 二维背包 292
6.2.6 分组背包 294
6.2.7 有依赖的背包 298
6.3 树形DP的实验范例 300
6.4 状态压缩DP的实验范例 305
6.5 单调优化1D/1D DP的实验范例 309
6.5.1 经典模型1：利用决策代价函数w的单调性优化 310
6.5.2 经典模型2：利用决策区间下界的单调性优化 313
6.5.3 经典模型3：利用最优决策点的凸性优化 318
6.6 相关题库 322
第7章 高级数据结构的编程实验 353
7.1 后缀数组的实验范例 353
7.1.1 使用倍增算法计算名次数组和后缀数组 353
7.1.2 计算最长公共前缀 356
7.1.3 后缀数组的应用 357
7.2 线段树的实验范例 370
7.2.1 线段树的基本概念和基本操作 370
7.2.2 线段树单点更新的维护 372
7.2.3 线段树子区间更新的维护 375
7.3 处理特殊图的实验范例 387
7.3.1 计算欧拉图 387
7.3.2 计算哈密顿图 393
7.3.3 计算最大独立集 402
7.3.4 计算割点、桥和双连通分支 406
7.4 相关题库 414
第8章 计算几何的编程实验 433
8.1 点线面运算的实验范例 433
8.1.1 计算点积和叉积 433
8.1.2 计算线段交 440
8.1.3 利用欧拉公式计算多面体 449
8.2 利用扫描线算法计算矩形的并的面积的实验范例 453
8.2.1 沿垂直方向计算矩形的并面积 453
8.2.2 沿水平方向计算矩形的并面积 457
8.3 计算半平面交的实验范例 460
8.3.1 计算半平面交的联机算法 461
8.3.2 利用极角计算半平面交的算法 466
8.4 计算凸包和旋转卡壳的实验范例 474
8.4.1 计算凸包 474
8.4.2 旋转卡壳实验 479
8.5 相关题库 482
