第1章算法竞赛概述
1.1培养杰出程序员的捷径
1.1.1编写大量代码
1.1.2丰富的算法知识
1.1.3计算思维和逻辑思维
1.1.4团队合作精神
1.2算法竞赛与创新能力的培养
1.3算法竞赛入门
1.3.1竞赛语言和训练平台
1.3.2判题和基本的输入与输出
1.3.3测试
1.3.4编码速度
1.3.5模板
1.3.6题目分类
1.3.7代码规范
1.4天赋与勤奋
1.5学习建议
1.6本书的特点
第2章算法复杂度
2.1计算的资源
2.2算法的定义
2.3算法的评估
第3章STL和基本数据结构
3.1容器
3.1.1vector
3.1.2栈和stack
3.1.3队列和queue
3.1.4优先队列和priority_queue
3.1.5链表和list
3.1.6set
3.1.7map
3.2sort()
3.3next_permutation()
第4章搜索技术
4.1递归和排列
4.2子集生成和组合问题
4.3BFS
4.3.1BFS和队列
4.3.2八数码问题和状态图搜索
4.3.3BFS与A*算法
4.3.4双向广搜
4.4DFS
4.4.1DFS和递归
4.4.2回溯与剪枝
4.4.3迭代加深搜索
4.4.4IDA*
4.5小结
第5章高级数据结构
5.1并查集
5.2二叉树
5.2.1二叉树的存储
5.2.2二叉树的遍历
5.2.3二叉搜索树
5.2.4Treap树
5.2.5Splay树
5.3线段树
5.3.1线段树的概念
5.3.2点修改
5.3.3离散化
5.3.4区间修改
5.3.5线段树习题
5.4树状数组
5.5小结
第6章基础算法思想
6.1贪心法
6.1.1基本概念
6.1.2常见问题
6.1.3Huffman编码
6.1.4模拟退火
6.1.5习题
6.2分治法
6.2.1归并排序
6.2.2快速排序
6.3减治法
6.4小结
第7章动态规划
7.1基础DP
7.1.1硬币问题
7.1.20/1背包
7.1.3最长公共子序列
7.1.4最长递增子序列
7.1.5基础DP习题
7.2递推与记忆化搜索
7.3区间DP
7.4树形DP
7.5数位DP
7.6状态压缩DP
7.7小结
第8章数学
8.1高精度计算
8.2数论
8.2.1模运算
8.2.2快速幂
8.2.3GCD、LCM
8.2.4扩展欧几里得算法与二元一次方程的整数解
8.2.5同余与逆元
8.2.6素数
8.3组合数学
8.3.1鸽巢原理
8.3.2杨辉三角和二项式系数
8.3.3容斥原理
8.3.4Fibonacci数列
8.3.5母函数
8.3.6特殊计数
8.4概率和数学期望
8.5公平组合游戏
8.5.1巴什游戏与Pposition、Nposition
8.5.2尼姆游戏
8.5.3图游戏与SpragueGrundy函数
8.5.4威佐夫游戏
8.6小结
第9章字符串
9.1字符串的基本操作
9.2字符串哈希
9.3字典树
9.4KMP
9.5AC自动机
9.6后缀树和后缀数组
9.6.1概念
9.6.2用倍增法求后缀数组
9.6.3用后缀数组解决经典问题
9.7小结
第10章图论
10.1图的基本概念
10.2图的存储
10.3图的遍历和连通性
10.4拓扑排序
10.5欧拉路
10.6无向图的连通性
10.6.1割点和割边
10.6.2双连通分量
10.7有向图的连通性
10.7.1Kosaraju算法
10.7.2Tarjan算法
10.82SAT问题
10.9最短路
10.9.1FloydWarshall
10.9.2BellmanFord
10.9.3SPFA
10.9.4Dijkstra
10.10最小生成树
10.10.1prim算法
10.10.2kruskal算法
10.11最大流
10.11.1FordFulkerson方法
10.11.2EdmondsKarp算法
10.11.3Dinic算法和ISAP算法
10.12最小割
10.13最小费用最大流
10.14二分图匹配
10.15小结
第11章计算几何
11.1二维几何基础
11.1.1点和向量
11.1.2点积和叉积
11.1.3点和线
11.1.4多边形
11.1.5凸包
11.1.6最近点对
11.1.7旋转卡壳
11.1.8半平面交
11.2圆
11.2.1基本计算
11.2.2最小圆覆盖
11.3三维几何
11.3.1三维点和向量
11.3.2三维点积
11.3.3三维叉积
11.3.4最小球覆盖
11.3.5三维凸包
11.4几何模板
11.5小结
第12章ICPC区域赛真题
12.1ICPC亚洲区域赛(中国大陆)情况
12.2ICPC区域赛题目解析
12.2.1F题Friendship of Frog(hdu 5578)
12.2.2K题Kingdom of Black and White(hdu 5583)
12.2.3L题LCM Walk(hdu 5584)
12.2.4A题An Easy Physics Problem(hdu 5572)
12.2.5B题Binary Tree(hdu 5573)
12.2.6D题Discover Water Tank(hdu 5575)
12.2.7E题Expection of String(hdu 5576)
12.2.8G题Game of Arrays(hdu 5579)
12.2.9I题Infinity Point Sets(hdu 5581)
参考文献

