标签:倍增

【题解】洛谷1081/codevs1199 开车旅行 链表,倍增,模拟——litble

题目分析

这题70分暴力很easy...正解有点难想...但是比较容易理解...可是代码比较难打...

work1

我们可以预处理从每一个城市出发小A和小B分别到的下一城市。
怎么处理?排序后用[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】bzoj4326/洛谷2680/codevs5440 运输计划 ——litble

题目描述

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 LANE航线规划 (并查集+倍增LCA+时间倒流+线段树+DFS序) -boshi

收回我以前对某些题的评论--这一道tmd才是最恶心的。

苟活者在淡红的WA中会依稀看见微茫的希望,真正的傻B会更奋然而AC。--某树人

耗时4.5个小时,手写180行代码,套用5种模板,定义1[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】货车运输 codevs – 3287 倍增求lca

1. 题目

传送门= ̄ω ̄=

题目描述 Description

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】find the safest road HDU – 1596

1. 题目

传送门= ̄ω ̄=

problem

XX星球有很多城市,每个城市之间有一条或多条飞行通道,但是并不是所有的路都是很安全的,每一条路有一个安全系数s,s是在 0 和 1 间的实数(包括0[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】 倍增求LCA

1. 何谓LCA

LCA(Least Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。

img

如图,1和7的公共祖先有5和10,而它们的LCA[......]

[继续阅读= ̄ω ̄=]

Read MoreComment