算法竞赛ICPC、CCPC、NIO、蓝桥杯、天梯赛

前言

🎁🎁🎁本文章将进行超链接，建议大家收藏，在接下来的一年时间，本文章基本可以完成更新，请大家耐心等待~~

⭐️本博客深入解析与算法竞赛相关的数据结构、算法、代码。包括基础数据结构、基本算法、搜索、高级数据结构、动态规划、数论和线性代数、组合数学、计算机几何、字符串和图论。

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

大家对算法有任何疑问都可以在评论区提出来哦！博主会尽最大可能回答哦！因为博主对机器学习、深度学习、AIOT比较感兴趣，所以平时会观看一些算法和数据结构方面的书籍，以下内容是通过罗勇军老师的书籍所写。无论你学习算法的起点在哪里，只要你肯努力，持之以恒，不断探索和实践，你一定会取得进步。每次遇到困难，不要放弃，而是要勇敢地面对它，坚信自己能够克服它。相信自己，相信自己的能力！ 希望大家通过接下来的学习，在算法方面更上一层楼。

以下为学习算法竞赛的思维导图，可能会看不清，请联系博主取图

一、为什么学习算法竞赛

目前国内影响比较大的计算机算法竞赛有全国青少年信息学奥林匹克竞赛（NOI）、国际大学生程序设计竞赛（ICPC）、中国大学生程序设计大赛（CCPC）、蓝桥杯全国软件和信息技术专业人才大赛（软件类）、中国高校计算机大赛-团体程序设计天梯赛等。

学习和参加算法竞赛是通往杰出程序员的捷径。算法竞赛在提高代码量、掌握丰富的算法知识、培养计算思维和逻辑思维、培养团队合作精神等多个方面都有很大的帮助。

二、学习算法的阶段

⭐️初学者
一名刚学过C/C++、Java、Python中任意一门编程语言的学生，做了一些编程题目，建立了编码兴趣，对进一步学习有信心和动力。
⭐️中级者
精通编程语言，编码得心应手，做过几百道基础算法题，并且准备继续对算法竞赛倾心投入，可能遇到学习瓶颈，计算思维还不够。
⭐️高级者
获得过蓝桥杯、ICPC、CCPC、NIO的奖牌。

以下内容按难度进行了划分

阶段	内容	初级	中级	高级
阶段一	基础数据结构	掌握链表、队列、栈，树	掌握堆
阶段二	基本算法	掌握二分法、排序与排列	掌握倍增法、分治法、贪心法
阶段三	搜索	掌握BFS和DFS、洪水填充	掌握双向广搜、IDDFS和IDA*	掌握BFS与双端队列、A*算法
阶段四	高级数据结构	掌握并查集、二叉查找树	掌握树状数组、线段树、LCA、笛卡尔树集	掌握可持久化线段树、动态树与LCT
阶段五	动态规划	掌握DP概念和编程方法、经典线性DP问题	掌握数位统计DP、区间DP、树形DP	掌握一般优化、单调队列优化、四边形不等式优化
阶段六	数论和线性代数	掌握模运算、高斯消元、素数	掌握矩阵的应用、0/1分数规则、威尔逊定理	掌握积性函数、欧拉函数、杜教筛
阶段七	组合数学	掌握鸽巢原理、二项式定理和杨辉三角	掌握卢卡斯定理、容斥原理	掌握母函数、公平组合游戏（博弈论）
阶段八	计算几何		掌握二维几何、圆	掌握三维几何
阶段九	字符串	掌握进制哈希、Manacher	掌握字典树、回文树、KMP	掌握AC自动机、后缀自动机
阶段十	图论	掌握图的储存、拓扑排序	掌握无向图的连通性、有向图的连通性、最短路径	掌握最大流、二分图

⭐️⭐️⭐️下面部分将进行超链接，未进行超链接的部分表示还没有更新

三、算法竞赛具体学习内容

1、基础数据结构

1.1、链表

1.1.1、动态链表

1.1.2、静态链表

1.1.3、STL list

1.2、队列

1.2.1、STL queue

1.2.2、手写循环队列

1.2.3、双端队列和单调队列

1.2.4、优先队列

1.3、栈

1.3.1、STL 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.2、ST算法

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.1、BFS和DFS基础

3.1.1、搜索简介

3.1.2、搜索算法的基本思路

3.1.3、BFS的代码实现

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

3.1.5、BFS和DFS的对比

3.1.6、连通性判断

3.2、剪枝

3.2.1、BFS判重

3.2.2、剪枝的应用

3.3、洪水填充

