纳什均衡-神仙博弈论-CF98E-解题报告

· · 题解

首先一个性质：当n,m\ge 1时，不会有人莽猜。我看其他题解都认为这很显然，我还是说一下原因吧：

如果我们直接猜，那么1/(m+1)胜利，其余失败

如果我们猜对方手中自己没有的牌，那么1/(m+1)胜利，其余还可以知道对方的一张牌

所以我们肯定优先问对方。

这道题神仙就神仙在询问还可以欺骗（问对方自己有的），对方可以选择相信还是不相信。

我们肯定是用DP解决。f(n,m)表示先手n张牌，后手m张牌的先手胜率。

我们用第一个T/F表示询问还是欺骗，第二个T/F表示对方是否相信。可得如下递推式：

\begin{aligned}&TT=m/(m+1)(1-f(m-1,n))\\&TF=1/(m+1)+m/(m+1)(1-f(m-1,n))\\&FT=1\\&FF=1-f(m,n-1)\end{aligned}

我们假设先手选择询问的概率是p，那么后手肯定在相信还是不相信中取先手胜率最小的，也就是：

\begin{aligned}\max_{p}(\min(&\frac m{m+1}(1-f(m-1,n))\times p+(1-p),\\&(\frac m{m+1}(1-f(m-1,n))+\frac 1{m+1})\times p+(1-f(m,n-1))\times(1-p))))\end{aligned}

这是两条直线。当且仅当取交点时，min最大。

double dp(int n,int m)
{
    if(!m) return 1;
    if(!n) return 1.0/(m+1);
    double &r=f[n][m];
    if(r>-1) return r;
    double k0=(1-dp(m-1,n))*m/(m+1)-1,b0=1;
    double k1=((1-dp(m-1,n))*m+1)/(m+1)-(1-dp(m,n-1)),b1=1-dp(m,n-1);
    r=(b1-b0)/(k0-k1);
    return r=k0*r+b0;
}