牛客算法周周练1

A - Maximize The Beautiful Value

定义
定义
若将向前移动位，那么新的答案
若将向前移动位，那么新的答案
故有
因为题目中规定，可知，故
也就是说，对于任意的，它向前移动的步数越少，所得到的结果越优；所以只需要枚举，计算向前移动步的结果并取max即可。

Code:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43375997

B - 身体训练

定义为第个人排第位时，从最后一位跑到第一位需要的时间
那么有
一共有个排列使得第个人排在第位，即第个人排在第位的概率为
所以

Code:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43376128

C - Borrow Classroom

显然，何老师要么在SK去找小Q的路上截住SK，要么在小Q去教务处的路上截住小Q。
那么怎么判断何老师能否截住呢？

定义为点到点的路径。
定义为点到点的距离。

若何老师能截住SK：
何老师走的路径为，SK走的路径为，设点为这两条路径的交点。

那么，必有，因为两人的速度相同，若何老师在点无法截住SK，那么之后也截不住。


若何老师能截住小Q：
何老师走的路径为，小Q走的路径为，设点为这两条路径的交点。
若，则必有；
若，则必有

那么如何找点呢？实际上，对于与，它们的交点必定是、、中深度最大的一个，所以只要求几次即可。

Code: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43376570

D - 景区路线规划

定义表示当前游览完点，剩余时间，继续游览能获得的开心度的期望。
若有个点与点相邻、游览时间+距离不超过，那么(这里为满足条件的点、为到的距离)。

设一超级源点，对~所有点连一条有向边，边权设为，然后记忆化搜索即可。

Code: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43380072

E - 幸运数字Ⅱ

直接暴力打表(只需要打出项即可)，然后利用表进行计算即可。

Code：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43375801