小马智行pony.ai 2019校招真题（一）
时长:120分钟 总分:100分
159浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 3 |
1.
车队管理
小马智行(Pony.ai)在广州南沙区有一支稳定运营的自动驾驶车队，可以将南沙区的地图看做一个二维的网格图，小马智行的广州office在(0, 0)位置。
公司现在有n台车，每天会按如下规则从围绕南沙区进行路测：
1. 初始n辆车都在公司。
2. 放眼整个南沙地图，每过一分钟， 若有一个网格的车数大于等于8， 则这个网格同时会有8辆车分别前往上，下，左，右，左上，左下，右上，右下的网格，不停执行该步骤直到所有的车辆的位置都固定不变。
作为小马智行车辆控制中心的一员， 你需要监管车辆运营的情况， 你需要等到所有车辆的位置固定之后，进行q次抽样统计， 每次需要统计出以
为左下角，以
为右上角的矩形范围内车辆的车辆的数目。
公司现在有n台车，每天会按如下规则从围绕南沙区进行路测：
1. 初始n辆车都在公司。
2. 放眼整个南沙地图，每过一分钟， 若有一个网格的车数大于等于8， 则这个网格同时会有8辆车分别前往上，下，左，右，左上，左下，右上，右下的网格，不停执行该步骤直到所有的车辆的位置都固定不变。
作为小马智行车辆控制中心的一员， 你需要监管车辆运营的情况， 你需要等到所有车辆的位置固定之后，进行q次抽样统计， 每次需要统计出以
为左下角，以为右上角的矩形范围内车辆的车辆的数目。 第一行为n和q， 分别代表初始office内的车辆数和抽样的次数。
之后q行，每行包含4个变量
, 
, 
, 
含义见题目描述。
, , , 含义见题目描述。
后， 进行q次抽样，每次查询以
为左下角，以
为右上角的矩形范围内车辆的数目。
2.
车辆安排
目前小马智行已经获得了加州RoboTaxi服务的许可，意味着小马智行已经可以在加州向所有的公众提供服务。
于是在未来的某一天，小马智行在加州已经拥有了N辆自动驾驶车辆可以面向公众服务，这些车总共有26种颜色，颜色分别为小写字母a到z。现在已知在Pony的服务系统PonyPilot中，总共有M个乘客正在排队，其中每个乘客也有各自的车辆颜色偏好,颜色范围也是a到z。
现在运营小P突然有了一个奇怪的想法：小P想知道总共有多少个位置连续的子队列，能够满足现有的所有车辆可以在同一时刻把子队列中的乘客同时接上乘客喜爱的颜色的车。注意每个车辆只能接一个乘客，且车的颜色要恰好是乘客喜欢的颜色。
输入描述：
第一行输入两个数字N，M。N代表车辆数，M代表乘客人数。
第二行输入一个字符串A，长度为N，表示每辆车的颜色。
第三行输入一个字符串B，长度为M，表示当前排队的乘客分别喜欢的车的颜色。
其中，1<=N<=1000000, 1<=M<=1000000。输入样例： 4 6 pony pponyy 输出描述： 输出一个数，即总共满足要求的子队列数。输出样例 12
于是在未来的某一天，小马智行在加州已经拥有了N辆自动驾驶车辆可以面向公众服务，这些车总共有26种颜色，颜色分别为小写字母a到z。现在已知在Pony的服务系统PonyPilot中，总共有M个乘客正在排队，其中每个乘客也有各自的车辆颜色偏好,颜色范围也是a到z。
现在运营小P突然有了一个奇怪的想法：小P想知道总共有多少个位置连续的子队列，能够满足现有的所有车辆可以在同一时刻把子队列中的乘客同时接上乘客喜爱的颜色的车。注意每个车辆只能接一个乘客，且车的颜色要恰好是乘客喜欢的颜色。
第二行输入一个字符串A，长度为N，表示每辆车的颜色。
第三行输入一个字符串B，长度为M，表示当前排队的乘客分别喜欢的车的颜色。
其中，1<=N<=1000000, 1<=M<=1000000。输入样例： 4 6 pony pponyy 输出描述： 输出一个数，即总共满足要求的子队列数。输出样例 12
3.
路径规划
路径规划对于自动驾驶来说是非常重要的一环，它决定了自动驾驶的车辆如何在道路上行驶。现在给出一个城市的地图，请规划出最快从起点到达终点的路线。 地图中的路都平行于X轴或Y轴，所有的路是双向通行的。路与路的交叉点有交通灯限制通行，所有的交通灯都是统一周期控制的。
交通灯共有三种不同的状态。第一种是只能右转，维持T1秒；第二种是可以直行左转和右转，维持T2秒；第三种是只能直行和右转，维持T3秒。
三种状态按顺序交替循环，即[0, T1), [T1 + T2 + T3, 2T1 + T2 + T3), [2T1 + 2T2 + 2T3, 3T1 + 2T2 + 2T3)时只能右转，[T1, T1 + T2), [2T1 + T2 + T3, 2T1 + 2T2 + T3), [3T1 + 2T2 + 2T3, 3T1 + 3T2 + 2T3)时可以直行左转和右转，[T1 + T2, T1 + T2 + T3), [2T1 + 2T2 + T3, 2T1 + 2T2 + 2T3), [3T1 + 3T2 + 2T3, 3T1 + 3T2 + 3T3)时可以直行和右转，如此类推。
路的中间和路口都无法掉头。假设车的速度为1单位长度/s，在起点处车可以自己选择启动的方向，给出起点和终点的坐标，问从起点开到终点最少需要的时间。
输入描述：
第一行输入道路的条数N。然后N行，每行4个整数X1 Y1 X2 Y2，表示每条道路两个端点的坐标。输入保证每条道路平行于X轴或Y轴，每条路的长度都大于0,，道路之间不会有长度大于0的重合。
然后一行4个整数SX SY TX TY，表示起点和终点的坐标。保证起点和终点位于道路上。
最后一行3个整数T0 T1 T2，表示交通灯三种状态的持续时间。输入样例： 2 0 2 4 2 2 0 2 4 1 2 2 1 1 1 1 输出描述： 输出到达终点的最少时间。数据保证可以从起点走到终点。输出样例 2
