day0

我一个蒟蒻为什么会到2期

day1

一、最短路

1.dijkstra（单源求最短路，只适用于边权为正的情况）：工作原理与bfs相似，可以使用堆优化。具体的后面再开坑吧。

2.spfa(单源最短路，适用于有负权的情况)：用一个点的最短路去更新其他的点。具体先坑着。

3.floyd：用于求出所有点对之间的最短路，代码短，常数很小。具体的等着和上面两个最短路的方法一起开坑吧

例题：

1.BZOJ2346：将旋转一次后的边边权设为1，没有旋转的边权为0，寻找最短路（洛谷P4667，洛谷P2243，LOJ2632）

2.BZOJ4152

二、最小生成树：选择n-1条边，把这n个点连成一棵树，并且边权和最小

1.kruskal：按权值从小到大考虑所有边。如果把这条边加入生成树不会出现环，就加入。否则跳过这条边。使用并查集维护连通性。

2.prim：从任意一个定点开始，每次寻找一个与当前点集最近的一个点，并把两点之间的边加入到树中。实现类似dijkstra。可以使用堆维护。

例题：

1.BZOJ3714：最小生成树即为答案。每一可以询问两个前缀和的异或和，只需n个方程且联通0~n即可。

2.NOIP2013货车运输：求出最小生成树，显然只会走最小生成树上的边，倍增求出这条路径上的最大权值即可。

三、强连通分量：如果一个有向图中任意两点都可达，称这个图时强连通的。非强连通有向图的极大强连通分量子图，称为强连通分量（SCC）

1.tarjan：对图进行DFS，建出一颗DFS树。需要用一个站stack存放所有没决定SCC的点。剩下的先坑着。

例题：

1.BZOJ1179：SCC缩点，然后就是DAG上求最长路

2.BZOJ2208：SCC缩点，然后统计从一个SCC能够到达的SCC的点数和。可以在DAG上dp，bitset加速转移即可。

四、例题

1.BZOJ4398：相当于有一些关键点，求它们两两之间最短路的最小值。二进制分组，其中一组作为起点，另外的点作为重点，跑最短路即可。

2.NOI2018D1T1：kraskal重构树。求最大生成树，每次往树里加边时，新建一个点代表这条边，然后把那两个联通快连到这个点上。如果x有一个祖先y，边权为a，那么从x出发，不经过权值<=a的边，所能到达的点就是y子树中的所有点。

第一天就先写到这里吧。

day2

1.倍增：这个太简单就不说了把

2.ST表：这个后面再开坑吧

3.最近公共祖先：先提到同一深度，然后倍增向上跳

例题：

1.SCOI2015国旗计划：每次贪心选择右端点最靠右的区间，于是每个区间都有一个确定的后继区间，一个一个跳过去可以统计答案。 倍增加速即可。

2.BZOJ4818简化版

description：求有多少个长为n的序列，元素在0~m之间，并且和是p的倍数。 n，m $\leq 10^{9}$ ，p $\leq 100$ 。

思路：和快速幂基本一样。 f(i,j)表示长为 $2^i$ 且和为j的序列有多少个。 f(i,j)= $\sum_{x+y=j} f(i-1,x)\times f(i-1,y)$

4.线段树：这个先坑着

例题：

1.description：维护一个颜色序列，支持区间修改颜色，询问一个区间有多少个颜色段。 n,m $\leq 10^{5}$ 。

思路：线段树每个点维护颜色段数量，左端点颜色，右端点颜色。合并时看…………

2.description：维护一个整数序列，支持单点修改，询问区间最大子段和。

思路：线段树每个点维护这个区间的最大子段和，左端点开头的最大子段和，右端点结尾的最大子段和。合并时讨论各种情况。

类似：洛谷P4513小白逛公园

3.BZOJ4653：按照区间长度排序，一个左端点对应的合法最小右端点递增。双指针维护左端点对应的右端点即可。需要用到线段树区间加，全局max。

5.树状数组：坑着

拓展：二位树状数组：还是坑着

例题：

1.BZOJ1452（洛谷P4054）：对每种权值维护一个二维树状数组

2.BZOJ3747：枚举右端点，维护对应的左端点的权值。加入一个物品i时，找到上一个这种物品的出现位置prei，把[prei+1，i]区间加上这个物品的权值。线段树实现。

3.BZOJ3594：显然这k个区间右端点都是n，f(i,j)表示前i个数，上升j次的最大LIS。 f(i,j)=max{f(x,y)+1}(y<j, $a_{x}$ +y< $a_{i}$ +j)。二维树状数组优化。

4.

description：维护一个数列，三种操作：单点加；区间对某一个数取模；询问区间和。 n,m $\leq$ 100000。

思路：暴力

5.LOJ6062：把b排序，一个 $a_{i}$ 可以和b的一个后缀匹配， $a_{i}$ 可以覆盖一个后缀。显然有解的条件是 $b_{i}$ 至少要被i个数覆盖。加入一个数时把它对应的后缀+1，线段树维护max{ $val_{i}$ -i}即可。

6.线段树合并：暴力不解释

例题：

1.BZOJ3307

2.THUWC2018 D1T2

3.BZOJ3262

4.BZOJ4237

第二天就这样了，感觉留的坑有点多呀。。。

day3

