838
CodeForces 838D Airplane Arrangements
洛谷传送门 CF 传送门 考虑加入第 \(n + 1\) 个位置,这样座位构成了一个环。每个位置被覆盖的概率相等,为 \(\frac{m}{n + 1}\),然后算出概率再乘方案数就行了。 code // Problem: D. Airplane Arrangements // Contest: C ......
CF838D Airplane Arrangements 题解
## 题意 一架飞机有 $n$ 个座位排成一列,有 $m$ 名乘客($m \leq n$)依次上飞机。 乘客会选择一个目标座位(两人可以选同一个目标座位),然后选择从前门或者后门上飞机,上飞机后,他们会走到自己的目标座位,如果目标座位已经有人坐了,他们会继续往前走,在走到第一个空位后坐下。如果走到最 ......
CF838B Diverging Directions
好像挺神奇的,也可能是我菜。 以下称前 $n-1$ 条边为「树边」,因为它们组成一棵树;后 $n-1$ 条边为「回边」,因为它们由树节点回到根。 就是对于一个询问,如果 $v$ 在 $u$ 的子树内,发现无论如何答案都要包括 $u\to v$ 的只经过树边的路径。那么只走这条路径一定是最优的,直接维 ......