第3章STL和基本数据结构
容器
队列
栈
链表
set
map
STL(Standard Template Library)是C++的标准模板库，竞赛中很多常用的数据结构、算法在STL中都有，熟练地掌握它们在很多题目中能极大地简化编程。本章所介绍的内容是竞赛训练的基本内容，需要完全掌握。
STL包含容器(container)、迭代器(iterator)、空间配置器(allocator)、配接器(adapter)、算法(algorithm)、仿函数(functor) 6个部分。本章介绍容器和两个常用算法。
3.1容器
STL容器包括顺序式容器和关联式容器。
1. 顺序式容器
顺序式容器包括vector、list、deque、queue、priority_queue、stack等，它们的特点如下。
 vector： 动态数组，从末尾能快速插入与删除，直接访问任何元素。
 list： 双链表，从任何地方快速插入与删除。
 deque： 双向队列，从前面或后面快速插入与删除，直接访问任何元素。
 queue： 队列，先进先出。
 priority_queue： 优先队列，最高优先级元素总是第一个出列。
 stack： 栈，后进先出。
2. 关联式容器
关联式容器包括set、multiset、map、multimap等。
 set： 集合，快速查找，不允许重复值。
 multiset： 快速查找，允许重复值。
 map： 一对多映射，基于关键字快速查找，不允许重复值。
 multimap： 一对多映射，基于关键字快速查找，允许重复值。
