zcmimi's blog

arrow_back倍增共16篇文章

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

先想想暴力做法:

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

优化:

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

先按海拔从高到低排序,这样见出来的kruskal重构树的是海拔的小根堆

我们可以倍增找出最远可以到达的祖先,然后求出这段区间中的点与点1的最小距离

可以在dfs的时候预处理

详见代码

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

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

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

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

kruskal重构树

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

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

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

否则连接x,y

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

连接x,y时,将边权变成一个新的节点t权值为边权,然后连边> t\rightarrow x,t\rightarrow y

代码:

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

解法1

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

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

倍增思想

f[s][i][j]表示最多走s条边,i,j之间最大掉边权和时多少

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

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

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

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

接着用倍增处理出开2^i循环次的数据

然后就直接暴力

具体看代码,码风有点新奇

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

有趣的题

先倍增处理出len_x一个点最长往上跳多少个

然后动态规划

dp_x为在放置最少的情况下x还能再向上跳多少个

那么dp_x = \max(f[to])-1

如果dp_x = -1,那么在选中++ans_x,dp_x = len_x-1

2/2
Search
search