牛客NOIP暑期七天营-普及组2-C硬币

硬币

https://ac.nowcoder.com/acm/contest/926/C

题目大意:有n枚硬币,a枚正面朝上,b枚反面朝上,每次操作随机抽取一枚翻过来,m次操作正面朝上的数量的数学期望是多少?

如果只有1枚硬币,每次翻转的都是同一枚,最终要么是正面朝上,要么是反面朝上,数学期望是0或者1。

对于n枚硬币,a枚正面朝上,b枚反面朝上,下一次有两种状态:

1、随机抽到正面朝上,翻转后a-1枚朝上,b+1枚朝下,概率是a/n

2、随机抽到反面朝上,翻转后a+1枚朝上,b+1枚朝下,概率是b/n

如果当前的情况的概率是x,那么这两种情况的概率分别是

反向推也是同样的道理。

递推关系:f[i][j]表示第i次操作,有j枚硬币正面朝上,上一步是f[i-1][j-1]和f[i-1][j+1],注意边界即可。

最终答案:m次之后,1的概率+2的概率+...+n的概率。

滚动数组优化:

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, b, p;
double f[5][5005], ans;
int main(){
    scanf("%d%d%d%d", &n, &a, &b, &m);
    f[0][a] = 1;
    for(i=1; i<=m; i++){
        for(j=0; j<=n; j++){
            f[i&1][j] = 0;
            if(j < n) f[i&1][j] += f[i-1&1][j+1] * (j+1) / n;
            if(j) f[i&1][j] += f[i-1&1][j-1] * (n-j+1) / n;
        }
    }
    for(i=1; i<=n; i++) ans += i * f[m&1][i];
    printf("%.8lf\n", ans);
    return 0;
}

优化前二维数组:

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, b;
double f[5005][5005], ans;
int main(){
    scanf("%d%d%d%d", &n, &a, &b, &m);
    f[0][a] = 1;
    for(i=1; i<=m; i++){
        for(j=0; j<=n; j++){
            if(j < n) f[i][j] += f[i-1][j+1] * (j+1) / n;
            if(j) f[i][j] += f[i-1][j-1] * (n-j+1) / n;
        }
    }
    for(i=1; i<=n; i++) ans += i * f[m][i];
    printf("%.6lf\n", ans);
    return 0;
}

从前往后推:

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, b;
double f[5005][5005], ans;
int main(){
    scanf("%d%d%d%d", &n, &a, &b, &m);
    f[0][a] = 1;
    for(i=0; i<m; i++){
        for(j=0; j<=n; j++){
            if(j) f[i+1][j-1] += f[i][j] * j / n;
            f[i+1][j+1] += f[i][j] * (n-j) / n;
        }
    }
    for(i=1; i<=n; i++) ans += i * f[m][i];
    printf("%.8lf\n", ans);
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
09-25 10:34
东北大学 Java
多面手的小八想要自然醒:所以读这么多年到头来成为时代车轮底下的一粒尘
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务