[正版][正版] 算法竞赛 罗勇军 清华大学出版社 全国青少年信息学奥林匹克NOI 中国国际大学生程序设计ICPC CC

                                                    店铺公告

为保障消费者合理购买需求及公平交易机会，避免因非生活消费目的的购买货囤积商品，抬价转售等违法行为发生，店铺有权对异常订单不发货且不进行赔付。异常订单：包括但不限于相同用户ID批量下单，同一用户（指不同用户ID，存在相同/临近/虚构收货地址，或相同联系号码，收件人，同账户付款人等情形的）批量下单（一次性大于5本），以及其他非消费目的的交易订单。 温馨提示：请务必当着快递员面开箱验货，如发现破损，请立即拍照拒收，如验货有问题请及时联系在线客服处理，（如开箱验货时发现破损，所产生运费由我司承担，一经签收即为货物完好，如果您未开箱验货，一切损失就需要由买家承担，所以请买家一定要仔细验货）， 关于退货运费：对于下单后且物流已发货货品在途的状态下，原则上均不接受退货申请，如顾客原因退货需要承担来回运费，如因产品质量问题（非破损问题）可在签收后，联系在线客服。

编辑推荐

一本算法竞赛大全，全面深入解析算法专题、数据结构、模板代码。10个专题，330个知识点，102个章节视频讲解。本书解析了算法竞赛考核的数据结构、算法；组织了每个知识点的理论解析和经典例题；给出了简洁精要的模板代码；通过明快清晰的文字、透彻的图解，实现了较好的易读性。

内容简介

本书是一本全面、深入解析与算法竞赛有关的数据结构、算法、代码的计算机教材。

本书包括十个专题： 基础数据结构、基本算法、搜索、高级数据结构、动态规划、数论和线性代数、组合数学、计算几何、字符串和图论。本书覆盖了绝大多数算法竞赛考点。

本书解析了算法竞赛考核的数据结构、算法； 组织了每个知识点的理论解析和经典例题； 给出了简洁、精要的模板代码； 通过明快清晰的文字、透彻的图解，实现了较好的易读性。

本书的读者对象是参加算法竞赛的中学生和大学生、准备面试IT企业算法题的求职者、需要提高算法能力的开发人员，以及对计算机算法有兴趣的广大科技工作者。

目录

源码下载

第1章基础数据结构

1.1链表

1.1.1动态链表

1.1.2静态链表

1.1.3STL list

1.2队列

1.2.1STL queue

1.2.2手写循环队列

1.2.3双端队列和单调队列

1.2.4优先队列

1.3栈

1.3.1STL stack

1.3.2手写栈

1.3.3单调栈

1.4二叉树和哈夫曼树

1.4.1二叉树的概念

1.4.2二叉树的遍历

1.4.3哈夫曼树和哈夫曼编码

1.5堆

1.5.1二叉堆的概念

1.5.2二叉堆的操作

1.5.3二叉堆的手写代码

1.5.4堆和priority_queue

小结

第2章基本算法

2.1算法复杂度

2.1.1算法的概念

2.1.2复杂度和大O记号

2.2尺取法

2.2.1尺取法的概念

2.2.2反向扫描

2.2.3同向扫描

2.3二分法

2.3.1二分法的理论背景

2.3.2整数二分

2.3.3实数二分

2.4三分法

2.4.1原理

2.4.2实数三分

2.4.3整数三分

2.5倍增法与ST算法

2.5.1倍增法

2.5.2ST算法

2.6前缀和与差分

2.6.1一维差分

2.6.2二维差分

2.6.3三维差分

2.7离散化

2.7.1离散化的概念

2.7.2离散化手工编码

2.7.3用STL函数实现离散化

2.7.4离散化的应用

2.8排序与排列

2.8.1排序函数

2.8.2排列

2.9分治法

2.9.1汉诺塔和快速幂

2.9.2归并排序

2.9.3快速排序

2.10贪心法与拟阵

2.10.1贪心法

2.10.2拟阵

小结

第3章搜索

