正文

【Codeforces 98E】 Help Shrek and Donkey 游戏策略神题

IP云
IP云V管理员/6 阅读
09/28
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

from http://www.cnblogs.com/MashiroSky/p/6576398.html

A君有n张牌，B君有m张牌，桌上还有一张反扣着的牌，每张牌都不一样。

每个回合可以做两件事中的一件

  • 猜测桌上的牌是什么，猜对则胜，猜败则输。
  • 询问对方是否有某张牌，若有则需要将其示出，否则继续游戏。

A和B都很聪明，问A的胜率。

Solution

首先不到最后一刻是不会选择猜桌上的牌的。

假如某一次对方问了一张自己手上没有的牌，就可能会怀疑桌上的牌就是这张。

而询问对方是否有某张牌，我们可以选择询问自己手上有的牌，假如对方相信而去猜测这张牌的话就会输掉，我们称这样的行为作欺骗。

记f(n,m)f(n,m)表示先手有nn张牌，后手有mm张牌，先手的获胜概率。

那么就可以列一个表格，表示先手的选择以及后手的应对。

  • 先手选择猜测对方的牌

    • 后手认为先手在猜测，先手获胜的概率是mm+1(1−f(m−1,n))mm+1(1−f(m−1,n))
    • 后手认为先手在欺骗，先手获胜的概率是1m+1+mm+1(1−f(m−1,n))1m+1+mm+1(1−f(m−1,n))

  • 先手选择欺骗

    • 后手认为先手在猜测，先手获胜的概率是11
    • 后手认为先手在欺骗，先手获胜的概率是1−f(m,n−1)1−f(m,n−1)

那么对于先手的任意一个策略，后手会选择最优的策略去使他赢的概率尽可能小。也就是说假如先手用pp的概率选择去猜测，1−p1−p的概率选择去欺骗。那么最终的贡献就是

maxp{min{pmm+1(1−f(m−1,n))+(1−p),pm+1+pmm+1(1−f(m−1,n))+(1−p)(1−f(m,n−1))}}maxp{min{pmm+1(1−f(m−1,n))+(1−p),pm+1+pmm+1(1−f(m−1,n))+(1−p)(1−f(m,n−1))}}

将pp视为自变量，问题就转化为两条直线取minmin的问题，求个交点就可以得到最大值。

细节

直线的交点别求错了。。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++

首先这个思路不太好想

其次在状态转移时，注意先手是可以两种决策随便选，故存在概率；而后手决策无非两种

脑补一下是这样的把。。