CCPC 2021 湘潭全国邀请赛 D-Car 题解

2021-11-05 21:56 作者:昵称不能为空voidf 0人读过 | 我要投稿

现场没开，按主办方说法是铜牌题莫名其妙变成金牌题，深感自己化式子能力不足

补题链接：https://acm.hdu.edu.cn/showproblem.php?pid=6941

题目大意：车车（视为点）在一条长为L的长直公路上行驶，一开始没有任何测速点，规定从起点起步时速度为0，到达终点时速度必须为0，车车的加速度绝对值不能超过A，接下来有N个测速点依次建立：

每个测速点以(S, V)的二元组整数形式给出，表示测速点建立在离起点S处，限速为V
车车通过每个测速点时不得超过测速点规定的速度

对于每个测速点的建立，您需要回答建成后会不会影响车车从起点到终点的消耗的最短时间。影响输出1，否则输出0

官方题解：

因为过于简略，自己补题的时候踩了很多坑……

先证明一下题解给的结论，由于我不会化式子，这里采用画图证明。

考虑在两个测速点之间行驶，不失一般性，设v1为离起点更近的测速点的限速，令v1>v2，如果飚满A的加速度，v-t图大概长这样：

其中分界点两侧直线关于分界点到x轴的投影线对称，由v-t图的性质我们知道图下黑色部分的面积就是两个测速点之间的距离。由于测速点距离一定，每个合法方案这样画出来的投影面积必须等于当前黑块的面积。我们将两个测速点连线作三角形(v1, v2, 分界点)的底，黑色部分被分为一个梯形和这个三角形。

在分界点上作关于直线(v1, v2)的投影，我们得到了这个三角形的高。现在我们考虑改变直线(v1, 分界点)的斜率，在前半段加速阶段不违反速度限制的题设下，如图

为了方便我们仍考虑匀速直线运动，画出蓝线后分析一下这个图的意义：如果我们另前半段加速度减缓，后半段减速的加速度变快的话，可以作出这样一个距离与黑色部分面积一致的行驶方案，但是注意后半段因为加速度绝对值已经超过上限，所以这样一个方案是不可行的，为了让时间消耗变小我们只能让后半段的匀减速阶段尽可能靠近上限A，这样为了构造一个距离（面积）等于三角形(v1, v2, 分界点)的三角形，只能如图所示做一个第3顶点不与平移至分界点的底线相交的三角形：

然后你发现此时蓝线的末端在x坐标上已经超过v2点，即这种方案耗时更久。

对于非匀加速直线运动的画法，作图发现为了让其面积满足需求，必须有一块面积补充其前期因为低于分界点产生的代价，使得右端点x坐标大于v2点：

想要让时间更短的话就只能把这些多的面积尽可能往前面堆，而堆到极限就是我们最初画出来两侧直线对称的方案。于是结论证毕。

现在开始考虑题目：如何判断一个测速点是否影响当前最优时间？

还是从图上看，当一个点入侵了前面那个画法作出来的三角形的时候，最优行驶方案就需要根据这个测速点进行调整了：

当然如果当前测速点没有入侵任何一段这样的图形，那么就说这个测速点无效，输出0，并且什么都不做。

现在考虑两个问题：

如何维护这样的一系列图形，使得复杂度正确？
题目给的测速点是(S, V)，怎么拿到它在v-t图上的位置？

对于第一个问题，其实我们发现只需要维护关键测速点关于距离的序列，每次新加入一个测速点只需要二分就能得到它受哪一段制约，这样就能保证复杂度正确。实现可以按官方题解说的用一个map来维护。

对于第二个问题，本人的思路巨略复杂，开始化式子：

式子中只有t1和t2是未知的，联立距离公式和速度公式，化简后解出关于t1的一元二次方程：

先搬一个解二元一次方程的轮子：

解这个方程，可以得到分界点的位置，这样我们可以得到一个分段函数，对于区间[x1, x2]，我们先判断S在分界点的哪一侧，然后用匀加速度位移公式： $v_1t%2B%5Cfrac%7B1%7D%7B2%7DAt%5E2%3DS$ 解出车车到S这点需要的时间，然后可以算出原图中在这点的速度。如果这个速度要小于等于新建限速点规定的速度，那么就可以输出0啦。