题解：P13386 [GCJ 2011 Finals] Google Royale

🧭：遇到赌博类游戏的时候考虑分析这个游戏是否是“公平的”，也就是说，期望会如何变化。

🧭：找到一个在所有合法转移下期望不变的势函数；如果边界值已知，那么初始势函数值就是最终胜率。公平一维游走里，这个势函数就是位置本身，所以胜率是距离比例。

首先注意到本题的操作是一次移动可以选择整数 $k,B$ 满足 $k\geq 1,1\leq B\leq \min(x,V-x),2^{k-1}B\leq M$，随后会以 $\frac{2^k-1}{2^k}$ 的概率移动 $B$，以 $\frac{1}{2^k}$ 的概率移动 $-(2^k-1)B$。这个操作是不改变期望的！也就是说，这个游戏是公平的，因为最后一步一定会恰好走到 $V$，所以希望胜率最高和希望期望输的最惨等价（设期望输到 $L$，胜率为 $p$，有 $p=1-\frac{V-A}{A-L}$，所以希望输的惨。

那么我们接下来的目标就是让自己失败的尽可能靠左。考虑找到一组合法的最大的 $B-(2^k-1)B$，这就是能到达的最左位置！我们使用策略：

1. 当 $x>B$ 时等概率移动 $1$。

2. 当 $x=B$ 时直接移动 $k$

这种策略就可以在 $A\geq B$ 时到达期望死亡位置的理论最小值，我们已知死亡位置，胜率也就被确定了。

当 $x<B$ 时，直观上来讲，我们的策略就变成了尽可能先走到 $B$，递归下去处理即可。我们接下来证明这个直观感受：

• 如果我们的第一步是走到了某个 $<B$ 的点，那么这被囊括在了走到 $B$ 的决策中，一定不劣。
• 否则，分析一下胜率可以发现跳到 $>B$ 的位置对最劣点带来的期望收益为 $0$。

故递归下去即可。