3.1BFS和DFS基础

3.1.1搜索简介

3.1.2搜索算法的基本思路

3.1.3BFS的代码实现

3.1.4DFS的常见操作和代码框架

3.1.5BFS和DFS的对比

3.1.6连通性判断

3.2剪枝

3.2.1BFS判重

3.2.2剪枝的应用

3.3洪水填充

3.4BFS与最短路径

3.5双向广搜

3.5.1双向广搜的原理和复杂度分析

3.5.2双向广搜的两种实现

3.5.3双向广搜例题

3.6BFS与优先队列

3.7BFS与双端队列

3.8A*算法

3.8.1贪心最优搜索和Dijkstra算法

3.8.2A*算法的原理和复杂度

3.8.33种算法的对比

3.8.4h函数的设计

3.8.5A*算法例题

3.9IDDFS和IDA*

3.9.1IDDFS

3.9.2IDA*

小结

第4章高级数据结构

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.3线段树

4.3.1线段树的概念

4.3.2区间查询

4.3.3区间操作与LazyTag

4.3.4线段树的基础应用

4.3.5区间最值和区间历史最值

4.3.6区间合并

4.3.7扫描线

4.3.8二维线段树(树套树)

4.4可持久化线段树

4.4.1可持久化线段树的思想

4.4.2区间第k大/小问题

4.4.3其他经典问题

4.5分块与莫队算法

4.5.1分块

4.5.2基础莫队算法

4.5.3带修改的莫队算法

4.5.4树上莫队

4.6块状链表

4.7简单树上问题

4.7.1树的重心

4.7.2树的直径

4.8LCA

4.8.1倍增法求LCA

4.8.2Tarjan算法求LCA

4.8.3LCA的应用

4.9树上的分治

4.9.1静态点分治

4.9.2动态点分治

4.10树链剖分

4.10.1树链剖分的概念与LCA

4.10.2树链剖分的典型应用

4.11二叉查找树

4.12替罪羊树

4.12.1不平衡率

4.12.2替罪羊树的操作

4.12.3例题

4.13Treap树

4.13.1Treap树的性质

4.13.2基于旋转法的Treap树操作

4.14FHQ Treap树

4.14.1FHQ的基本操作

4.14.2FHQ Treap树的应用

4.15笛卡儿树

4.15.1笛卡儿树的概念

4.15.2用单调栈建笛卡儿树

4.15.3笛卡儿树和RMQ问题

4.16Splay树

4.16.1Splay旋转

4.16.2Splay树的平摊分析

4.16.3Splay树的常用操作和代码

4.17KD树

4.17.1从空间到二叉树的转换

4.17.2KD树的概念和基本操作

4.17.3寻找最近点

4.17.4区间查询

4.18动态树与LCT

4.18.1LCT的思想

4.18.2从原树到辅助树

4.18.3LCT的存储和性质

4.18.4LCT的操作

4.18.5LCT的基本应用

小结

第5章动态规划

5.1DP概念和编程方法

5.1.1DP的概念

5.1.2DP的两种编程方法

5.1.3DP的设计和实现

5.1.4滚动数组

5.2经典线性DP问题

5.3数位统计DP

5.3.1数位统计DP的递推实现

5.3.2数位统计DP的记忆化搜索实现

5.3.3数位统计DP例题

5.4状态压缩DP

5.4.1引子

5.4.2状态压缩DP的原理

5.4.3状态压缩DP例题

5.4.4三进制状态压缩DP

5.5区间DP

5.5.1石子合并问题和两种模板代码

5.5.2区间DP例题

5.5.3二维区间DP

5.6树形DP

5.6.1树形DP的基本操作

5.6.2背包与树形DP

5.7一般优化

5.8单调队列优化

5.8.1单调队列优化的原理

5.8.2单调队列优化例题

5.9斜率优化/凸壳优化

5.9.1把状态转移方程变换为平面的斜率问题

5.9.2求一个dp［i］

5.9.3求所有dp［i］

5.9.4例题

5.10四边形不等式优化

5.10.1应用场合

