首页 > 其他分享 >题解:AT_abc204_e [ABC204E] Rush Hour 2

题解:AT_abc204_e [ABC204E] Rush Hour 2

时间:2024-09-25 16:23:12浏览次数:11  
标签:abc204 Rush 函数 Hour 题解 ABC204E

变形的 dijkstra。

先思考什么情况下需要等待以及等待多长时间最优。我们把题目上的计算方法按照当前的时间 \(t\) 和通过所需的时间 \(f(t)\) 列个函数关系:

\[f(t)=t+c+\lfloor \frac{d}{t+1}\rfloor \]

然后用 Desmos 画个图可以得到图像(其实就是对勾函数):

image

因为 \(c,d\geq 0\),所以我们只考虑上半部分。容易发现这个函数是有最值的,根据高一数学知识可得此时 \(t=\sqrt{d}-1\)。

于是我们得到初步结论:跑最短路的时候比较当前时间和上面求出来的东西,如果当前时间已经在其之后,那么根据图象发现等待是不优的,所以正常转移。否则我们直接等到出现最小值的时刻再走就行了。

因为涉及到浮点数运算,所以需要注意精度问题。

一开始的时候发现无解判错了,怎么改都改不过,于是写了个并查集(我好菜)。

提交记录

标签:abc204,Rush,函数,Hour,题解,ABC204E
From: https://www.cnblogs.com/Lydic/p/18431590

相关文章

  • [湖北省选模拟 2023] 棋圣 / alphago 题解
    很牛的题目啊。-Alex_Wei发现这个操作比较复杂但限制较弱,考虑通过考察“不变的量”来刻画操作。容易发现若为二分图,则初始颜色不同的一定不能移动到一起。又因为在存在环的图上这个限制很弱/目前较难考虑,所以先考虑树的情况,发现答案存在可能取到的上界,令\(c_{i,j}\)为初......
  • CF1119H Triple 题解
    DescriptionSK酱送给你了一份生日礼物。礼物是\(n\)个三元组\((a_i,b_i,c_i)\)和四个正整数\(x,y,z,k\)。你利用这\(n\)个三元组填充了\(n\)个数组,其中第\(i\)个数组中有\(x\)个\(a_i\),\(y\)个\(b_i\),\(z\)个\(c_i\)(所以第\(i\)个数组长度为\((x+y+z)\)。......
  • Codeforces Round 974 (Div. 3)题解记录
    A.RobinHelps签到模拟,遍历一遍即可,注意没钱时不给钱。\(O(n)\)#include<iostream>#include<set>#include<map>#include<vector>#include<algorithm>#include<bitset>#include<math.h>#include<string>#include<string.h>#......
  • [ARC122E] Increasing LCMs 题解
    感觉像比较套路的构造题。思路假如我们正着进行构造,可以发现我们加入一个数以后,对后面的数产生的影响是很大的。但是如果我们从最后一个数开始构造,那么可以发现它是不会对之后的构造产生任何影响的。应为越前面的数的限制会越少,那么可以填的数一定是不减的。一个数可以填在后......
  • 算法题之图论 [NOIP2001 提高组] Car的旅行路线详细题解
    P1027[NOIP2001提高组]Car的旅行路线这道题的思路呢,就是建个图,然后跑一遍Floyd,比较最小值就可以解决了。but!它每个城市只给三个点(共四个),所以还得计算出第四个点坐标。这里根据矩形的中点公式来表示未知点的坐标:(这个思路源于大佬 _jimmywang_       ......
  • [ARC121E] Directed Tree 题解
    简单容斥题。思路题面的条件相当于一个位置上填的点不能是自己的祖先。发现直接做并不好做。考虑容斥。我们想要求出\(f_i\)为至少有\(i\)个不合法位置的方案数。那么答案为:\[\sum_{i=0}^nf_i(-1)^i\]如何求解。设\(f_{i,j}\)为\(i\)子树下有\(j\)个不合法位......
  • 2024-2025专题一题单 - 题解
    A-Virus原题链接题解B-Coverage原题链接题解C-Sensors原题链接题解D-MakeTakahashiHappy原题链接题解E-Don’tbecycle原题链接题解F-AlmostEqual原题链接题解G-StepUpRobot原题链接题解H-SnukeMaze原题链接题解I-MEX原题链接......
  • P5329 [SNOI2019] 字符串 题解
    Description给出一个长度为\(n\)的由小写字母组成的字符串\(a\),设其中第\(i\)个字符为\(a_i\(1\leqi\leqn)\)。设删掉第\(i\)个字符之后得到的字符串为\(s_i\),请按照字典序对\(s_1,s_2,……,s_n\)从小到大排序。若两个字符串相等,则认为编号小的字符串字典序更小。......
  • CF164D Minimum Diameter 题解
    最小点覆盖模板题。思路考虑二分直径\(x\)。我们将距离\(>x\)的点对连一条边,那么每一条边的两端至少有一端需要被删掉。这是最小点覆盖的定义。那么就是判断最小点覆盖是否小于等于\(k\)。发现这个问题并不好用一些多项式复杂度的做法解决。考虑暴搜。每一次我们把度......
  • CF2003F Turtle and Three Sequences 题解
    个人觉得*2800有点虚高。如果做过类似的题(比如[THUSCH2017]巧克力),应该可以想到随机映射,状压dp也不难想。实际上,看到要选出\(m\)种不同的颜色,且\(m\le5\)就可以想到将每种颜色随机映射到\(1\)到\(m\)中,这样子得出来的答案不会更优,而当答案选择的\(m\)种颜色恰好......