书名：算法竞赛实战笔记  
定价：78.0  
ISBN：9787121470127  
作者：无  
版次：*1版  
出版时间：2024-01  

内容提要：  
近年来，随着互联网和人工智能的广泛应用，算法作为其关键技术的内核，备受学校和企业的重视，算法竞赛更成为算法领域的一颗明珠。本书依托编著者多年算法竞赛的教学积累，全方位介绍了竞赛中常用的算法及近年来算法竞赛领域*新的研究成果，基于算法竞赛中广泛使用的在线评测网站——洛谷，着重介绍线性数据结构，基础算法，搜索算法，动态规划等方面的知识。本书适合对算法竞赛感兴趣的青少年阅读，也可作为相关领域教师、计算机专业学生的参考用书。  



作者简介：  
作者梁博：2019年到今，负责北大附中初中信息学奥赛教学工作。2022年学生成绩：入选省队：陈凯丰，谢梓涵，梁嘉文。北京20个省队名额中占3人。（根据往年情况，进入省队基本都可以保送清华或者北大）2021年学生成绩：吕彦哲银牌。陈凯丰（初二）作为夏令营选手获得银牌，签约北大，成为历史上签约北大*小的选手。2020年学生成绩：学生中初中组（普及组）参赛人数60人，一等奖获奖20人，二等奖25人，北京市7个满分同学中占3人。省一等奖比例30%远超全市平局值，总获奖率68%初二即有两名同学获得高中组（提高组）一等奖。2014-2021在小米负责签名与编译系统研发，科研成果转化为32项专利，如：CN201510549837.6一种应用软件预装次数的控制方法及装置CN201510547599.5应用版本信息的获取方法、设备和系统CN201510857770.2终端系统升级方法及装置CN201610694577.6数字签名方法及装置其余28项专利不列出，可以在相关网站检索到.2009-2021 浙江大学竺可桢学院计算机科学与技术专业  

媒体评论：  
1.**名信息学奥赛教练执笔，多校金*教练经验结晶2.来自竞赛强校训练题库的例题、习题，在线公开可评测3.近百幅插图，带你探究算法每一个细节4.基于C++14和NOI Linux2.0版本编写，紧跟*新竞赛环境5.配套视频课程，赠送*值优惠券  

