链接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("%.5f\n",ans);
	}
    return 0;
}