NFLSPC #2 Game 题解

2019-11-29 16:51:32 By wzy

引理:两人若都采取最优操作方案,那么 Alice 的胜率等价于所有格子等概率随机颜色后,左边和右边连通的概率。

证明:

如果 Alice 在一个回合前知道 Bob 将会走哪个格子,那么假设他当前的策略也选这个格子,这样至少能够达到引理中胜利的概率,即所有格子颜色随机上下连通的概率。

同理,对于 Bob 来说也能够使用此策略达到“所有格子颜色随机左右连通的概率”的胜率。

因此考虑令 $x$ 为最终的期望得分,从 Alice 来看,$x \ge E($格子随机分配$)$,从 Bob 来看,$x \le E($格子随机分配$)$,因此 $x=E($格子随机分配$)$。

因此只需要计算所有格子颜色随机时,上下连通和左右连通的概率,插头 dp 即可。

评论

avatar
newbieyzr
没有看懂证明(的第一句话)QAQ

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。