【Codeforces 187D】BRT Contract(线段树||STL)

Description

有一条路线,路线上有起点终点,中间有n个红绿灯,每单位时间可以行走单位距离,

在0时刻每个红绿灯都是绿色,在$g$时刻后变成红色,再$r$时刻后变回绿色,依次循环。

现在给出距离$d_i$,有$q$组询问,问$x$时刻从起点出发到达终点的时间。

$n,q\leq 100000$,$r,g,d_i\leq 10^9$

题目解析

这是一道很明显的代码题。

解法一

设$dp_i$表示0时刻从$i$号节点出发到达终点的时间。

有$dp_i=dp_j+dis(i,j)$,$j$是从$i$出发后第一个红灯的位置,$dis(i,j)$是到$j$加上等待红灯的时间。

那么答案就是$dis(0,i)+dp_i$,这里的$dis(0,i)$是指$x$时刻出发。

问题转换为了求从$i$点出发第一个红灯的$j$。

首先我们将所有的时间关于终点的0时刻做相对时间,即$i$点的$t$时刻变成了$-sum_i+t$,

$sum_i$是$i$点到终点的距离。将问题转化为模意义下后,

又因为当$sum_i-sum_j\space \in \space [g,g+r)\space mod\space (g+r)$时,$j$合法,

那么当$i$点的0时刻出现在$j$的$[g,g+r)$中时,$j$合法,

我们不妨用线段树/set/map来维护0时刻出发的第一个红灯,

每次将位移之后的$[g,g+r)$区间的标号改成$i$,求$dp_i$时便是询问位移后的0所在位置的标号。

至于回答询问,我们可以看做$d_1=d_1+x$,一样的求出答案。

解法二:(来自Hineven)

我们还是一样的思想,这里我们以起点的0时刻做相对时间,

先将所有的询问离线,对于位移后的区间$[g,g+r)$,将区间内的所有询问合并到$g+r-1$上。

为了统计每个询问等待的时间,我们将每一个位置看做一个点,$g+r-1$向所有被合并的点连边,权值为时间差。

从第一个红路灯到第$n$个红路灯,最后每个叶子节点都代表一个询问,

它的答案就是到根节点的路径权值和加上从起点到终点的距离。

代码

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注