【bzoj2318】Spoj4060 game with probability Problem

时间:2022-09-05 23:47:14

题目描述

Alice和Bob在玩一个游戏。有n个石子在这里,Alice和Bob轮流投掷硬币,如果正面朝上,则从n个石子中取出一个石子,否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面,同样,Bob有q的概率投掷出他相投的一面。

现在Alice先手投掷硬币,假设他们都想赢得游戏,问你Alice胜利的概率为多少。

输入

第一行一个正整数t,表示数据组数。

对于每组数据,一行三个数n,p,q。

输出

对于每组数据输出一行一个实数,表示Alice胜利的概率,保留6位小数。

样例输入

1
1 0.5 0.5

样例输出

0.666667

提示

数据范围:
1<=t<=50
0.5<=p,q<=0.99999999
对于100%的数据 1<=n<=99999999

题解

概率dp

这题真是巨坑。。。

f[i]表示i块石头先投者获胜的概率,g[i]表示i块石头后投者获胜的概率。

易推出:

$f[i]=\frac{p_0·g[i-1]+(1-p_0)·q_0·f[i-1]}{1-(1-p_0)·(1-q_0)}$

$g[i]=\frac{q_0·f[i-1]+(1-q_0)·p_0·g[i-1]}{1-(1-p_0)·(1-q_0)}$

然而这里$p_0$和$q_0$都是目标概率,而题目中的p和q都是几率,

所以需要根据情况决定是否想要正面朝上。

根据方程的推导:

A想让自己获胜的概率最大,即让$f[i]$最大。

假设$g[i-1]-f[i-1]$不等于$0$,把$f[i]$的推导式展开,得:

$f[i]=\frac{p_0·g[i-1]+(1-p_0)·q_0·f[i-1]}{1-(1-p_0)·(1-q_0)}\\\ \ \ \ \ \ =\frac{(p_0+q_0-p_0·q_0)·f[i-1]+p_0(g[i-1]-f[i-1])}{p_0+q_0-p_0·q_0}\\\ \ \ \ \ \ =f[i-1]+\frac{p_0(g[i-1]-f[i-1])}{p_0+q_0-p_0·q_0}\\\ \ \ \ \ \ =f[i-1]+\frac1{\frac{p_0+q_0-p_0·q_0}{p_0(g[i-1]-f[i-1])}}\\\ \ \ \ \ \ =f[i-1]+\frac1{\frac{1-q_0+\frac{q_0}{p_0}}{g[i-1]-f[i-1]}}$

显然当$g[i-1]-f[i-1]>0$时,$p_0$越大越好;当$g[i-1]-f[i-1]<0$时,$p_0$越小越好。

$q_0$的推导同理。

于是可以得到结论:

当f[i-1]<g[i-1]时,都想要正面朝上,$p_0=p$,$q_0=q$;

当f[i-1]>g[i-1]时,都不想要正面朝上,$p_0=1-p$,$q_0=1-q$。

但是n太大肿么办?

于是用到概率黑科技:

当n越来越大时,f[n]逐渐趋近于一个定值,而且题目中只要求保留6位小数。

所以就此题而言f[1000+k]可以近似等于f[1000]。

于是时间复杂度就降为O(1000T),可解。
#include <cstdio>
#include <cstring>
double f[1001] , g[1001];
int main()
{
int t;
scanf("%d" , &t);
while(t -- )
{
int n , i;
double p , q;
scanf("%d%lf%lf" , &n , &p , &q);
memset(f , 0 , sizeof(f));
memset(g , 0 , sizeof(g));
if(n > 1000)
n = 1000;
f[0] = 0;
g[0] = 1;
for(i = 1 ; i <= n ; i ++ )
{
if(f[i - 1] > g[i - 1])
p = 1 - p , q = 1 - q;
f[i] = (p * g[i - 1] + (1 - p) * q * f[i - 1]) / (1 - (1 - p) * (1 - q));
g[i] = (q * f[i - 1] + (1 - q) * p * g[i - 1]) / (1 - (1 - p) * (1 - q));
if(f[i - 1] > g[i - 1])
p = 1 - p , q = 1 - q;
}
printf("%.6lf\n" , f[n]);
}
return 0;
}

