本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-10-07 10:38:22

Mighty Rock Tower

题意：一个石子堆，初始为空，每次操作可以放上一枚石子。设当前石子的数量是 $x$，那么这一轮有 $P_x$ 的概率一个石子掉落（石子掉落后 $x$ 仍不变）。求石子堆到 $n$ 个的期望步数。

设 $f_i$ 表示由 $i - 1$ 个石子堆到第 $i$ 个的期望步数。考虑从第 $i - 1$ 个石子堆上后发生了什么。

一种可能是全掉完了。概率是 $P_i^i$，代价是 $\sum\limits_{j=1}^i f_j$；

另一种可能是掉到某一个 $j$ 就不再掉，概率是 $P_i^{i-j} (1 - P_i)$，代价是 $\sum\limits_{k=j+1}^i f_j$。这里 $j\in [1, i]$。

还有根本没有掉的，但是根本没有贡献。

这个式子拆开 $1 - P_i$ 项化简，可以得到一个 $O(N)$ 转移。由于 $P_i$ 只有 $100$ 种，因此可以对每一种 $P_i$ 前缀优化。最终复杂度是 $O(n\max P)$。

Game on Sum (Hard Version)

先看 Subtask 1。设 $f(i, j)$ 表示 Bob 已经进行了 $i$ 轮，已经选择了 $j$ 轮加法，最后的值。

现在我们不知道 Alice 会选什么。但是设她会选 $t$，那么

$$ f(i, j) = \min (f(i - 1, j) - t, f(i - 1, j - 1) + t) $$

Bob 会让答案尽可能小，所以外面套一个 $\min$。这个式子显然是在取到均值的时候最大，因此 Alice 会取这两个转移路径的均值。于是我们得到

$$ f(i, j) = \dfrac {f(i - 1, j) + f(i - 1, j - 1)} 2 $$

边界是 $j = 0$ 和 $i = j$。$j = 0$ 时，Bob 全都选减法，因此 Alice 全给 $0$。$j = i$ 时，Bob 全选加法，因此 Alice 全给 $k$。

对于 Subtask 2，考虑每个位置对 $f(n, m)$ 的贡献。能贡献的位置只有 $f(i, i) = ki$，贡献路径是 $(i, j) \rightarrow (i + 1, j), (i + 1, j + 1)$，也就是竖着或者斜着走，方案数是 $n - i - 1\choose m - j$。贡献是多少？一开始的贡献是 $ki$，随着往下走一行，会除以一个二。一共走 $n - i$ 行，因此除以 $2^{n-i}$。

所以最后的答案是

$$ \sum\limits_{x=1}^{n-1} \dfrac{{n-x-1\choose m-j} kx}{2^{n-x}} $$

比较奇妙。