3.1.1vector
视频讲解
数组是基本的数据结构，有静态数组和动态数组两种类型。在算法竞赛中，编码的惯例是： 如果空间足够，能用静态数组就用静态数组，而不用指针管理动态数组，这样编程比较简单并且不会出错； 如果空间紧张，可以用STL的vector建立动态数组，不仅节约空间，而且也不易出错。
vector
http://www.cplusplus.com/reference/vector/vector/。是STL的动态数组，在运行时能根据需要改变数组大小。由于它以数组形式存储，也就是说它的内存空间是连续的，所以索引可以在常数时间内完成，但是在中间进行插入和删除操作会造成内存块的复制。另外，如果数组后面的内存空间不够，需要重新申请一块足够大的内存。这些都会影响vector的效率。
vector容器是一个模板类，能存放任何类型的对象。
1. 定义
其示例如表3.1所示。
表3.1vector定义示例
功能例子说明
定义int型数组
vector(int) a;默认初始化，a为空
vector(int) b(a);用a定义b
vector(int) a(100);a有100个值为0的元素
vector(int) a(100, 6);100个值为6的元素
定义string型数组
vector(string) a(10,"null");10个值为null的元素
vector(string) vec(10,"hello");10个值为hello的元素
vector(string)b(a.begin(), a.end());b是a的复制
定义结构型数组struct point { int x, y; };
vector(point) a;a用来存坐标
用户还可以定义多维数组，例如定义一个二维数组：
vector(int) a［MAXN］;
它的第一维大小是固定的MAXN，第二维是动态的。用这个方式可以实现图的邻接表存储，细节见本书10.2节。
2. 常用操作
vector的常用操作如表3.2所示。
表3.2vector的常用操作
功能例子说明
赋值a.push_back(100);在尾部添加元素
元素个数int size=a.size();元素个数
续表
功能例子说明
是否为空bool isEmpty=a.empty();判断是否为空
打印cout((a［0］((endl;打印第一个元素
中间插入a.insert(a.begin()+i, k);在第i个元素前面插入k
尾部插入a.push_back(8);尾部插入值为8的元素
尾部插入a.insert(a.end(), 10,5);尾部插入10个值为5的元素
删除尾部a.pop_back();删除末尾元素
删除区间a.erase(a.begin()+i, a.begin()+j);删除区间［i, j-1］的元素 删除元素a.erase(a.begin()+2);删除第3个元素
调整大小a.resize(n)数组大小变为n
清空a.clear();清空
翻转reverse(a.begin(), a.end());用函数reverse()翻转数组
排序sort(a.begin(), a.end());用函数sort()排序，从小到大排
下面用一个例题来说明vector的使用。
hdu 4841 “圆桌问题”
圆桌边围坐着2n个人。其中n个人是好人，另外n个人是坏人。从第一个人开始数，数到第m个人，立即赶走该人； 然后从被赶走的人之后开始数，再将数到的第m个人赶走，依此方法不断赶走围坐在圆桌边的人。
预先应如何安排这些好人与坏人的座位，才能使得在赶走n个人之后圆桌边围坐的剩余的n个人全是好人？
输入： 多组数据，每组数据输入： n,m≤32767。
输出： 对于每一组数据，输出2n个大写字母，“G”表示好人，“B”表示坏人，50个字母为一行，不允许出现空白字符。相邻数据间留有一个空行。
输入样例：
2 3

本书对知识点进行了精心的剖析。很多知识点看起来复杂难解，但如果结合清晰的代码、生动的文字、通俗的比喻、一目了然的图解、画龙点睛的注解，能让人有一种豁然开朗的感觉。这也是本书写作的目标。

算法竞赛，例如ACMICPC、CCPC等，在中国已经
活跃多年，是最具影响力的大学生计算机竞赛。目前，
已经出版的算法竞赛书也有30多部，有一些被队员们奉
为“宝书”，有很好的口碑。本书作者是竞赛教练，因
为工作的原因，详细阅读过这些书。这些书，或者讲解
深刻让人佩服，或者娓娓道来令人愉悦，或者洋洋大观
让人欲罢不能。读经典书，甘之如饴。在多年的竞赛教
练工作中，本书作者作为喜欢自我表现的社会人，也常
常跃跃欲试，试图写出一本新的经典书。本书作者认为
，竞赛队员在算法竞赛学习中的痛点需求如下。算法思
路： 一点就透，豁然开朗。模板代码： 结构精巧，清
晰易读。知识体系： 由浅入深，逐步推进。赛事相关
： 参赛秘籍，高手经验。上面立的几个flag虽然高不
可攀，但确实是本书作者内心的旗帜。本书是一本“竞
赛书”，不是计算机算法教材，也不是编程语言书，因
此对大多数知识点本身不会做过多的讲解，而是把重点
放在讲解竞赛所常用的知识点上，以及如何把知识点和
竞赛题结合起来。当然，由于编程竞赛涉及太多知识点
，一本竞赛书不可能面面俱到，把所有内容都堆砌进来
。市面上还有太多经典的算法教材和编程语言教材，这
都是竞赛队员应该认真阅读的。本书对知识点进行了精
心的剖析。很多知识点看起来复杂难解，但如果结合清
晰的代码、生动的文字、通俗的比喻、一目了然的图解
、画龙点睛的注解，就能让人豁然开朗。这也是本书的
目标。代码能力体现了编程者的实力。学习别人的好代
码是提高自己编码水平的捷径。本书把知识点讲解和竞
赛题目紧密地结合在一起，同时给出实用的代码。这些
代码有的是作者精心组织和编写的，有的是搜索大量资
料后进行整理总结的结果。其中很多代码完全可以作为
编程的模板，希望能对参赛学生起到参考的作用。特别
是经典问题，往往有经典代码，凝结了很多人的劳动。
本书作者并没有独创经典代码的能力，因此书中不可避
免地引用和改写了一些公开的代码。对于一些能找到出
处的经典代码，在书中都标注了出处。本书主要面向初
学者和中级进阶者。初学者面对海量繁杂的竞赛知识点
往往会产生深深的无力感和挫折感，本书由浅入深地讲
解知识点，逐步推进，帮助初学者建立自信心，从而快
速地从能理解的实际问题入手，模仿经典代码解决问题
，进入中级学习阶段。竞赛是很专业的活动，经验非常
重要。书中就一些日常训练和参赛的细节问题介绍了作
者的体会。学习算法竞赛有很大难度，需要精通编程语
言、掌握很多算法，但是这并不意味着需要先学好算法
和编程语言才能进行竞赛训练。事实上，建议初学者从
零基础就开始学习算法编程竞赛，与算法学习和语言学
习同步进行。竞赛是操练的擂台，竞赛题目把知识点和
具体问题结合起来，让学到的知识有了打击的“力点”
。以上是本书的特点，希望本书能给算法竞赛的初学者
和进阶学习者以较大的帮助。如果是初学者，通过本书
可以快速入门，例如了解竞赛的知识点、建立算法思维
、动手写出高效率的代码。如果是中级进阶者，学习本
书，可以更透彻地掌握复杂算法的思想、学习经典代码
、完善知识体系，从而更自信地加入到竞争激烈的比赛
活动中。本书提供教学大纲、教学课件、程序源码，扫
描封底的课件二维码可以下载； 本书还提供120分钟的
视频讲解，扫描书中的二维码可以在线观看。在本书的
编写过程中，华东理工大学竞赛队员提出了一些建议，
感谢2015级队长姚远，以及王亦凡、王泽宸、翁天东、
傅志凌等队员。作者2019年5月
源码下载

本书是算法竞赛的入门和进阶教材，包括算法思路、模板代码、知识体系、赛事相关等内容。本书把竞赛常用的知识点和竞赛题结合起来，讲解清晰、透彻，帮助初学者建立自信心，快速从实际问题入手，模仿经典代码解决问题，进入中级学习阶段。
全书分为12章，覆盖了目前算法竞赛中的主要内容，包括算法竞赛概述、算法复杂度、STL和基本数据结构、搜索技术、高级数据结构、基础算法思想、动态规划、数学、字符串、图论、计算几何。
本书适合用于高等院校开展的ICPC、CCPC等算法竞赛培训，中学NOI信息学竞赛培训，以及需要学习算法、提高计算思维的计算机工作者。