【bzoj2318】Spoj4060 game with probability Problem的更多相关文章

  1. 【BZOJ2318】Spoj4060 game with probability Problem 概率

    [BZOJ2318]Spoj4060 game with probability Problem Description Alice和Bob在玩一个游戏.有n个石子在这里,Alice和Bob轮流投掷硬 ...

  2. 【bzoj2318】Spoj4060 game with probability Problem 概率dp

    题目描述 Alice和Bob在玩一个游戏.有n个石子在这里,Alice和Bob轮流投掷硬币,如果正面朝上,则从n个石子中取出一个石子,否则不做任何事.取到最后一颗石子的人胜利.Alice在投掷硬币时有 ...

  3. 【BZOJ 2318】 2318&colon; Spoj4060 game with probability Problem(概率DP)

    2318: Spoj4060 game with probability Problem Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 371  Sol ...

  4. BZOJ2318&colon; Spoj4060 game with probability Problem

    #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #i ...

  5. BZOJ 2318&colon; Spoj4060 game with probability Problem&lpar; 概率dp &rpar;

    概率dp... http://blog.csdn.net/Vmurder/article/details/46467899 ( from : [辗转山河弋流歌 by 空灰冰魂] ) 这个讲得很好 , ...

  6. 【CF954I】Yet Another String Matching Problem(FFT)

    [CF954I]Yet Another String Matching Problem(FFT) 题面 给定两个字符串\(S,T\) 求\(S\)所有长度为\(|T|\)的子串与\(T\)的距离 两个 ...

  7. 2318&colon; Spoj4060 game with probability Problem

    2318: Spoj4060 game with probability Problem Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 356  Sol ...

  8. Bzoj 2318 Spoj4060 game with probability Problem

    2318: Spoj4060 game with probability Problem Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 524  Sol ...

  9. 【概率论】2-1&colon;条件概率&lpar;Conditional Probability&rpar;

    title: [概率论]2-1:条件概率(Conditional Probability) categories: Mathematic Probability keywords: Condition ...

随机推荐

  1. &lbrack;LeetCode&rsqb; Integer to Roman 整数转化成罗马数字

    Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 t ...

  2. Python&colon;如何删除文件中的空白行?

    def delblankline(infile,outfile): infopen = open(infile,'r') outfopen = open(outfile,'w') lines = in ...

  3. Javascript和ECMAScript二三事

    来自<javascript高级程序设计 第三版:作者Nicholas C. Zakas>的学习笔记(一) Javascript是一种专为与网页交互而设计的脚本语言,由下列三个不同部分组成: ...

  4. nodejs读取本地txt文件并输出到浏览器

    var fs = require('fs'); var chrome=""; //同步执行 function tongbu(){ var data =fs.readFileSync ...

  5. Java ------------获取不会重复的随机数

    import java.util.UUID; public class UTest {    public static void main(String[] args) { //UUID通过rand ...

  6. DL4NLP——词表示模型(二)基于神经网络的模型:NPLM;word2vec(CBOW&sol;Skip-gram)

    本文简述了以下内容: 神经概率语言模型NPLM,训练语言模型并同时得到词表示 word2vec:CBOW / Skip-gram,直接以得到词表示为目标的模型 (一)原始CBOW(Continuous ...

  7. 【动画】JQuery实现冒泡排序算法动画演示

    1 前言 冒泡排序是大家最熟悉的算法,也是最简单的排序算法,因其排序过程很象气泡逐渐向上漂浮而得名.为了更好的理解其基本的思想,毛三胖利用JQuery实现了冒泡排序的动画演示,并计划陆续实现其它排序算 ...

  8. Feign get接口传输对象引发一场追寻

    一个报错引发的追寻之路: Feign get接口传输对象,调用方接口代码: @FeignClient(name = "manage") public interface Acces ...

  9. &commat;JsonView 简单介绍&lbrack;z&rsqb;

    @JsonView是jackson json中的一个注解,Spring webmvc也支持这个注解. 这个注解的作用就是控制输入输出后的json. 假设我们有一个用户类,其中包含用户名和密码,一般情况 ...

  10. winSockets编程(五)非阻塞模式(远程算数程序)

    ##