Alice和Bob赌糖果(概率dp)概率论qq44032783的博客-

链接https://ac.nowcoder.com/acm/problem/14962

来源：牛客网

题目描述

Alice和Bob赌糖果。规则是这样的：Alice从[ l, r]中随机抽一个数，Bob从[ L, R]中随机抽一个数，谁抽的数大谁就赢，输的一方给另一方1颗糖（平局不用给糖），他们会一直赌下去直到有一方没有糖果为止。Alice有n颗糖果，Bob有m颗糖果，求Alice将Bob的糖果赢完的概率。

输入描述

第一行3个整数n, l, r。
第二行3个整数m, L, R。

输出描述

Alice将Bob糖果赢完的概率，结果保留5位小数。

示例1

输入
1 1 3
1 1 2
输出
0.75000

示例2

输入
0 1 100
1 1 100
输出
0.00000

备注

0 <= n,m <=1e5,n+m > 0
1 <= l <= r <= 100,1 <= L <= R <= 100

思路

首先我们大致理解下题意：Alice起始位置在坐标轴的n点，他往右走一格的概率是
$p$

p，往左走一格的概率是
$1-p$

1−p,题目要求的则是Alice走到
$n+m$

n+m处的概率。
思路：假设Alice赢的概率为
$p$

p,输的概率则为
$1-p$

1−p，当Alice有
$i$

i颗糖果时，其将Bob的糖果赢完的概率设为
$f_i$

fi​,可列出以下方程：

$f_0 = 0, f_{n+m} = 1$

f0​=0, fn+m​=1

$f_i=(1-p)f_{i-1}+pf_{i+1} (1)$

fi​=(1−p)fi−1​+pfi+1​ (1)
根据题目
$f_{n+m}=1$

fn+m​=1 我们采用倒推，假设
$f_i=k_if_{i+1}$

fi​=ki​fi+1​带入（1）式中得到
$k_i$

ki​的递推关系式：

$k_i=frac{p}{1-(1-p)k_{i-1}}(2)$

ki​=1−(1−p)ki−1​p​(2)

$because$

∵
$f_0=0f_1$

f0​=0f1​
$therefore$

∴
$k_0=0$

k0​=0
综上述可知答案为
$f_n=prod_{i=n}^{n+m-1}k_i$

fn​=∏i=nn+m−1​ki​

代码示例

#include <iostream> using namespace std; double calc(int a, int b, double p){ double ans = 1.0, k = 0.0; for(int i = 1; i < b; i++){   k =  p / (1 - (1 - p) * k) ;//思路中的公式2 if(i >= a) ans *= k; } return ans; } int main(){ int n, l, r, m, L, R; scanf("%d%d%d%d%d%d", &n, &l, &r, &m, &L, &R); if(!n) printf("0.00000");//特判Alice开始没有糖果的时候，赢的概率为0 else{ int t1 = 0, t2 = 0; for(int i = l; i <= r; i++) for(int j = L; j <= R; j++){ if(i > j) t1++;//Alice赢的次数 else if(i < j) t2++;//Bob赢的次数,平局对结果无影响不考虑 } double p = t1 * 1.0 / double(t1 + t2);//注意精度 double ans = calc(n, n+m, p);//Alice从开始的n个糖果数到赢得所有n+m的糖果数的概率 printf("%.5fn",ans); } return 0; }