牛客算法周周练1

A - Maximize The Beautiful Value

定义 $sum(l, r) = \sum\limits_{i=l}^{r} a[i]$
定义 $init = F(n) = \sum\limits_{i=1}^{n} i \cdot a[i]$
若将 $a[i]$ 向前移动 $j$ 位，那么新的答案 $res_{i,j} = init - j \cdot{a[i]} + sum(i - j, i - 1)$
若将 $a[i]$ 向前移动 $j+1$ 位，那么新的答案 $res_{i,j+1} = init - (j + 1) \cdot{a[i]} + sum(i - (j + 1), i - 1)$
故有 $res_{i, j + 1} - res_{i, j} = a[i - (j + 1)] - a[i]$
因为题目中规定 $\forall{i} \in [1, n - 1], a[i] \leq a[i + 1]$ ，可知 $a[i-(j+1)] \leq a[i]$ ，故 $res_{i, j + 1} - res_{i, j} \leq 0$
也就是说，对于任意的 $i$ ，它向前移动的步数越少，所得到的结果越优；所以只需要枚举 $i(k + 1 \leq i \leq n)$ ，计算 $a[i]$ 向前移动 $k$ 步的结果并取max即可。

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

B - 身体训练

定义 $t_{i, j}$ 为第 $i$ 个人排第 $j$ 位时，从最后一位跑到第一位需要的时间
那么有 $t_{i, j} = \frac{u \cdot n}{(c[i] - (j - 1) \cdot{d[i]}) - v}$
一共有 $(n-1)!$ 个排列使得第 $i$ 个人排在第 $j$ 位，即第 $i$ 个人排在第 $j$ 位的概率为 $\frac{(n-1)!}{n!} = \frac{1}{n}$
所以 $res = \frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n} t_{i, j}$

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

C - Borrow Classroom

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

定义 $Path(x, y)$ 为点 $x$ 到点 $y$ 的路径。
定义 $dis(x, y)$ 为点 $x$ 到点 $y$ 的距离。

若何老师能截住SK：
何老师走的路径为 $Path(A, C)$ ，SK走的路径为 $Path(B, C)$ ，设点 $D$ 为这两条路径的交点。
点D示例
那么，必有 $dis(A, D) \leq dis(B, D)$ ，因为两人的速度相同，若何老师在点 $D$ 无法截住SK，那么之后也截不住。

若何老师能截住小Q：
何老师走的路径为 $Path(A, 1)$ ，小Q走的路径为 $Path(C, 1)$ ，设点 $D$ 为这两条路径的交点。
若 $D = 1$ ，则必有 $dis(A, 1) < dis(C, 1) + dis(B, C)$ ；
若 $D \neq 1$ ，则必有 $dis(A, D) \leq dis(C, D) + dis(B, C)$

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

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

D - 景区路线规划

定义 $dp[u][t]$ 表示当前游览完点 $u$ ，剩余时间 $t$ ，继续游览能获得的开心度的期望。
若有 $x$ 个点与点 $u$ 相邻、游览时间+距离不超过 $t$ ，那么 $dp[u][t] = \frac{1}{x}\sum{(dp[v][t - dis(u, v) - c[v]] + h[v])}$ (这里 $v$ 为满足条件的点、 $dis(u, v)$ 为 $u$ 到 $v$ 的距离)。

设一超级源点 $s$ ，对 $1$ ~ $n$ 所有点连一条有向边 $<s, i>$ ，边权设为 $0$ ，然后记忆化搜索即可。

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

E - 幸运数字Ⅱ

直接暴力打表(只需要打出 $2^{9} + 2^{8} + ... + 2 + 1 = 1023$ 项即可)，然后利用表进行计算即可。

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