M_sea

洛谷2059 [JLOI2013]卡牌游戏
题目描述N个人坐成一圈玩游戏。一开始我们把所有玩家按顺时针从1到N编号。首先第一回合是玩家1作为庄家。每个回合庄家...
扫描右侧二维码阅读全文
28
2018/02

洛谷2059 [JLOI2013]卡牌游戏

题目描述

N个人坐成一圈玩游戏。一开始我们把所有玩家按顺时针从1到N编号。首先第一回合是玩家1作为庄家。每个回合庄家都会随机(即按相等的概率)从卡牌堆里选择一张卡片,假设卡片上的数字为X,则庄家首先把卡片上的数字向所有玩家展示,然后按顺时针从庄家位置数第X个人将被处决即退出游戏。然后卡片将会被放回卡牌堆里并重新洗牌。被处决的人按顺时针的下一个人将会作为下一轮的庄家。那么经过N-1轮后最后只会剩下一个人,即为本次游戏的胜者。现在你预先知道了总共有M张卡片,也知道每张卡片上的数字。现在你需要确定每个玩家胜出的概率。

这里有一个简单的例子:

例如一共有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.

传送门

算法

SB暴力

正解是概率DP。。。

设$f[i][j]$表示还剩i个人时第j个人的获胜概率。

边界显然是$f[1][1]=1.0$。
那么状态如何转移呢?

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

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

所以$f[i][j]+=f[i-1][c]/m$,最后输出即可。

注意到$j==c$时是不用计算的。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
double f[60][60]; //f[i][j]表示还剩i个人时第j个人的获胜概率 
int num[60];
int main() {
    int n,m; scanf("%d%d",&n,&m);
    for (re int i=1;i<=m;i++) scanf("%d",&num[i]);
    f[1][1]=1.0;
    for (re int i=2;i<=n;i++)
        for (re int j=1;j<=n;j++)
            for (re int k=1;k<=m;k++) {
                int c=(num[k]%i) ? num[k]%i : i;
                if (c<j) f[i][j]+=f[i-1][j-c]/m;
                else if (c>j) f[i][j]+=f[i-1][i-c+j]/m;
            }
    for (re int i=1;i<=n;i++) printf("%.2lf%% ",f[n][i]*100.0);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 41 PM

发表评论

1 条评论

  1. ZCDHJ

    我都不会算概率