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

· · 题解

【题目描述】

这里有一个简单的例子： 例如一共有$4$个玩家，有四张卡片分别写着$3,4,5,6$。 第一回合，庄家是玩家$1$，假设他选择了一张写着数字$5$的卡片。那么按顺时针数$1,2,3,4,1$，最后玩家$1$被踢出游戏。 第二回合，庄家就是玩家1的下一个人，即玩家$2$。假设玩家$2$这次选择了一张数字$6$，那么$2,3,4,2,3,4$，玩家$4$被踢出游戏。 第三回合，玩家$2$再一次成为庄家。如果这一次玩家$2$再次选了$6$，则玩家$3$被踢出游戏，最后的胜者就是玩家$2$。 【输入输出格式】 - 输入格式 第一行包括两个整数$n,m$分别表示玩家个数和卡牌总数。 接下来一行是包含$m$个整数，分别给出每张卡片上写的数字。 - 输出格式 输出一行包含$n$个百分比形式给出的实数，四舍五入到两位小数。分别给出从玩家$1$到玩家$n$的胜出概率，每个概率之间用空格隔开。 【输入输出样例】 - 输入样例$1 
4 4
3 4 5 6

25.00% 25.00% 25.00% 25.00% 
5 5
2 3 5 7 11

22.72% 17.12% 15.36% 25.44% 19.36%

【数据范围】

对于30%的数据，有1 \leq n \leq 10；

对于50%的数据，有1 \leq n \leq 30；

对于100%的数据，有1 \leq n \leq 50，1 \leq m \leq 50，1 \leq 每张卡片上的数字 \leq 50。

思路：这道题目很明显可以通过枚举来确定最后的胜利者是谁。然后我们就可以根据所有的结果来分析每一个人的胜率了。下面我将举出一个n=2,m=3的例子：

2 3
1 2 3

第1种情况：1号拿了1号卡牌，上面的数字是1。因此1号出局，2号胜利。

第2种情况：1号拿了2号卡牌，上面的数字是2。因此2号出局，1号胜利。

第3种情况：1号拿了3号卡牌，上面的数字是3。因此1号出局，2号胜利。

根据上面的结果，我们发现：1号赢了1次，2号赢了2次。因此1号的胜率为\frac{1}{3}，2号的胜率为\frac{2}{3}。将1号和2号的胜率四舍五入到两位小数时他们的胜率分别为33.33%和66.67%。dfs()的复杂度是O(m^n)的，感谢各位大佬提醒！

那么我们怎样才能够进一步地优化我们的程序呢？

其实我们可以使用一种叫做概率动态规划的算法，即我们常说的概率DP。

我们可以用概率DP来解决这个问题。我们可以用f[i][j]来表示在还剩下i个人时，从庄家开始数第j个人的获胜的概率。其实还有一种时间复杂度约为O(\sum_1^{n-1}\sum_{j=1}^n\sum_{k=1}^{n-i} {m})的一种方法，在这里我就不做介绍了，在这篇文章中我只介绍上面的这种时间复杂度约为O(mn^2)的一种办法。

首先我们可以确定当还有1个人时第1号的胜率为100%，即1.0。我们不难发现f[i][]的状态可以从f[i-1][]中转移过来。那么怎么转移我们的f数组呢？

我们可以首先枚举庄家抽到的卡牌k，得到这一轮被淘汰的人的位置c。当然，如果c=j ，就不要考虑了（因为这表示此轮第j个人被淘汰）。

而第c个人被淘汰之后，剩下的i-1个人要组成一个新的环，庄家为第c个人的下一个。容易算出，当c>j时，第j个人是新的环里从新庄家数起的第i-c+j个人，当c<j时，第j个人是新的环里从新庄家数起的第j-c个人。

上面的引用部分里的内容摘自@xyz32768的博客，放入题解时有删改。

因此我们可以得出状态转移方程：

当c>j时，f[i][j]=f[i][j]+f[i-1][i-c+j] \div m，即f[i][j]=f[i][j]+\frac{f[i-1][i-c+j]}{m}；

否则当c<j时，f[i][j]=f[i][j]+f[i-1][j-c] \div m，即f[i][j]=f[i][j]+\frac{f[i-1][j-c]}{m}。

其中，j \leq i会更加优，感谢@Yunxuan的建议。

下面上100分（满分）代码：

#include <cstdio>
double f[1001][1001];
int a[10001];
int main()
{
    int n=0,m=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
    }
    f[1][1]=1.0;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            for(int k=1;k<=m;k++)
            {
                int c=(a[k]%i!=0)?(a[k]%i):i;
                if(c>j)
                {
                    f[i][j]+=f[i-1][i-c+j]/m;
                }
                else if(c<j)
                {
                    f[i][j]+=f[i-1][j-c]/m;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%.2lf%% ",f[n][i]*100.0);
    }
    return 0;
}