2024暑假集训总结

知识点清单：

树状数组拓展：

（1）k维前缀和

（2）树状数组+倍增 没码过，小慌

线段树：

（1）线段树不仅仅是一个维护区间和、区间最值或者类似于方差那道题，维护区间的平方等等信息，它的深层是将区间拆分为 \(O(logn)\) 个子区间从而将修改与查询降为 \(O(log n)\) 级别，因此对于线段树的使用不能死板，它还可以维护很多区间信息，例如一个矩阵，lmax,rmax,等等等等。

（2）线段树优化dp，这个目前感觉很少遇到过很难的，基本暴力dp一列，用线段树优化就很显然？

（3）线段树上二分

（4）动态开点线段树，是在数据规模很大的情况下使用的，用于减少不必要的空间消耗

（5）线段树合并，目前做题太少对其应用的了解不大深刻，只知道能够以 \(O(log n)\) 的时间复杂度合并两棵线段树

（6）可持久化线段树，用于维护历史信息的线段树，核心思想还是线段树，实现方式跟动态开点的版本大同小异

（7）扫描线，解决矩形面积并之类的问题

离线分治算法：

（1）线段树分治

（2）cdq分治：降低维度的分治

（3）整体二分 ：基于值域的分治，避免多次二分，仅二分一次，但每次二分会把所有原会被访问到的情况都访问，这样虽然情况看似增多，但复杂度还是一个\(O(log n )\)级别的

Dp:

感觉还行？具体的一些地方，先把题码个差不多再总结吧。

图论：

（1）最短路：典型应用的话感觉大多偏分析结论然后套板子，其中的分层图最短路需要仔细斟酌一下建边，后面两个部分，差分约束和同余最短路是讨论的重点。

1）差分约束：差分约束解决的问题是，有n个变量 \(x1,x2,...,xn\)，以及若干个差分方程 \(xi −xj ≤ c(1 ≤ i,j ≤ n,i= j)\)，求出一组合法解。通过一些建边加上最短路就可以解决。

2）同余最短路：只会基础，理解不够深刻

（2）最小生成树

1）Kruscal算法：贪心的按照边权从小到大遍历，如果当前边的两点已联通就不加反之，加

2）Prim算法：类似于Dij

3）Brovka算法：思想非常简单。初始时每个点都是一颗不同的树，每次遍历边表，找距离每棵树最近的另一棵树，并把它们连起来。可以发现，每一次一棵树都与另一棵树连接起来，所以每次树的数量都至少减少到一半，所以这样操作的次数为\(O(logV)\)次。每次我们遍历边表，连接所用的时间为\(O(E+V∗α(V))\)，所以总复杂度为\(O(ElogV)\)。

对于这三种算法的使用具体还得看题目了，目前对于这三种算法的具体使用做题还是少了。

（3）有向图连通性：强联通分量这里懂了，2-SAT 就是解决一类给定多个限制条件，条件形式类似于 a,b至少成立一个，判断有无解，求解，此时的建边给我的感觉很像扩展域并查集，跑一个 Tarjan 就差不多了。

（4）无向图连通性：

1）点双，边双，缩点，割点，割边

2）圆方树

3）欧拉回路

额……以及期间遇见的很多神奇的建图技巧，例如线段树优化建图，前缀和优化建图，倍增优化建图？

（5）网络流：只会基础

字符串

Hash：用于判断两个东西是否相同，所以实际的应用不仅仅是字符串Hash，还有树Hash或者一些别的？Hash 的写法一定一定要注意注意，之前因为Hash冲突有一道题调了一晚上，但是很奇异的是双Hash不是很难被卡吗，那天双 Hash 竟然能被 洛谷卡掉，应该是Hash 模数的问题，背后的原理，我回头再找一下。

Kmp：Kmp里面的那个f[]太有用了很多题都是基于f[]搞的

AC自动机 ：Kmp上树？

Manacher：……感觉这几个字符串算法都不算很难（）

树上问题

（1）LCA的另一种求法：

​ 考虑一棵树的欧拉序（不妨记为seq），即任何时候进入节点（包括 第一次和回溯的时候）时都要记录一下编号。 如果记pu表示u第一次出现所在位置，则从pu到pv上的点一定 包含\(lca(u,v)\)且不包含比它更浅的点。 所以只需要求出\(argminpv i=pu depseqi\) 即可。 这里用经典的倍增求RMQ做法即可做到\(O(1)\)查询。

（2）树的直径：两次dfs

（3）树的重心：

1）使得删去这个点后，剩余子树大小最大值最小的点被称为树的重心。

2）重心的数量最多有两个，如果有两个，则它们相邻。

3）删掉重心后，所有子树大小不超过整棵树的一半。

4）所有点到某个点的距离和中，到重心的距离之和最小，如果有两个重心那么和相同。

5）在删除或加入一个叶子，最多只会引起重心移动一条边。

6）求法也很简单，对于每个点求出所有子树大小（别忘了上面那个子树）后按照定义求解即可

（4）重剖 这个东西也没啥好说的，之前已经学过了

（5）dsu on Tree ：对于这个东西感觉说不上来……额……不会

（6）虚树，虚树就是注意到了原树有很多地方对答案是无贡献的于是只保留有贡献的点，建立起一棵虚树，用来降低规模。好像没写过相关的题，有点慌……

数论

对于这部分，我就偷个小懒？主要的问题是莫反推式子，那些题吧，老师推的时候感觉也很对，自己一推就蒙了，技巧还是不熟呗，然后其它的部分，没有什么太大的问题。