欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[LnOI2019]加特林轮盘赌

程序员文章站 2022-03-27 20:23:16
题目题目背景加特林轮盘赌是一个养生游戏.题目描述与俄罗斯轮盘赌等手枪的赌博不同的是,加特林轮盘赌的赌具是加特林。加特林轮盘赌的规则很简单:在加特林的部分弹夹中填充子弹。游戏的参加者坐在一个圆桌上,轮流把加特林对着自己的头,扣动扳机一秒钟。中枪的自动退出,坚持到最后的就是胜利者。我们使用的是2019年最新技术的加特林,他的特点是无需预热、子弹无限,每一个人,在每一回合,中枪的概率是完全相同的P_0P0​。每局游戏共有nn只长脖子鹿,从1长脖子鹿开始,按照编号顺序从小到大进行游戏,绕着圆桌...

题目

题目背景
加特林轮盘赌是一个养生游戏.

题目描述
与俄罗斯轮盘赌等手枪的赌博不同的是,加特林轮盘赌的赌具是加特林。

加特林轮盘赌的规则很简单:在加特林的部分弹夹中填充子弹。游戏的参加者坐在一个圆桌上,轮流把加特林对着自己的头,扣动扳机一秒钟。中枪的自动退出,坚持到最后的就是胜利者。

我们使用的是2019年最新技术的加特林,他的特点是无需预热、子弹无限,每一个人,在每一回合,中枪的概率是完全相同的P_0P
0

每局游戏共有nn只长脖子鹿,从1长脖子鹿开始,按照编号顺序从小到大进行游戏,绕着圆桌不断循环。

游戏可能会循环进行多轮,直到场上仅剩下最后一只长脖子鹿时,游戏结束。

给出P_0P
0

和nn,询问kk号长脖子鹿最终成为唯一幸存者的概率P_kP
k

输入格式
仅一行三个数,P_0,n,kP
0

,n,k.

输出格式
一个浮点数P_{k} P
k

,误差应该小于10^{-8}10
−8
.(请保留更多位数的小数)

输入输出样例
输入 #1 复制
0.5 2 1
输出 #1 复制
0.33333333
输入 #2 复制
0.5 2 2
输出 #2 复制
0.66666667
输入 #3 复制
0.5 3 1
输出 #3 复制
0.23809524
输入 #4 复制
0.5 3 2
输出 #4 复制
0.28571429
说明/提示
对于10%的数据,n <= 100n<=100.

对于30%的数据,n <= 500n<=500.

对于另外20%的数据,k = nk=n.

对于100%的数据,1 <= k <= n <= 10^{4}, 0 <= P_0 <= 1.1<=k<=n<=10
4
,0<=P
0

<=1.

所有数据的时间限制为 1000ms 1000ms,空间限制为 256mb 256mb,可开启O2优化。

思路

令pw1[i]表示前(k-1)只长颈鹿自毙i次以内退役的概率,pw2[i]表示编号在k+1~n的长颈鹿自毙i次以内退役的概率。于是pw1[i]=s[i](k-1),pw2[i]=s[i](n-k),其中s[i]为一只长颈鹿自毙i次以内退役的概率,很容易得到s[i]=1-(1-p)i,因为一次中枪没有退役的概率为1-p,重复i次均退役则是(1-p)i,所以i次内退役的概率就是1-(1-p)i。因为题目中求的是小数,精度要求是10-8,所以枚举第k只长颈鹿在第i次中枪时退役且为最后一个退役的概率,把所有概率加起来就行了,可以做到线性复杂度,枚举到106即可(我写的是线性105也过了)。注意要特判n=1/k=1/k=n的情况。

代码

#include<bits/stdc++.h>
using namespace std;
double mi[10010];
double dp[2][10010];
int main(){
    int n,m;
    double k;
    cin>>k>>n>>m;
    if(k==0){
        if(n==1)cout<<1<<endl;
        else cout<<0<<endl;
        return 0;
    }
    mi[0]=1;
    for(int i=1;i<=n;i++){
        mi[i]=mi[i-1]*(1.0-k);
    }
    dp[0][1]=1;
    for(int i=2;i<=n;i++){
        double sum=0;
        for(int j=2;j<=i;j++){
            sum+=(dp[0][j-1]*mi[i-j+1]);
        }
        dp[1][1]=k*sum/(1.0-mi[i]);
        for(int j=2;j<=i;j++){
            dp[1][j]=dp[1][j-1]*(1.0-k)+dp[0][j-1]*k;
        }
        for(int j=1;j<=i;j++){
            dp[0][j]=dp[1][j];
        }
    }
    printf("%0.8lf\n",dp[0][m]);
    return 0;
}

本文地址:https://blog.csdn.net/Eric1561759334/article/details/109279513