2020ACM暑期集训 框架（暑期不断更新）

前言:ACM暑期集训自2020.7.6日开始,集训期间一三五学习算法，二四六进行比赛补题讲题，周日周赛。最后进行综合练习。疫情期间特殊原因不能返校，采取线上集训的方式，一天自学算法（看视频和博客）并在VJ尽可能完成拉的练习题，练习题能写多少写多少；一天进行比赛，比赛题要求晚上评讲前全部补完（有复习价值的写一下博客），本博客主要是集训框架，大家可以在这里找到相应的推荐视频和整理的博客进行学习，有问题在群里进行交流。

ACM暑期集训 目录

第一周 C++/二分双指针单调栈/简单搜索第二周 简单数据结构/kmp/字典树第三周 简单DP/背包DP/区间DP第四周 并查集/最小生成树/最短路（包括链式向前星）第五周 树的重心和直径/树状数组/线段树第六周 Tarjan入门/强连通图+割点与桥/二分图（匈牙利）第七周 快速幂、矩阵快速幂/简单数论（gcd,exgcd,素数筛）/数论定理（欧拉定理，费马小定理，威尔逊定理，乘法逆元，同余定理）第八周 普通博弈/SG定理/SummerFinal

第一周 C++/二分双指针单调栈/简单搜索

C++STL/JavaAPI (这一块基本都学过了，这两天直接练题比赛)二分尺取单调栈 推荐视频: y总的二分. 推荐视频: 双指针单调栈. —————————— 博客: 二分查找. 博客: 尺取（双指针）. 博客: 单调栈.简单搜索 推荐视频: 北理DFS BFS. 推荐视频：SJTU搜索入门题讲解. 博客: 搜索（BFS DFS）入门.

---

第二周 简单数据结构/kmp/字典树

简单数据结构 ps:大家看一个视频简单了解一下数据结构（尤其是没学过数据结构的同学，学过的可以不看）里面的相关概念即可，练习与比赛题仍然以 简单搜索为主 推荐视频: SJTU简单数据结构. 博客：树和二叉树(C++)，学过数据结构的同学可以不看. 博客：树和二叉树(C++)(Java)

kmp 推荐视频：只看kmp部分 推荐视频：字符串. 博客：kmp入门. 博客：next数组求最小循环节，记住结论就行，推导不要求掌握

字典树 推荐视频: 这个是通过例题讲解的字典树. 博客：字典树模板（C++）. 博客：字典树模板（Java）

---

第三周 简单DP/背包DP/区间DP

简单DP 推荐视频: SJTU DP. 博客：大家先了解DP是什么，如何写状态方程就行，这个博客这个周有选择地看

背包DP 推荐视频: y总的背包九讲.

区间DP 推荐视频：区间DP讲解 推荐视频: 闫氏DP分析法，大家把前面的巩固一下，y总NB！. 博客：区间DP

---

第四周 并查集/最小生成树/最短路（包括链式向前星）

PS：事实上，最小生成树也会用到并查集，我们学习的并查集刚开始主要是简单并查集，同时也要去理解关系并查集，这四天（包括最小生成树）的练习题和比赛我们也会逐渐练习关系并查集的使用。 (在这一周的学习中，建议大家先了解一下链式向前星的存图方法，可以直接先看最短路那个视频，那个视频的前半部分是图论初步)

并查集 推荐视频：SJTU并查集和最小生成树，最小生成树可以不学，紧接着就会学. 博客：并查集（java）. 博客：并查集C++.

最小生成树 推荐视频：前面的最小生成树会了可以不看，SDU最小生成树讲解. 博客:最小生成树（java）. 博客:最小生成树（C++）

最短路 推荐视频：SJTU最短路. 博客：最短路

---

第五周 树的重心和直径/树状数组/线段树

树的重心和直径 推荐视频:树直径.树状数组，线段树（共四天） 推荐视频：SJTU树状数组，线段树.

---

第六周 Tarjan入门/强连通图+割点与桥/二分图（匈牙利）

PS:其实上面看着是三个东西，其实是Tarjan算法的三种应用。视频看一个就行了，这个星期大家尽量可以使用和更改模板代码，对于一些代码的细节不用深究。

Tarjan 推荐视频：浙师大tarjan,这个学姐讲的超级好的

第七周 快速幂、矩阵快速幂/简单数论（gcd,exgcd,素数筛）/数论定理（欧拉定理，费马小定理，威尔逊定理，乘法逆元，同余定理）

ps: 数论的东西比较杂，大家先看两个视频了解一下ACM中的数论内容和知道相关的数学知识就行。（视频中的一些知识看不懂不用强求，暂时也用不到） 推荐视频：SJTUACM中的数学入门一. 推荐视频：SJTUACM中的数学入门二.

---

第八周 普通博弈/SG定理/SummerFinal

推荐视频：ACM博弈入门:普通博弈. 推荐视频：ACM博弈入门:SG定理. em…等同学们学到这个地方的时候我们呢也快开学了，大家开学实验室见，不见不散！