orz王思齐大佬（今天好像是~~某人的生日~~七夕）

1.dfs序：

把树dfs一边，走到一个节点就加进序列。 dfs序中，一个节点的子树一定是连续的一段。结合线段树可以对子树进行操作。

2.欧拉序：

把树dfs一遍，进入一个节点和离开时都把它加进序列。对于两个节点，欧拉序上，它们之间深度最小的节点是lca。用st表预处理后可以实现O(nlogn)预处理，O(1)查询的lca。如果将进入视为+，离开视为-，那么到当前节点的前缀和就是根节点到当前节点的链的和。

3.树链剖分：

把一颗树划分成若干条祖先到子孙的链。

即每个点只有一个儿子和他在一条链上，一般叫重儿子。

这个儿子可以选择子树大小最大的（重链剖分），或者向下延伸的链最长的（长链剖分）。。

将一棵树进行重链剖分后，从根往叶子走，每次走到一条新的链上时，新链子树的大小不超过旧链子树的大小，所以每次会让大小减半。总链数是logn的。

在dfs时，如果优先走重儿子，可以发现中联上的点标号连续。

这样可以把一个原树上的一条链变成最多2log条重链上的区间。

对于一条链u-v，如果它们在一条中联上，那么可以直接查询，否则需要将当前重链顶端深度较大的一个跳到当前重链顶端的父亲。

例题：

1.bzoj4034（洛谷P3178）：树链剖分不解释

2.bzoj1036（洛谷P2590）：树链剖分+线段树

3.bzoj3083（洛谷P3979）：树链剖分+线段树

4.bzoj4551（洛谷P4092）：树链剖分裸题（也可以是神奇的并查集）

5.bzoj3307（洛谷P4556）：线段树合并or神奇的树链剖分

6.bzoj3991（洛谷P3320）：虚数+set+dfs序（玄学。。。）

4.树分治

（1）点分治

（2）边分治

例题：

1.bzoj3365/1468（洛谷P1608）：树状数组or点分治

2.bzoj2599：点分治，map维护

3.bzoj3697：点分治

4.bzoj2152：点分治模板or树形dp

5.bzoj3730：点分治重构树

6.bzoj1095：开始进入玄学了。。。

7.bzoj4598

8.bzoj4860

9.bzoj4317

我仿佛已经感受到了下午即将爆零，溜了溜了。

day4

由于今天的题目过于毒瘤，就不附思路了。

1.扫描线：

对于二维平面上的一些点，直接处理可能需要二维数据结构，这是可以按一维排序后使用一维数据结构维护。

例题：

1.bzoj4822

2.bzoj2743

3.hdu6369

2.trie：

一般的trie就是每个点开个大小为字符集的数组，存他的儿子。

但是这样的trie不常用，一般常用的都是bitwise trie（二叉trie）。

一个二叉trie可以认为是一个值域为0~ $2^{k}-1$ 的线段树。

例题：

1.bzoj 3689

3.可持久化

常见的可持久化数据结构有并查集、堆、线段树、平衡树等。

常见的可持久化方法有path copy和fat node。

4.可持久化线段树

把操作过的节点新建一遍。

可持久化平衡树的思想类似。

例题：
1.bzoj3932

5.可持久化堆

一般写左偏树。

在merge时新建节点。

例题：

1.bzoj3673/3674

6.可持久化树状数组

例题：

1.bzoj4103

2.bzoj2588

3.bzoj2653

4.bzoj4571

5.bzoj3784

居然昨天写的不见了，重新补的有点水，将就吧。

day5

题目的证明都挺长的，而且数学公式不少，和昨天一样省略思路。

wxh：对拍大法好

1.斜率优化

先来一个凸包：例题——洛谷P2742

例题：

1.bzoj1010（洛谷P3195）

2.bzoj4518

3.bzoj3675

2.决策单调性

对于一些dp方程，经过一系列的猜想和证明，可以得出，所有取的最优解的转移点（即决策点）位置是单调递增的。

例题：

1.LOJ6039

2.CF868F：和莫队有点关系~~（莫队是什么）~~

补充例题：bzoj1492：cdq分治

day6

莫名其妙没有保存起，崩溃இ௰இ

例题已经记不清题号了，就不列出来了。

上午：

1.树形DP

2.状压DP

3.期望DP

下午：

滚回高二大班了。

1.可持久化线段树（主席树）：先坑着

2.st表

3.分块：蒟蒻表示不会

day7

上午：

1.并查集

例题：

1.bzoj1202（洛谷P2294）

2.bzoj4569（洛谷P3295）

2.拓扑排序

3.最小生成树

4.最近公共祖先

5.树链剖分

6.几道水题，略过

下午：

1.单源最短路

2.多源最短路

3.几道简单题

4.强连通分量

5.无向图的点双，边双，割点和桥

6.又是几道简单题

day8

杂题选讲，懒得列出来了。

day9

数论专题，没救了。。。

1.矩阵乘法

2.欧几里得定理

3.拓展欧几里得定理

4.置换群

5.乘法逆元

6.BSGS

7.中国剩余定理

8.线性筛

9.欧拉函数

10.容斥原理

11.莫比乌斯函数

12.高斯消元

13.线性基

day10

计算几何。。。说白了基本高中数学，表示懵逼，懒得写了。

2018暑假七林集训（二）