本文主要是介绍（CSP2019模拟）DTOJ 4644. speike，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
众所周知，Speike 狗是一条特别喜欢追着Tom 打的狗。
现在，Tom 又把Speike 惹生气了，现在Speike 需要跨越千山万水找Tom 报仇。
Speike 所在的世界可以看成是一个无穷大的平面，平面由一个平面直角坐标系确定。在平面上有许多不相交的矩形障碍，矩形的四边平行于坐标轴。
Speike 需要从 ( 0 , 0 ) (0,0) (0,0) 出发，在尽量短的时间内跑到 ( X t , 0 ) (X_t,0) (Xt,0)，也就是Tom 在的位置。
出题人规定，Speike 只能沿着平行于坐标轴的方向运动，且不能进入矩形障碍的内部，但是可以在障碍边界上移动。
所有障碍的横坐标都在 [ 0 , X t ] [0,X_t] [0,Xt] 之内。保证矩形不相交(即没有公共面积)，也不会退化成线段或者点。
Speike 的智商不是很高，因此他需要你帮忙设计一条最短的路线。当然，你只需要告诉他路线的长度就行了。
| 测试点编号 | n的范围 | 特殊性质 |
|---|---|---|
| 1 | n ≤ 0 n \le 0 n≤0 | 无 |
| 2,3 | n ≤ 1 n \le 1 n≤1 | 无 |
| 4,5,6 | n ≤ 20 n \le 20 n≤20 | a , b , c , d , X t ∈ [ − 1 0 3 , 1 0 3 ] a, b, c, d, X_{t} \in\left[-10^{3}, 10^{3}\right] a,b,c,d,Xt∈[−103,103] |
| 7,8,9,10 | n ≤ 200 n \le 200 n≤200 | a , b , c , d , X t ∈ [ − 1 0 5 , 1 0 5 ] a, b, c, d, X_{t} \in\left[-10^{5}, 10^{5}\right] a,b,c,d,Xt∈[−105,105] |
| 11,12,13 | n ≤ 2000 n \le 2000 n≤2000 | a , b , c , d , X t ∈ [ − 1 0 3 , 1 0 3 ] a, b, c, d, X_{t} \in\left[-10^{3}, 10^{3}\right] a,b,c,d,Xt∈[−103,103] |
| 14,15 | n ≤ 2000 n \le 2000 n≤2000 | 无 |
| 16,17 | n ≤ 1 0 5 n \le 10^5 n≤105 | 所有矩形都与 x x x轴相交 |
| 18,19,20 | n ≤ 5 × 1 0 5 n \le 5 \times 10^5 n≤5×105 | n n n有一定梯度 |
− 1 0 8 ≤ a , c ≤ X t ≤ 1 0 8 , − 1 0 8 ≤ b , d ≤ 1 0 8 , n ∈ [ 0 , 1 0 5 ] -10^{8} \leq a, c \leq X_{t} \leq 10^{8},-10^{8} \leq b, d \leq 10^{8}, n \in\left[0,10^{5}\right] −108≤a,c≤Xt≤108,−108≤b,d≤108,n∈[0,105]。
保证矩形不相交(即没有公共面积)，每个矩形不会退化成线段或者点，且横坐标都在 [ 0 , X t ] [0,X_t] [0,Xt] 之内。
题解
考场：
最后一个半小时对着这道题自闭毫无想法（完全没有发挥出前两题写得比较顺利的优势），感觉碰到这种坐标上的题就脑壳疼，最后只打了直接坐标系上建图的最短路。
正解：
slzAK，xjq在最后15分钟打出75分暴力，这就是神犇们与蒟蒻之间的差距吧。
注意到矩形不相交且可以经过边界（一开始还一直忘记这两点），感性地觉得只有矩形的顶点是有用的，即路径只会在矩形顶点处拐弯且只会向右，于是可以对矩形顶点之间暴力连边跑最短路就有75分了。
再考虑一下从起点走到终点的过程：若没有与x轴相交的矩形则直接走，否则在与x轴有交的所有左边界中，最右端的那个一定是最后一个到达的边界，因为在那之后就可以直接沿着坐标轴方向到达终点。这样又注意到只有左边界是有用的，以此类推，对于每个左边界的端点也是由它前面最后纵坐标一个包含它的边界转移过来，记 f [ i ] [ 0 / 1 ] f[i][0/1] f[i][0/1]为到达第i个边界的上/下端的最短路，用线段树维护即可。
这篇关于（CSP2019模拟）DTOJ 4644. speike的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
