南宁市网站建设_网站建设公司_论坛网站_seo优化

P14370 [JOISC 2018] 最差的记者 3 / Worst Reporter 3Solution

注意：我个人推荐 LibreOJ 题面，看这份的样例图片会好不止亿点点。

前言

在考场上只拿了12 1212分（只想出了Subtask 2）QwQ，大佬勿喷！

这道题纯模拟可以把Subtask 2的分数拿下（因为数据实在太小了），时间复杂度O ( n + q t ) \mathcal{O}(n+qt)O(n+qt)，已经到达10 14 10^{14}1014级别了，肯定爆。

所以我们需要一种算法可以达到O ( n + q ) \mathcal{O}(n+q)O(n+q)（即线性处理），好在它_并不困难。

思路

Part I.

我们会发现一件特别有意思的事情。

每个人的移动周期等于单次的移动距离。

其实这就好写了，我们也得到了一个我们需要的线性的方法：递推。

把每个人的移动周期都用f i f_ifi​记录下来（0 ≤ i ≤ n 0 \le i \le n0≤i≤n）。

注意给旗手一个f 0 = 1 f_0 = 1f0​=1，毕竟它前面没有人（题目已经说了）。

Part II.

第二件有意思的事情。

如果前面的人移动一次后超越了我，那么我就直接跟在他后面，即f i = f i − 1 f_i = f_{i-1}fi​=fi−1​。

小 L：如果我慢悠悠地移动咋办呢？

那么前面的人走⌈ d i f i − 1 ⌉ \lceil \frac{d_i}{f_{i-1}} \rceil⌈fi−1​di​​⌉次后我再跑，那么f i = f i − 1 × ⌈ d i f i − 1 ⌉ f_i = f_{i-1} \times \lceil \frac{d_i}{f_{i-1}} \rceilfi​=fi−1​×⌈fi−1​di​​⌉。

其实做到这里状态转移就已经推完了。

总结一下，这个状态转移其实就是

f ( x ) = { f i = f i − 1 ( d i ≤ f i − 1 ) f i = f i − 1 × ⌈ d i f i − 1 ⌉ ( d i ≥ f i − 1 ) f(x)=\left\{ \begin{aligned} f_i & = f_{i-1} & (d_i \le f_{i-1}) \\ f_i & = f_{i-1} \times \lceil \frac{d_i}{f_{i-1}} \rceil & (d_i \ge f_{i-1}) \\ \end{aligned} \right.f(x)=⎩⎨⎧​fi​fi​​=fi−1​=fi−1​×⌈fi−1​di​​⌉​(di​≤fi−1​)(di​≥fi−1​)​

Part III.

不过我们发现f i f_ifi​（0 ≤ i ≤ n 0 \le i \le n0≤i≤n）会有很多是一样的，于是直接把他的左端点记录下来。

小 L：那么怎么处理这些呢？你是不是要一个时间复杂度低一点的算法？

我们发现它们都是倍增的（至少是2 22倍关系），所以可以直接把复杂度降到O ( log ⁡ V ) \mathcal{O}(\log V)O(logV)级别。

然后再和{ l , r } \{l, r\}{l,r}取交集就可以了。

贴两段比较没用的代码。

if(d[i]<=dp[i-1]){dp[i]=dp[i-1];le[i]=le[i-1];}else{dp[i]=((d[i]-1)/dp[i-1]+1)*dp[i-1];le[i]=i;}// 不懂的看上面去 :)

while(pos>=0){intx=t/dp[pos]*dp[pos];ans+=max(0ll,min(r,-1ll*le[pos]+x)-max(l,-1ll*pos+x)+1);pos=le[pos]-1;}

QwQ，绿题拿下！

后记

请勿抄袭题解，违者可能被洛谷棕名哦。