寒假集训总结

· · 个人记录

**Day 1**

今天是年前来到机房集训的第一天，老师今天讲的基础算法，贪心，二分，双指针，位运算。
详情点这里
里面有习题，注意双指针，位运算和反悔贪心要多加巩固！！！

Day 2

今天打了模拟赛，做的一般，没达到预期，不过还好。我就不在多说了，详情点这里，今天讲的是单调栈和队列，再加上离散化，可以听懂，笔记放到专栏里了。

Day 3

今天讲了莫队和ST表，莫队比较好就是时间复杂度较少且可以进行查询，相当于分块进阶版，所以要想练好莫队，分块的练习也不能少，笔记还是放专栏里了。

Day 4

今天讲的是树和树状数组，说句实话，有点没听懂，树，为没有环且互相联通的无向图，树还分很多概念，例如，树的直径，树的重心，子树，可以帮助解决许多类型的问题详情点这里

Day 5 - Day 6

这两天讲的都是DP，分为区间DP和树形DP。
区间DP：主要是三重循环，第一重枚举长度，第二重枚举左端点，第三重枚举k的位置，以此来找出最大或最小答案。
树形DP：主要是自下而上的去推，可能会设很多个dp数组，主要是推出dp的状态转移方程，就能dfs求出答案。

Day 7

今天讲的是最短路问题，主要有以下几个算法：
1.迪杰斯特拉，主要应用是求单源最短路径，但缺点是不能解决边权为负，和判断负环，优点是时间复杂度较少，为m log m
2.floyd 时间复杂度较大为n ^ 3 ，优点是简单暴力，且能判断最小环和负环问题。
3.bellman 算法时间复杂度为nm，优点是可以判断有没有负环的情况。
4.spfa 算法时间复杂度为n ^ 2 ，优点是可以解决负边权，缺点是非常容易被卡时间。

Day 8

今天讲的是并查集和平衡树，其实也没什么好说的。
并查集就是看他们两个在不在一个集合中，然后再合并祖先。
平衡树是一种难但可以用set代替的算法，详情放专栏里了