16 青岛
- easy: AB
- medium easy: CDGK
- hard: E
A
签到
B
签到
C
(f(x)) 表示长度为 (x) 木棍的期望，有 (f(x)=frac{int_{a}^{x}f(t)dt}{x})，求一阶线性微分方程即可。
D
考虑每种硬币，我们一直抛硬币直到所有硬币全翻面，那么答案为 (sum_{k} P(此类在恰第 k 轮解体)*P(其它硬币在 k-1 轮结束后全解体))。(P(恰为 k) = P(至少为 k) - P(至少为 k+1))
E
F
G
我们需要最大化边苟住概率之积，以边苟住概率的对数为费用。源点向人连边，桌子向汇点连边，最大费用最大流。注意最短路时精度问题。
K
KD树入门题，但又由于F0_0H太久没写KD树了，导致连估价函数都不会写了....*