题目描述
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
提示
概率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]。
#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的更多相关文章
-
【BZOJ2318】Spoj4060 game with probability Problem 概率
[BZOJ2318]Spoj4060 game with probability Problem Description Alice和Bob在玩一个游戏.有n个石子在这里,Alice和Bob轮流投掷硬 ...
-
【bzoj2318】Spoj4060 game with probability Problem 概率dp
题目描述 Alice和Bob在玩一个游戏.有n个石子在这里,Alice和Bob轮流投掷硬币,如果正面朝上,则从n个石子中取出一个石子,否则不做任何事.取到最后一颗石子的人胜利.Alice在投掷硬币时有 ...
-
【BZOJ 2318】 2318: Spoj4060 game with probability Problem(概率DP)
2318: Spoj4060 game with probability Problem Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 371 Sol ...
-
BZOJ2318: Spoj4060 game with probability Problem
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #i ...
-
BZOJ 2318: Spoj4060 game with probability Problem( 概率dp )
概率dp... http://blog.csdn.net/Vmurder/article/details/46467899 ( from : [辗转山河弋流歌 by 空灰冰魂] ) 这个讲得很好 , ...
-
【CF954I】Yet Another String Matching Problem(FFT)
[CF954I]Yet Another String Matching Problem(FFT) 题面 给定两个字符串\(S,T\) 求\(S\)所有长度为\(|T|\)的子串与\(T\)的距离 两个 ...
-
2318: Spoj4060 game with probability Problem
2318: Spoj4060 game with probability Problem Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 356 Sol ...
-
Bzoj 2318 Spoj4060 game with probability Problem
2318: Spoj4060 game with probability Problem Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 524 Sol ...
-
【概率论】2-1:条件概率(Conditional Probability)
title: [概率论]2-1:条件概率(Conditional Probability) categories: Mathematic Probability keywords: Condition ...
随机推荐
-
[LeetCode] Integer to Roman 整数转化成罗马数字
Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 t ...
-
Python:如何删除文件中的空白行?
def delblankline(infile,outfile): infopen = open(infile,'r') outfopen = open(outfile,'w') lines = in ...
-
Javascript和ECMAScript二三事
来自<javascript高级程序设计 第三版:作者Nicholas C. Zakas>的学习笔记(一) Javascript是一种专为与网页交互而设计的脚本语言,由下列三个不同部分组成: ...
-
nodejs读取本地txt文件并输出到浏览器
var fs = require('fs'); var chrome=""; //同步执行 function tongbu(){ var data =fs.readFileSync ...
-
Java ------------获取不会重复的随机数
import java.util.UUID; public class UTest { public static void main(String[] args) { //UUID通过rand ...
-
DL4NLP——词表示模型(二)基于神经网络的模型:NPLM;word2vec(CBOW/Skip-gram)
本文简述了以下内容: 神经概率语言模型NPLM,训练语言模型并同时得到词表示 word2vec:CBOW / Skip-gram,直接以得到词表示为目标的模型 (一)原始CBOW(Continuous ...
-
【动画】JQuery实现冒泡排序算法动画演示
1 前言 冒泡排序是大家最熟悉的算法,也是最简单的排序算法,因其排序过程很象气泡逐渐向上漂浮而得名.为了更好的理解其基本的思想,毛三胖利用JQuery实现了冒泡排序的动画演示,并计划陆续实现其它排序算 ...
-
Feign get接口传输对象引发一场追寻
一个报错引发的追寻之路: Feign get接口传输对象,调用方接口代码: @FeignClient(name = "manage") public interface Acces ...
-
@JsonView 简单介绍[z]
@JsonView是jackson json中的一个注解,Spring webmvc也支持这个注解. 这个注解的作用就是控制输入输出后的json. 假设我们有一个用户类,其中包含用户名和密码,一般情况 ...
-
winSockets编程(五)非阻塞模式(远程算数程序)
##