CSP-S复习计划-LCA

这可能是我的最后一篇博文了,CSP万岁!
用倍增的思想求父亲,然后倍增找祖先就好
但是千万千万注意logs的数组范围,不然暴毙迟早的(找了两天bug没有干什么事的我)

CSP-S复习计划-STL

对就是STL(Soul translater),桐老爷牛逼!
好多好多STL可以用,但是好多都忘了怎么用了(崩溃)

Queue(队列)

Stack(栈)

Set(集合)

List(序列式容器:链表)

Map(关联型容器)

Vecrot(顺序容器)

 ......  查看更多

CSP-S复习计划-次小生成树

思路:先一条一条边加进去,求一棵最少生成树。
然后加一条边,形成一个联通图,存在环,找环上最大的点断,枚举完,得出的就是次小生成树,可能和最小生成树结果是一样的,所以不是严格次小
其实还有很多很多很多地方可以优化,考试时再yy吧。 ......  查看更多

CSP-S复习计划-2sat

学了则么久才知道,2sat原来就是强连通,只不过是拆点了,我以前学的是个什么2sat啊。

CSP-S复习计划-树链剖分

要分清重边和轻边的区别,也要知道什么时候多建一个虚点0,然后把边值上移到点值

CSP-S复习计划-Tarjan强连通

Tarjan强连通可以求强连通(联通子集)的个数,具体的话就等到用的时候就用吧(都那个样)

CSP-S复习计划-网络流

别问我为什么连网络流都要复习,问就是我太菜了
网络流就是找最大可以经过的流量,最小费用最大流就是在网络流的基础上一层一层建边跑出来的。

最小费用最大流模板,就是不停的找最短路,然后减流量就是了 ......  查看更多

CSP-S复习计划-ST稀疏表

ST表可以快速离线求区间最值,

    \[O(nlogn)\]

预处理

    \[O(1)\]

查询
以前没有学过log之前很懵,但是现在清楚很多了(相比两年前)
这题的st数组很特别,相比于树状数组,他

    \[st[i][j]\]

的意思为从第i个开始连续数

    \[2^j\] ......  查看更多

CSP-S复习计划-AC自动机

有n个单词和一句话
求出这句话包括几个单词

这就是一道例题了

很好,看了看,其他的都是套个dp,套个建图的憨憨模板,这个就好,其他自己推吧!

CSP-S复习计划-KMP

KMP

有a串b串,问b串在a串第一次出现的位置

就是简单的KMP模式串匹配而已,重点就是跳fail,和ac自动机原理差不多(更更更简单了)
然后就匹配就好

EXKMP

a串b串,求a[i~lena]与b的最长前缀

这题是exkmp的模板题,还是记模板好了,直接记住p,l的定义,不行就手推就好(反正打不出来就算了吧)
以下这一段都可以跳过不要问我为什么 ......  查看更多