menu zcmimi's blog

arrow_back 倍增

矩阵乘法

这题倍增加速比快速幂快,可以节省很多多余的计算

二进制拆位后才能矩阵运算 ```cpp

include<bits/stdc++.h>

define fur(i,x,y) for(in

zc
2020-05-29 17:09

LCT动态维护最小生成树

维护链上的最大值和次大值

先找出最小生成树,然后枚举剩下的边,找出相差最小的,得出答案

这题还可以用kruskal生成树+倍增(或树剖)做,常数会小很多 ```cp

zc
2020-04-06 22:06

看题意想到了主席树和LCT

LCT套主席树可行,但是比较麻烦,我们用另一种方法

启发式合并+主席树(\mathcal{n \log^2 n})

每次将小的插入到大的,顺便更新倍增LCA

zc
2020-03-01 11:57

```cpp

include<bits/stdc++.h>

define il inline attribute ((always_inline))

define MB temp

zc
2020-01-27 09:31

根据仙人掌图构建圆方树

若两个点的lca是原图的点,那么直接d_x+d_y-2\times d_{lca(x,y)}

否则就是两个点到环的距离加上两个点在环上的最短距离 ```cpp

inc

zc
2020-01-26 22:12

我们可以用倍增求出能控制某个点x的最远的点y的位置

应该将f_xy的点的答案+1

我们可以差分一下,

++ans_{f_x},--ans_{f_y}

然后从下加得到的就是

zc
2020-01-18 22:40

解法1

主席树+离散化(深度太大需要离散化)

```cpp

include<bits/stdc++.h>

namespace ZDY{

#pragma GCC optimize(3
zc
2019-12-31 11:31

可以算是kruskal重构树的模板题

建完kruskal重构树,我们可以发现一个节点(新建的带点权的点)能走到的节点一定在它的子树中

那么我们可以用dfs序+主席树维护

k

zc
2019-12-31 11:31

先想想暴力做法:

bfs出不涉水可以到达的点,然后在这些点中找出与点1的最小距离

优化:

我们可以使用kruskal重构树来快速求出这些点

先按海拔从高到低排序,这样见出来的kruskal

zc
2019-12-31 11:31

先用set预处理出离每个点最近的点和第二近的点

n~1 每次往set里插入{a[i],i} 然后把前驱后继找出来比较一下 具体看代码

(听说有排序后双向链表的神仙做法)

zc
2019-12-21 19:47
1 / 2
Search
search