zcmimi's blog

categories/算法/技巧/共8篇文章

avatar
zcmimi
2020-10-10 19:06:08

分块是一种非常好用的根号算法,本质上是暴力优化技巧

原理是将序列分成\sqrt n块,预处理出每个块的结果,在查询时只需要在完整块的基础上枚举散块更新答案即可

复杂度\mathcal O(n\sqrt n)

avatar
zcmimi
2020-09-25 20:10:32

根号分治是一种

练习

LG 5901 [IOI2009]regions

avatar
zcmimi
2020-09-25 14:51:21

虚树是一种统计树上信息的技术

例题: LG 2495 [SDOI2011]消耗战

如果树的点数很少,可以直接树上dp

可以发现\sum k_i \le 5 \times 10^5

我们可以每次都把提供

总结一下各种启发式合并

什么是启发式合并

可以算是一种技巧

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

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

这就是启发式合并的思想

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

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

avatar
zcmimi
2020-01-26

对于类似f_i=\min_{j=1}^{i-1}f_j+val(i,j)的方程

比如val(i,j)=a_i\times b_j,同时包含了i,j两个变量,

这样没法直接用单调队列

如果把val(i,j)展开能转化成$\frac{y{j1}-y{j2}}{x{j1}-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]满足四边形不等式可以用打表或数

kruskal重构树

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

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

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

否则连接x,y

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

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

avatar
zcmimi
2019-01-20 00:22:39
1/1
Search
search