5.10.2四边形不等式优化操作

5.10.3四边形不等式定义和单调性定义

5.10.4四边形不等式定理

5.10.5例题

小结

源码下载

第6章数论和线性代数

6.1模运算

6.2快速幂

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.5异或空间线性基

6.5.1异或空间线性基的概念

6.5.2线性基的构造

6.5.3线性基的应用

6.60/1分数规划

6.6.1二分法与0/1分数规划

6.6.2应用场景

6.7GCD和LCM

6.7.1GCD

6.7.2LCM

6.7.3裴蜀定理

6.8线性丢番图方程

6.8.1二元线性丢番图方程

6.8.2扩展欧几里得算法与二元丢番图方程的解

6.8.3多元线性丢番图方程

6.9同余

6.9.1同余概述

6.9.2一元线性同余方程

6.9.3逆

6.9.4同余方程组

6.10素数(质数)

6.10.1小素数的判定

6.10.2大素数的判定

6.10.3素数筛

6.10.4质因数分解

6.11威尔逊定理

6.12积性函数

6.13欧拉函数

6.13.1欧拉函数的定义和性质

6.13.2求欧拉函数的通解公式

6.13.3用线性筛(欧拉筛)求1～n内的所有欧拉函数

6.14整除分块(数论分块)

6.15狄利克雷卷积

6.16莫比乌斯函数和莫比乌斯反演

6.17杜教筛

6.17.1杜教筛的起源

6.17.2杜教筛公式的推导

6.17.3杜教筛算法和复杂度

6.17.4杜教筛模板代码

小结

第7章组合数学

7.1基本概念

7.2鸽巢原理

7.3二项式定理和杨辉三角

7.4卢卡斯定理

7.5容斥原理

7.6Catalan数和Stirling数

7.6.1Catalan数

7.6.2Stirling数

7.7Burnside定理和Plya计数

7.7.1置换群

7.7.2Burnside定理

7.7.3Plya计数

7.8母函数

7.8.1普通型母函数

7.8.2指数型母函数

7.8.3母函数与泰勒级数

7.9公平组合游戏(博弈论)

7.9.1巴什游戏与Pposition、Nposition

7.9.2尼姆游戏

7.9.3图游戏与SpragueGrundy函数

7.9.4威佐夫游戏

小结

第8章计算几何

8.1二维几何

8.1.1点和向量

8.1.2点积和叉积

8.1.3点和线

8.1.4多边形

8.1.5凸包

8.1.6最近点对

8.1.7旋转卡壳

8.1.8半平面交

8.2圆

8.2.1基本的定义和计算

8.2.2最小圆覆盖

8.3三维几何

8.3.1三维点和线

8.3.2三维点积

8.3.3三维叉积

8.3.4最小球覆盖

8.3.5三维凸包

8.3.6三维几何例题

小结

第9章字符串

9.1进制哈希

9.1.1BKDRHash哈希函数

9.1.2进制哈希的应用

9.2Manacher

9.2.1暴力法求最长回文子串

9.2.2Manacher算法

9.2.3模板代码

9.3字典树

9.3.1字典树的构造

9.3.2模板代码

9.4回文树

9.4.1回文树的关键技术

9.4.2模板代码

9.5KMP

9.5.1朴素的模式匹配算法

9.5.2KMP算法

9.5.3模板代码和例题

9.5.4扩展KMP

9.6AC自动机

9.6.1AC自动机算法

9.6.2模板代码

9.7后缀树和后缀数组

9.7.1后缀树和后缀数组的概念

9.7.2倍增法求后缀数组

9.7.3后缀数组的经典应用

9.8后缀自动机

9.8.1后缀自动机的概念

9.8.2endpos和等价类

9.8.3后缀自动机的构造

9.8.4模板代码

9.8.5后缀自动机的应用

小结

第10章图论

10.1图的存储

10.1.1邻接矩阵

10.1.2邻接表

10.1.3链式前向星

10.2拓扑排序

10.2.1拓扑排序的概念

10.2.2基于BFS的拓扑排序

