倍增文章列表
倍增专题
本蒟蒻只会个倍增lca，实在太菜了。 稍微灵活一下的倍增就不会了，所以开一个倍增专题，先把倍增练熟 1.跑路 由每次走 2 k 米很容易想到倍增。 map[k][i][j]表示从i走2 k 米能否走到...倍增,Floyd
[luoguP2680] 运输计划（lca + 二分 + 差分）
传送门 暴力做法 50 ~ 60 枚举删边，求最大路径长度的最小值。 其中最大路径长度运用到了lca 我们发现，求lca的过程已经不能优化了，那么看看枚举删边的过程能不能优化。 先把边按照权值排序，然...stl,tarjan,lca,dfs,倍增
[luoguP3258] [JLOI2014]松鼠的新家（lca + 树上差分）
传送门 需要把一条路径上除了终点外的所有数都 + 1， 比如，给路径 s t 上的权值 + 1，可以先求 x = lca(s，t) 类似数列上差分的思路，可以给 s 和 f[t] 的权值 + 1，给 ...lca,倍增,差分
[bzoj1787][Ahoi2008]Meet 紧急集合（lca）
传送门 可以看出，三个点两两之间的lca会有一对相同，而另一个lca就是聚集点。 然后搞搞就可以求出距离了。 ——代码 1 #include cstdio 2 #include cstring 3 #...lca,倍增
[luoguP2912] [USACO08OCT]牧场散步Pasture Walking（lca）
传送门 水题。 直接倍增求lca。 x到y的距离为dis[x] + dis[y] 2 * dis[lca(x, y)] ——代码 1 #include cstdio 2 #include cstrin...lca,倍增
NOIP2013D1T3货车运输（最大生成树+倍增lca）
传送门 这道题，先用kruskal求一遍图中的最大生成树。 然后，倍增求lca，求lca的同时求出边权的最小值。 #include cstring#include cstdio#include alg...最小生成树,lca,倍增
lca最近公共祖先（模板）
洛谷上的lca模板题—— 传送门 1.tarjan求lca 学了求lca的 tarjan算法（离线） ，在洛谷上做模板题，结果后三个点超时。 又把询问改成链式前向星，才ok。 这个 博客 ，tarja...模板,tarjan,倍增,lca,树链剖分
共1页/7条
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化