zcmimi's blog

arrow_back技巧共16篇文章

总结一下各种启发式合并

什么是启发式合并

可以算是一种技巧

比如要合并集合A,B,设|A|<|B|

这时候将 向B中插入A 的效率要比 向A插入B

这就是启发式合并的思想

Q: 很简单,但有什么用?

A: 假设我们要合并n个元素

avatar
zcmimi
2020-02-29

01背包

每个物品只能使用一次

普通多重背包

将可以用多次的物品拆为多个单次使用的物品

转化为01背包

二进制优化多重背包

但每个物品可以用的次数特别大的时候,如果还是直接拆很有可能会tle

[LG 1776 宝物筛选](https://www.luogu.com.c

avatar
zcmimi
2020-01-30

换根树链剖分

loj #139.树链剖分

前置知识:树链剖分

题意:树链加,子树加,需要支持换根,查询树链和,子树和

树链加、查询树链和 与普通的树链剖分一样

主要讲:

需要支持换根,子树加,查询子树和

设当前查询的点为x

avatar
zcmimi
2020-01-10

四边形不等式

定义

对于任意a_1\le a_2<b_1\le b_2,满足m[a_1,b_1]+m[a_2,b_2]\le m[a_1,b_2]+m[a_2,b_1]

那么m[i,j]满足四边形不等式

要证明m[i,j]满足四边形不等式可以用打表或数

avatar
zcmimi
2020-01-02

形态: 在一棵树上加多一条边

实现:

找出环后一次处理环上每个点的子树,然后再处理环

[IOI 2008]Island(求基环树直径)

IOI 2008 Island

先找出环,把环当根节点,找出每棵

kruskal重构树

我们回想一下kruskal生成最小生成树的过程:

先将边按边权从小到大排序,然后依次加入

如果x,y已经联通,则跳过这条边

否则连接x,y

kruskal重构树是在kruskal生成最小生成树的,

连接x,y时,将边权变成一个新的节点$

avatar
zcmimi
2019-11-11

静态链分治用于解决静态树上众数问题,比如Codeforces\ 600E

静态链分治是离线算法,有点像莫队,复杂度\Theta (n \log n \log n)

比如说遍历一遍子树可以得出答案,但是每棵子树

avatar
zcmimi
2019-11-01

点分治

点分治用于大规模处理树上路径

树的重心

树的最大子树最小的点

性质:每一个子树的大小都不超过\frac n2

```cpp int rt,mxs=inf,siz[N];// 当前 根,最大子树大小 void frt(int x,int f){ siz[x]=1

前置知识: 莫队算法(Mo's Algorithm)

树上莫队:

也就是把莫队搬到树上

入手模板: SP10707 COT2 - Count on a tree II

给定一个n个节点的树,每个

avatar
zcmimi
2019-01-30

建树

tarjan求出双连通分量后把其中的点连向新建的节点

建成的新图(树)即为圆方树

**性质:可

1/2
Search
search