10.2.3基于DFS的拓扑排序

10.2.4输出拓扑排序

10.3欧拉路

10.3.1欧拉路和欧拉回路的存在性判断

10.3.2输出一个欧拉回路

10.4无向图的连通性

10.4.1割点和割边

10.4.2双连通分量

10.5有向图的连通性

10.5.1Kosaraju算法

10.5.2Tarjan算法

10.6基环树

10.72SAT

10.8最短路径

10.8.1FloydWarshall算法

10.8.2传递闭包

10.8.3Dijkstra算法

10.8.4BellmanFord算法

10.8.5SPFA

10.8.6比较BellmanFord算法和Dijkstra算法

10.8.7负环和差分约束系统

10.9最小生成树

10.9.1Kruskal算法

10.9.2Prim算法

10.9.3扩展问题

10.10最大流

10.10.1FordFulkerson方法

10.10.2EdmondsKarp算法

10.10.3Dinic算法

10.10.4ISAP算法

10.10.5混合图的欧拉回路

10.11二分图

10.12最小割

10.13费用流

小结

附录APython在竞赛中的应用

A.1大数计算

A.2构造测试数据和对拍

A.2.1构造随机数据

A.2.2数据去重

A.2.3对拍

A.3输入/输出

索引

前言/序言

前言

读者拿到这本书的第一感觉可能是： 这本书真厚。接下来他有点忐忑和疑惑： 这本书虽然厚，但是它有价值吗？它的内容和风格适合我吗？还有其他的一些问题。下面做一个详细的解答。

为什么学算法竞赛

算法竞赛是计算机相关竞赛中影响最大的分支。目前国内影响大的计算机算法类竞赛有全国青少年信息学奥林匹克竞赛(NOI)、国际大学生程序设计竞赛(ICPC)、中国大学生程序设计竞赛(CCPC)、蓝桥杯全国软件和信息技术专业人才大赛(软件类)、中国高校计算机大赛团体程序设计天梯赛等。每个竞赛每年的参赛者，少则几万人，多则十几万人。

在大学里，与算法竞赛相关的课程有“计算机程序设计”“数据结构与算法”“算法分析与设计”“程序阅读与编程实践”“算法与程序设计实践”“算法艺术与竞赛”等。

在算法竞赛中获奖有很多好处。在学校可以获得奖学金，保研时获得加分。毕业找工作时更有用，一张算法竞赛的获奖证书是用人单位判断求职者能力的重要依据。算法竞赛受到学校、学生、用人单位的重视和欢迎。

学习和参加算法竞赛，是通往杰出程序员的捷径。竞赛的获奖者基本上都成长为出色的软件工程师，并且有很多人是IT公司的创业者。例如当前热门的自动驾驶公司小马智行的联合创始人兼CTO楼天城，是2009年ICPC全球总决赛第二名； 元戎启行公司的员工大多数是ICPC的金牌队员。

算法竞赛在以下几方面对IT人才培养起到了关键作用：

(1) 编写大量代码。代码量直接体现了程序员的能力。比尔·盖茨说： “如果你想雇用一个工程师，看看他写的代码，就够了。如果他没写过大量代码，就不要雇用他。”Linus说： “Talk is cheap，show me the code.”大量编码是杰出程序员的基本功。算法竞赛队员想获奖，普遍需要写5万~10万行的代码。

(2) 掌握丰富的算法知识。算法竞赛涉及绝大部分常见的确定性算法，掌握这些知识不仅能在软件开发中得心应手，而且是进一步探索未知算法的基础。例如现在非常火爆的、代表了人类未来技术的人工智能研究，涉及许多精深的算法理论，没有经过基础算法训练的人根本无法参与。

(3) 培养计算思维和逻辑思维。一道算法题往往需要综合多种能力，例如数据结构、算法知识、数学方法、流程和逻辑等，这是计算思维和逻辑思维能力的体现。