3.4、BFS与最短路径

3.5、双向广搜

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

3.5.2、双向广搜的两种实现

3.5.3、双向广搜例题

3.6、BFS与优先队列

3.7、BFS与双端队列

3.8、A*算法

3.8.1、贪心最优搜索和Dijkstra算法

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

3.8.3、3种算法的对比

3.8.4、h函数的设计

3.8.5、A*算法例题

3.9、IDDFS和IDA*

3.9.1、IDDFS

3.9.2、IDA*

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.8、LCA

4.8.1、倍增法求LCA

4.8.2、Tarjan算法求LCA

4.8.3、LCA应用

4.9、树上的分治

4.9.1、静态点分治

4.9.2、动态分治

4.10、树链部分

4.10.1、树链剖分的概念

4.10.2、树链剖分的典型应用

4.11、二叉查找树

4.12、替罪羊树

4.12.1、不平衡率

4.12.2、替罪羊树的操作

4.12.3、例题

4.13、Treap树

4.13.1、Treap树的性质

4.13.2、基于旋转法的Treap树操作

4.14、FHQ Treap树

4.14.1、FHQ的基本操作

4.14.2、FHQ Treap树的基本应用

4.15、笛卡尔树

4.15.1、笛卡尔树的概念

4.15.2、用单调栈建笛卡尔树

4.15.3、笛卡尔树和RMQ问题

4.16、Splay树

4.16.1、Splay旋转

4.16.2、Splay树的平摊分析

4.16.3、Splay树的常用操作

4.17、K-D树

4.17.1、从空间到二叉树的转换

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

4.17.3、寻找最近点

4.17.4、区间查询

4.18、动态树与LCT

4.18.1、LCT的思想

4.18.2、从原树到辅助树

4.18.3、LCT的存储和性质

4.18.4、LCT的操作

4.18.5、LCT的基本应用

5、动态规划

5.1、DP概念和编程方法

5.1.1、DP的概念

5.1.2、DP的两种编程方式

5.1.3、DP的设计和实现

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.6、0/1分数规则

6.6.1、二分法与0/1分数规则

6.6.2、应用场景

6.7、GCD和LCM

6.7.1、GCD

6.7.2、LCM

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.2、杜教筛算法和复杂度

6.17.3、杜教筛模板代码

7、组合数学

7.1、基本概念

7.2、鸽巢原理

7.3、二项式定理和杨辉三角

7.4、卢卡斯定理

7.5、容斥原理

7.6、Catalan数和Stirling数

7.6.1、Catalan数

7.6.2、Stirling数

7.7、Burnside定理和polya计数

7.7.1、置换群

7.7.2、Burnside定理

7.7.3、polya计数

7.8、母函数

7.8.1、普通型母函数

7.8.2、指数型母函数

7.8.3、母函数与泰勒级数

7.9、公平组合游戏（博弈论）

7.9.1、巴什游戏与P-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.1.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.1、哈希函数BKDRHash

9.1.2、进制哈希的应用

9.2、Manacher

9.2.1、暴力法求最长回文子串

9.2.2、Manacher算法

9.2.3、模板代码

9.3、字典树

9.3.1、字典树的构造

9.3.2、模板代码

9.4、回文树

9.4.1、回文数的关键技术

9.4.2、模板代码

9.5、KMP

9.5.1、朴素的模式匹配算法

9.5.2、KMP算法

9.5.3、模板代码和例题

9.5.4、扩展KMP

9.6、AC自动机

9.6.1、AC自动机算法

9.6.2、模板代码

9.7、后缀树和后缀树组

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

9.7.2、倍增法求

9.7.3、后缀树的经典应用

9.8、后缀自动机

9.8.1、后缀自动机的概念

9.8.2、endpos和等价类

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.1、Kosaraju算法

10.5.2、Tarjan算法

10.6、基环树

10.7、2-SAT

10.8、最短路径

10.8.1、Floyd算法

10.8.2、传递闭包

10.8.3、Dijkstra算法

10.8.4、Bellman-Ford算法

10.8.5、SPFA算法

10.8.6、比较Bellman-Ford算法和Dijkstra算法

10.8.7、负环和差分约束系统

10.9、最小生成树

10.9.1、Kruskal算法

10.9.2、Prim算法

10.9.3、扩展问题

10.10、最大流

10.10.1、Ford-Fullkerson方法

10.10.2、Edmonds-Karp算法

10.10.3、Dinic算法

10.10.4、SAP算法

10.10.5、混合圆的欧拉回路

10.11、二分圆

10.12、最小割

10.13、费用流