本书是算法竞赛的入门和进阶教材，包括算法思路、模板代码、知识体系、赛事相关等内容。本书把竞赛常用的知识点和竞赛题结合起来，讲解清晰、透彻，帮助初学者建立自信心，快速从实际问题入手，模仿经典代码解决问题，进入中级学习阶段。

全书分为12章，覆盖了目前算法竞赛中的主要内容，包括算法竞赛概述、算法复杂度、STL和基本数据结构、搜索技术、高级数据结构、基础算法思想、动态规划、数学、字符串、图论、计算几何。

本书适合用于高等院校开展的ICPC、CCPC等算法竞赛培训，中学NOI信息学竞赛培训，以及需要学习算法、提高计算思维的计算机工作者。

第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章算法竞赛概述 

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)

参考文献