(4) 培养团队合作精神。在软件行业，团队合作非常重要。像ICPC、CCPC这样的团队赛，把对团队合作的要求放在了重要位置。一支队伍的3个人，在同等水平下，配合默契的话可以多做一两道题，把获奖等级提高一个档次。他们在日常训练中通过长期磨合，互相了解，做到合理分工、优势互补，从而发挥出最优的团队力量。即使是蓝桥杯和NOI这样的个人赛，队员在学习过程中互助互学，也发挥了团队的关键作用。

为什么选用这本书

读者的期望总是很高的。

如果读者是一名算法竞赛的初学者，他非常希望有一本“神书”。读完这本“神书”之后，他或者在参加大公司的算法题面试时自信满满，或者参加算法竞赛时代码喷涌而出，或者在日常工作中能用巧妙的算法解决实际问题……前辈们向他推荐了一些好书，他看了书，做了一些例题，他觉得自己学到了很多算法，掌握了很多竞赛技巧，但是遇到实际问题，或者参加竞赛时，他还是感觉很晕，发现那些书和例题似乎都用不上。神书在哪里？

当他跨过初学者的门槛，他会认识到这样的“神书”其实并不存在。这往往不是书的问题，而是他对书的期望过高了。一些算法竞赛相关的教材确实写得很好，也有很好的口碑，可以说是学习算法竞赛的必读书。但是要将书上的知识转化为自己的能力，需要经过大量的练习，正如陆游诗中所说： “纸上得来终觉浅，绝知此事要躬行。”对应到编程这件事上，有两个重要的学习过程： ①学习经典算法和经典代码，建立算法思维； ②大量编码，让代码成为自己大脑思维的一部分。

算法竞赛的学习难度颇高，它需要一名参赛者掌握以下能力： 丰富的算法知识、快速准确的编码能力、敏捷的建模能力。

学习算法竞赛产生了一个自然的结果： 经过长期深入学习并在算法竞赛中得奖的学生，都建立了对自己计算机编程能力的自信，并能顺利成为出色的程序员。

算法竞赛这样高难度的学习显然不是一蹴而就的。算法竞赛的学习者分为三个层次： 初学者、中级队员和高级队员。本书努力帮助读者顺利度过从初级到高级的学习过程，希望读者看过本书之后，能说一句： “这本书虽然不神，但是还不错！”

本书是一本算法竞赛“大全”，讲解了算法竞赛涉及的绝大部分知识点。书中对应的部分也适合这三种层次的学员，陪伴他们从初学者走向高级队员。

(1) 初学者。一名刚学过C/C++、Java、Python中任意一门编程语言的学生，做了一些编程题目，建立了编码的兴趣，对进一步学习有信心和动力，希望有一本介绍算法竞赛知识点的书指导学习，这本书的初级部分正适合他，帮助他了解基础算法知识点、学习模板代码、练习基础题。经过这样的学习后，他很可能获得蓝桥杯省赛三等奖，甚至更好。不过，他仍没有获得ICPC、CCPC铜奖的能力。

(2) 中级队员。中级队员顺利地跨过了初学者阶段，他证明自己已经走上了成为杰出程序员的道路。中级队员符合这样的画像： 精通编程语言，编码得心应手； 他做过几百道基础算法题，并且准备继续对算法竞赛倾心投入； 他有了志同道合、水平相当的队友一起学习进步； 他遇到了学习瓶颈，计算思维还不够； 他只能做简单题和一些中等题，对难题无从下手。中级队员可能获得蓝桥杯省赛二等奖、一等奖，也差不多有ICPC、CCPC铜奖的水平。本书的中级部分能帮助他进一步掌握算法知识、提高算法思维能力、练习较难的题目。

(3) 高级队员。他们获得了蓝桥杯国赛二等奖或一等奖，以及ICPC、CCPC银牌或金牌。这些奖牌是“高级队员”的标签，他们已经足够被称为“出色的程序员”，在就业市场上十分抢手。本书的高级部分能帮助他们进一步扩展知识点，增强计算思维。

本书的内容介绍

本书内容的难度涵盖了初级、中级、高级，下面对本书的章节按难度做一个划分。