目录：  
第 0 章 一些不那么常识的常识 ············································································.1  
0.1 本地编程环境的配置··············································································.1  
0.1.1 在 Windows 系统上安装使用 Dev C++···············································.1  
0.1.2 在 MacOS 系统上安装 Xcode ··························································.4  
0.2 在线评测系统—洛谷···········································································.7  
0.2.1 注册洛谷 ···················································································.8  
0.2.2 提交题目 ···················································································.9  
0.2.3 团队管理 ···················································································11  
第 1 章 线性数据结构 ························································································15  
1.1 数据结构·····························································································15  
1.1.1 数据结构的定义 ··········································································15  
1.1.2 数据结构的运算 ··········································································17  
1.1.3 线性数据结构 ·············································································17  
1.2 栈······································································································18  
1.2.1 栈的定义 ···················································································18  
1.2.2 栈的作用 ···················································································20  
1.2.3 栈的固定数组实现 ·······································································21  
1.2.4 STL 中的栈 ················································································24  
1.2.5 括号匹配问题 ·············································································26  
1.2.6 前缀、中缀、后缀表达式 ······························································30  
1.2.7 后缀表达式的计算 ·······································································32  
1.2.8 中缀表达式转换为后缀表达式 ························································36  
1.2.9 中缀表达式的计算 ·······································································41  
1.3 队列···································································································43  
1.3.1 队列的定义 ················································································44  
1.3.2 队列的作用 ················································································46  
1.3.3 队列的固定数组实现 ····································································46  
1.3.4 STL 中的队列 ·············································································47  
1.3.5 基数排序（Radix Sorting）·····························································50  
1.3.6 结构体的构造函数 ·······································································56  
1.3.7 队列的应用 ················································································59  
1.4 前缀和·······························································································.66  
1.4.1 前缀和的引入 ············································································.66  
1.4.2 一维数组前缀和 ·········································································.66  
1.5 动态数组····························································································.75  
1.5.1 动态数组 vector ··········································································.75  
1.5.2 STL 中的动态数组 ······································································.75  
1.5.3 vector 的缺点 ·············································································.76  
1.5.4 vector 与迭代器 iterator·································································.76  
1.5.5 vector 与 C++11 ··········································································.78  
1.5.6 vector 的实现原理 ·······································································.80  
1.6 树·····································································································.82  
1.6.1 树的相关概念 ············································································.82  
1.6.2 树的性质 ··················································································.84  
1.6.3 特殊的树—二叉树 ···································································.84  
1.6.4 完全二叉树的性质 ······································································.85  
1.6.5 树的存储方式 ············································································.86  
1.6.6 树的遍历 ··················································································.89  
1.6.7 知二求一 ··················································································101  
1.6.8 树的宽度优先遍历 ······································································105  
1.7 本章习题····························································································105  
第 2 章 基础算法 ·····························································································106  
2.1 贪心算法····························································································106  
2.1.1 贪心算法的概念 ·········································································106  
2.1.2 基础贪心问题举例 ······································································107  
2.1.3 线段覆盖问题 ············································································111  
2.2 高精度计算·························································································113  
2.2.1 C++语言中的数据类型·································································113  
2.2.2 高精度加法 ···············································································115  
2.2.3 高精度减法 ···············································································118  
2.2.4 高精度乘法 ···············································································121  
2.2.5 高精度除法取余数 ······································································126  
2.3 归并排序····························································································129  
2.3.1 归并 ························································································130  
2.3.2 归并排序的时间复杂度分析 ··························································134  
2.3.3 归并排序的应用 ·········································································135  
2.4 快速排序··························································································.143  
2.4.1 快速排序的思想················································································.143  
2.4.2 快速排序的时间复杂度分析 ························································.146  
2.5 STL ································································································.151  
2.5.1 algorithm 头文件中的函数 ···························································.152  
2.5.2 容器 ······················································································.156  
2.6 本章习题··························································································.159  
第 3 章 搜索算法 ···························································································.160  
3.1 深度优先搜索····················································································.160  
3.1.1 迷宫寻路与烤鸡问题 ·································································.160  
3.1.2 全排列问题与回溯 ····································································.166  
3.1.3 洪水填充（Flood Fill）算法·························································.168  
3.1.4 八皇后问题与剪枝 ····································································.171  
3.1.5 数独问题 ················································································.174  
3.1.6 剪枝 ······················································································.177  
3.2 宽度优先搜索····················································································.181  
3.2.1 找眼镜 ···················································································.181  
3.2.2 马的遍历 ················································································.182  
3.2.3 01 迷宫···················································································.185  
3.2.4 八数码问题 ·············································································.188  
3.3 本章习题··························································································.190  
第 4 章 动态规划 ···························································································.191  
4.1 动态规划入门····················································································.191  
4.1.1 斐波那契数列 ··········································································.191  
4.1.2 数字三角形 ·············································································.193  
4.1.3 递推+填表···············································································.195  
4.2 动态规划解题步骤··············································································.199  
4.2.1 分解子问题 ·············································································.199  
4.2.2 确定状态 ················································································.200  
4.2.3 状态转移 ················································································.200  
4.2.4 动态规划能解决的问题的特点 ·····················································.201  
4.3 线性动态规划····················································································.201  
4.3.1 *长上升子序列问题（LIS）·······················································.201  
4.3.2 *长公共子序列问题（LCS）······················································.209  
4.4 背包类动态规划·················································································.213  
4.4.1 01 背包问题···············································································213  
4.4.2 多重背包问题 ············································································225  
4.4.3 完全背包问题 ············································································228  
4.4.4 分组背包问题 ············································································231  
4.4.5 二维费用背包问题 ······································································241  
4.5 区间动态规划与多维动态规划·············································································243  
4.5.1 区间动态规划 ············································································243  
4.5.2 多维动态规划 ············································································248  
4.6 本章习题····························································································256