牛客 202H 卡牌游戏 题解【概率期望】【递推】

作者: wjyyy 分类: DP,数学,概率期望,解题报告 发布时间: 2018-10-04 00:14

点击量:5

 

    是一道思路简单的期望题。

 

题目描述

小贝喜欢玩卡牌游戏。某个游戏体系中共有\(N\)种卡牌,其中\(M\)种是稀有的。小贝每次和电脑对决获胜之后都会有一个抽卡机会,这时系统会随机从\(N\)种卡中选择一张给小贝。普通卡可能多次出现,而稀有卡牌不会被重复抽到。小贝希望收集到\(K\)种稀有卡牌,她想知道期望需要多少次获胜才能实现这个目标。
 

输入输出格式

输入格式:

数据有多组,第一行一个整数\(T\)表示数据组数。

 

每组数据一行,三个整数\(N,M,K\).

 

输出格式:

对于每组数据,输出形如”Case #x: y”,其中\(x\)为这组数据的编号(从\(1\)开始),\(y\)为这组数据的答案。答案的绝对误差或相对误差在\(10^{-6}\)以内都认为是正确的。

 

输入输出样例

样例输入:

2
5 2 1
40 9 5

样例输出:

Case #1: 2.5
Case #2: 28.1146825397

说明

$$1 ≤ T ≤ 100 \\
1 ≤ N ≤ 10^5 \\
1 ≤ M ≤ N \\
1 ≤ K ≤ M$$

 

题解:

    是看到这题通过率比较高猜到这题应该不难想,推了一会结论。

 

    发现这里的概率与条件关系不大,只是分子分母在同时变化,那么我们可以把阶段分出来。因为要抽到第一张稀有卡才能去抽第二张,以此类推,因此定义\(f_i\)表示已经抽到\(i-1\)张卡时,再抽到第\(i\)张卡所需要的期望次数。那么知道普通卡是不会减少的,只用管稀有卡是否减少,只有稀有卡减少了总数才会减少。

 

    因此当已经抽到\(i\)张时,共有\(n-i\)张卡,其中有\(m-i\)个稀有卡。一次就抽中的概率为\(\frac{m-i}{n-i}\),那么期望抽到的次数为\((\frac{m-i}{n-i}^{-1}=\frac{n-i}{m-i}\),而无论抽到哪张卡状态都是唯一的,那么每个阶段的期望就都是确定的了。

 

    而阶段又是分开的,所以我们可以把阶段连续地加起来,答案就是\(\sum_{i=0}^{k-1}\frac{n-i}{m-i}\)了。时间复杂度\(O(Tk)\)

 

Code:

#include<cstdio>
#include<cstring>
int main()
{
    int T,n,m,k;
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
    {
        scanf("%d%d%d",&n,&m,&k);
        double ans=0.0;
        for(int j=1;j<=k;++j)
            ans=ans+(double)n--/m--;//直接计算
        printf("Case #%d: %.9lf\n",i,ans);
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */