题解 P2059 【[JLOI2013]卡牌游戏】

· · 题解

2018-10-24 更新

思路

与先前写题解的大佬们略有不同，我觉得可能更好理解一些。

如果有情况A有 m 的概率发生，且它有 n 的概率直接转换情况B，那么情况B发生的概率可加上 m×n。

概率可以层层（一层指的是淘汰一次）继承，可以考虑用DP。

这道题直觉是顺序递推，第一个人有 \frac{1}{m} 的几率选择某一张牌，所以下一个状态出现的概率为 \frac{1}{m}。但是下一个状态很古怪，因为这个状态除了包括概率值，还包括“谁被淘汰了”，后者也会影响接下来的淘汰结果。仔细考虑发现不好实现。

最好有一种继承方式不需要保留“谁被淘汰”这个状态。那就是倒序递推，从环内人数只有1的状态开始。

模拟一下样例1。现在卡牌是给定了，上面写着2，3，5，7，11。

当环内只有一个人时（没人钦定这是谁），这个人已经赢了，赋胜率100%。

考虑环内有两个人的情况（这也是不指定的两人）。这时的庄家可以从5张牌中任意选一个，每张牌被选中的概率都是 \frac{1}{5}。

如果选2。淘汰对方，自己胜利。

如果选3，5，7，11中的一张牌，可算出他淘汰了自己，留下了第二个人。

可见，余留两个人时，庄家胜率20%，坐在他后面的人胜率80%。

暂时看不出什么端倪。其实，“还剩两人”的状态对于解决“还剩三人”特别有利。

考虑环内有三个人的情况。

庄家 \frac{1}{5} 几率选2。结果是第2个人遭到了淘汰，剩下的3，1两人就组成了标准的两人环的情况！

若庄家选择牌2，则2号被淘汰（不会得到胜率贡献），3号（成为两人环的庄主）的胜率就将是20%，1号（成为两人环的小二）的胜率就将是80%。

当然这样分配胜率的前提是“本轮中庄家确实选了牌2”，实际概率仅 \frac{1}{5}；所以对3号胜利的真正贡献是 \frac{1}{5} × 20\%，对1号胜利的真正贡献是 \frac{1}{5} × 80\%。

庄家还可能选择别的牌（还可能淘汰自己）。但是淘汰掉三人中的一个后，接下来的两人形成新环（庄主可能改变），所以可以直接从两人环的情况继承。

这种方法不用保留谁被淘汰掉的状态。

四个人成环的情况，同样枚举庄家选择了什么牌，被淘汰的人之后的三个人的情况就可以利用已求出的三人环了。

//在第四层内，我们将根据已求出的三人环求出四人环内每个人的胜利几率。
//下面所有“4”是第四层的的意思，仅供模拟当前层。a[]数组存储着牌上的数字

  for(int k = 1; k <= m; ++k)//枚举4人中的庄家选的牌
  {
      int p = (a[k] % 4 == 0) ? 4 : a[k] % 4;
      //如果取a[k]这张牌，淘汰掉p（p = a[k] % 4），那么下一轮p+1坐庄，p+2将是二号
      //因此p+1获得“下一盘庄主的胜率 × 1/m”，p+2获得“下一盘小二的胜率 × 1/m”...

      for(int j = 1; j <= 4-1; ++j)//被淘汰者的后面的3个人，就成为新3人环的第1、2、3个人，因此可以获得一些胜率
      {
          ++p;//后面一个人
          if(p > 4)//这是回到环首了
              p = 1;                
          f[4][p] += f[4-1][j] / (double)(m);//根据上一层状态继承。本层第p个对应上一层第j个。注意这一选择的实际发生几率只有1/m
      }
  }

代码

//头文件等没特别
int n, m;
int a[51];//存各个牌上的数字

double f[51][51];
//对于指定的的卡牌，f[i][j]指的是i人形成的环中，第j个人的胜率
//我们将倒序递推出f数组

int main()
{
    n = getint(), m = getint();
    for(int i = 1; i <= m; ++i)
        a[i] = getint();

    f[1][1] = 1.0;//只剩一个人时，此人100%获胜

    for(int i = 2; i <= n; ++i)//根据i-1人环，求出i人环的情况
        for(int k = 1; k <= m; ++k)//枚举本轮庄家选择的牌
        {
            int p = (a[k] % i == 0) ? i : a[k] % i;
            //如果取a[k]，第a[k] % i（用p记录）人被淘汰，下一轮p+1坐庄

            for(int j = 1; j <= i-1; ++j)
            {
                ++p;//下一个人
                if(p > i)
                    p = 1;              
                f[i][p] += f[i-1][j] / (double)(m);
            }
        }

    for(int i = 1; i <= n; ++i)
        printf("%.2lf%% ", f[n][i] * 100.0);
    return 0;
}