2018 Multi-University, HDU Day 7

Problem A

Solved by kblack. 01:47 (+2)

题意：给一个边上带颜色的无向图，走的边颜色变化一次花 1，求最短路。

题解：边上加个点，到两个端点距离为 1，一个点出去的同色边缩一下，因为距离都是 1，跑 bfs 就好了，卡常。。。

Problem B

Solved by ultmaster. 04:56 (+4)

Problem D

Upsolved by kblack. (-2)

题意：$n$ 辆公交车，均匀概率地在一个时间点前到，如果 $T_i$ 还没到，就走路，公交车时间 $a$ 保证小于走路时间 $b$，求期望到家时间。

题解：两个部分，设 T 为最后等待的时间，最后走路的概率 $p = \sum_{i=1}^{n}{(1-\frac{min(L_i, T)}{m})}$，则假设公交也最后才开的期望时间为 $p \times (b+T) + (1-p) \times (a+T)$，然后减去公交车之前开的概率，这部分是$ \int_0^T {1-\prod_{i=1}^{n}(1-\frac{min(L_i, t)}{m})} dt$，这个要积的玩意儿是分段函数，最多分 $n$ 段，正确积分即可。

Problem E

Solved by ultmaster. 00:57 (+1)

Problem H

Solved by ultmaster. 01:41 (+)

Problem I

Solved by zerol. 01:26 (+1)

Problem J

Solved by kblack. 00:43 (+1)

题意：$\left\{\begin{eqnarray*} F_1 &=& A \\ F_2 &=& B \\ F_n &=& C\cdot{}F_{n-2}+D\cdot{}F_{n-1}+\left\lfloor\frac{P}{n}\right\rfloor \end{eqnarray*}\right.$ 给定 A, B, C, D, P, n 求 $F_n$。

题解：$\lfloor{\frac{P}{n}}\rfloor$ 只有 $\sqrt{P}$ 种，分段快速幂就好了，注意分段的间隔。

Problem K

Solved by zerol. 02:04 (+)