2018暑假七林集训(二)

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\leq100000。

思路:暴力

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注