本书系统地介绍了蓝桥杯程序竞赛中真题的常用算法及应用。全书共14章，包括竞赛预备知识、基础题、时间、字符串、规律题、二分法、优先队列与堆栈、基本递归、图论、动态规划、区间运算算法、数论、计算几何、游戏题等。书中列举了大量的蓝桥杯竞赛真题，进行了详尽的分析，极具实用性。本书可以作为普通高等学校大学生参加程序竞赛和学习算法的参考书，也可作为高校的创新实践课教材，同时对广大计算机算法爱好者深入研究算法或进入计算机相关公司工作有一定的指导作用。
(1)教材中讲过的知识点尽量略讲，教材中未讲的、竞赛中经常用到的重点讲；(2)蓝桥杯真题解析中分析透彻，采用图表技术，代码注释详尽；(3)某些题目用了多种方法解析，使读者明晓它们的优劣；(4)强调实践，让读者在具体题目中体会算法的妙用。
前言
创作背景
工业和信息化部人才交流中心主办的蓝桥杯软件和信息技术专业人才大赛自2010年举办以来，至今已成功举办15届，参赛院校达到1900多所，大赛连续多年入选高等教育学会竞赛排行榜单赛事，逐渐成为最有影响的程序竞赛之一。本书是作者为蓝桥杯竞赛尽的一份微薄之力。以下三点是作者的创作动机: ①作为蓝桥杯指导教师12年，见证了蓝桥杯的成长，很想把自己的程序竞赛知识奉献给广大读者；②网上也有一些关于蓝桥杯程序竞赛的真题解析，但大多写得很简略，一般的读者难以读懂；③程序竞赛书籍不好编写，许多人望而却步，这可能是这方面书少的因素，但这也更是促使我们完成本书的重要原因。
历经四年，这本竞赛书终于完成了！每道题我们都亲历而为，因为我们深知: 如果自己不把题目做出来，就很难给读者真正讲清楚。正如古语云: “宝剑锋从磨砺出，梅花香自苦寒来。”
本书内容
本书共14章，具体内容如下所示。
第1章竞赛预备知识。介绍了C语言常用函数及STL(standard template library)标准模板库常用算法及容器的应用方法。
第2章基础题。介绍了常用的穷举法、中等数学、取余、最大公约数、排序等内容。
第3章时间。主要强调了时间基准点是完成此类题目的关键所在。
第4章字符串。字符串编程是程序的基本功。介绍了竞赛中常用的搜索、拆分、与其他算法结合综合应用等内容。
第5章规律题。可通过常规方法及小量的输入数据获得小量的输出数据。通过观察输入、输出数据的变化特点，总结出经验公式，利用经验公式完成题目内容。
第6章二分法。介绍了STL二分法函数的应用及常规二分算法的分析与应用。
第7章优先队列与堆栈。介绍了两种容器在实际中的应用。优先队列在“最”值中应用广，堆栈在“括号”表达式中应用较多。第8章基本递归。介绍了为什么有递归，递归的重要性，并通过实例加以解析。
第9章图论。介绍了深度优先搜索、宽度优先搜索、并查集、单源最短路径、最小生成树在实际中的应用方法。
第10章动态规划。介绍了线性动态规划、区间动态规划、树形动态规划、数位动态规划的特点及应用实例。
第11章区间运算算法。介绍了树状数组、线段树、ST系数表的特点及应用方法。
第12章数论。介绍了快速幂取模、矩阵快速幂、欧拉函数、欧拉定理、扩展欧几里得、中国剩余定理等知识点及应用方法。
第13章计算几何。介绍了用到的点积、叉积等基本函数。讲解了求任意多边形面积、皮克定理、辛普森积分知识点及应用方法。
第14章游戏题。介绍了巴什博弈、尼姆博弈等知识点及实际应用。
本书特点
1. 本书实例丰富，涵盖了蓝桥杯第4～15届的历届试题，包含A、B、C组省赛试题及总决赛试题。有简单题，也有中等难度及难题，适合各类读者学习。
2. 实例中有些题目用了多种方法解析，读者可以加以对比，从中体会算法的不同及奥妙之处。
3. 实例讲解详尽，有些用到了大量的图表，分析了示例数据在算法应用中的详细变化过程，读者清楚了该过程，也就理解了算法实现的核心。
4. 本书从程序竞赛角度出发，讲解了与普通教材知识点的不同。例如竞赛中尽量不用C语言指针，一般不用邻接矩阵求解图论问题等。
附加说明
1. 本书中所选蓝桥杯历届真题，都在蓝桥云课官网、Dotcpp编程（C语言网）提交成功，在此深表感谢。
2. 本书中有两种示例: 一种是“【例XXX】”，表示是蓝桥杯历届真题；一种是“【eXXX】”，表示是自编题目或者选自其他Online Judge系统题目。如洛谷网站、杭州电子科技大学ACM网站、力扣网站等。
3. 选自Online Judge网站的题目由“网站名称+题目编号”组成，方便读者查询。
本书第5～14章由金百东编写，第1～4章由崔晓松编写。因本书程序较多，故全书变量均用正体。本书在编写过程中得到了蓝桥杯软件和信息技术专业人才大赛组委会李艳萍、郑未、单宝军等多位、学者给予的专业建议和帮助指导，提供了蓝桥杯大赛的历届真题，同时也得到了国信蓝桥教育科技股份有限公司的大力支持，在此一并表示感谢。
由于作者水平有限，书中难免有疏漏之处，恳请广大读者批评指正。
源程序
作者
2025年4月
金百东：东北师范大学，从事程序设计与教学30年，硕士学历，现任辽宁师范大学副教授。担任历届蓝桥杯程序设计竞赛指导教师，多年辽宁省大学生ACM程序竞赛指导教师。开发了本科生毕业论文选题管理系统、本科生创新创业项目管理系统、课程计算机管理系统，并已获得应用。在省级以上杂志发表论文18篇，已编写出版《C++STL基础及应用》、《Javaweb编程技术实用教程》、《Java设计模式及应用案例》、《Android简明程序设计》等多部教材。
目录
第1章竞赛预备知识1
1.1C语言常用函数1
1.1.1字符串数值转换函数1
1.1.2字符串函数1
1.2STL标准模板库3
1.2.1STL算法函数3
1.2.2STL容器11
第2章基础题21
2.1穷举法真题21
【例21】（第7届）抽签21
【例22】（第4届）买不到的数目22
【例23】（第7届）四平方和23
【例24】（第5届）拼接平方数23
【例25】（第4届）带分数25
2.2中等数学真题26
【例26】（第13届）因数平方和26
【例27】（第12届）和与乘积28
【例28】（第12届）杨辉三角形31
2.3取余真题35
【例29】（第8届）K倍区间35
【例210】（第13届）取模36
【例211】（第13届）近似GCD37
2.4最大公约数40
【例212】（第11届）循环小数40
【例213】（第10届）等差数列41
2.5排序真题42
【例214】（第13届）重新排序42
【例215】（第14届）平均45
2.6其他基本类型真题47【例216】（第6届）奇怪的数列47
【例217】（第13届）X进制减法49
【例218】（第13届）数的拆分51
【例219】（第14届）公因数匹配55
【例220】（第14届）棋盘58
【例221】（第13届）积木画59
【例222】（第8届）小计算器61
第3章时间65
【例31】（第9届）航班时间65
【例32】（第11届）回文日期67
【例33】（第8届）日期问题69
第4章字符串71
【例41】（第10届）最长子序列71
【例42】（第6届）密文搜索72
【例43】（第5届）排列序数73
【例44】（第9届）等腰三角形74
【例45】（第11届）重复字符串76
【例46】（第11届）字符串编码77
【例47】（第13届）内存空间79
【例48】（第14届）子串简写82
第5章规律题85
【例51】（第9届）约瑟夫环85
【例52】（第5届）生物芯片87
【例53】（第10届）数正方形88
【例54】（第14届）平方差90
【例55】（第10届）后缀表达式91
第6章二分法95
【例61】（第9届）递增三元组95
【例62】（第14届）买二赠一96
【例63】（第8届二分法）分巧克力98
【例64】（第13届）第K小的和100
【例65】（第13届国赛）卡牌101
【例66】（第11届）整数拼接103
【例67】（第13届）统计子矩阵105
第7章优先队列与堆栈109
【例71】(第15届)爬山109
【例72】（第13届）砍竹子111
【例73】(第14届)最大开支114
【例74】(第14届)整数删除117
【例75】（第13届）扫描游戏120
【例76】（第8届）正则问题124
第8章基本递归127
8.1递归引入127
8.2基本例题130
8.3递归真题135
【例81】（第13届）最大数字135
【例82】（第4届国赛）横向打印二叉树137
第9章图论141
9.1深度优先搜索141
9.2真题分析146
【例91】（第4届）剪格子146
【例92】（第7届）路径之谜148
【例93】（第5届求割点）危险系数150
【例94】（第9届）版本分支152
【例95】（第13届）扫雷155
【例96】（第8届）发现环160
9.3宽度优先搜索162
9.4真题分析165
【例97】（第6届BFS）穿越雷区165
【例98】（第9届）变暖167
【例99】（第10届）大胖子走迷宫169
9.5并查集172
9.6真题分析176
【例910】（第8届）合根植物176
【例911】（第10届）修改数组178
【例912】（第13届）推导部分和180
【例913】（第11届）网络分析183
9.7单源最短路径186
9.7.1Dijkstra算法186
9.7.2SPFA算法188
9.8真题分析191
【例914】（第13届）出差191
【例915】（第11届）限高杆193
9.9最小生成树与最近公共祖先197
9.10真题分析203
【例916】（第14届）网络稳定性203
第10章动态规划208
10.1线性动态规划208
10.2真题分析208
【例101】（第7届）密码脱落208
【例102】（第12届）砝码称重210
【例103】（第8届）包子凑数211
【例104】（第13届）李白打酒加强版213
【例105】（第10届）包含216
【例106】（第14届）接龙数列218
10.3区间动态规划219
10.4真题分析224
【例107】（第9届）搭积木224
【例108】（第14届）更小的数227
【例109】（第14届）合并石子229
10.5树形动态规划232
10.6真题分析233
【例1010】（第12届）左孩子右兄弟233
【例1011】（第6届）生命之树234
10.7数位动态规划237
10.8真题分析243
【例1012】（第12届）二进制问题243
第11章区间运算算法246
11.1树状数组246
11.1.1引入246
11.1.2原理246
11.1.3示例分析249
11.2线段树254
11.2.1引入254
11.2.2基本操作255
11.2.3示例分析259
11.3ST表269
11.4真题分析271
【例111】（第13届）最大公约数271
【例112】（第5届）小朋友排队274
【例113】（第8届）油漆面积276
第12章数论281
12.1快速幂取模281
12.1.1递归快速幂281
12.1.2递推快速幂281
12.2矩阵快速幂282
12.3欧拉函数283
12.4欧拉定理283
12.5扩展欧几里得284
12.6中国剩余定理285
12.7典型例题286
【例121】（第14届）互素数的个数286
【例122】（第5届）斐波那契288
【例123】（第9届）倍数问题291
第13章计算几何294
13.1基础知识294
13.2进阶知识295
13.2.1求任意多边形面积295
13.2.2皮克定理296
13.2.3辛普森积分297
【例131】（第11届）平面切分298
【例132】（第4届）车轮轴迹300
第14章游戏题305
14.1巴什博弈305
14.2尼姆博弈306
14.3真题分析308
【例141】（第5届）矩阵翻硬币308
【例142】（第8届）填字母游戏309
参考文献312
书单推荐
