链接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 p，往左走一格的概率是 1 − p 1-p 1−p,题目要求的则是Alice走到 n + m n+m n+m处的概率。
思路：假设Alice赢的概率为 p p p,输的概率则为 1 − p 1-p 1−p，当Alice有 i i i颗糖果时，其将Bob的糖果赢完的概率设为 f i f_i fi​,可列出以下方程：
f 0 = 0 ,   f n + m = 1 f_0 = 0,\ f_{n+m} = 1 f0​=0, fn+m​=1
f i = ( 1 − p ) f i − 1 + p f i + 1   ( 1 ) f_i=(1-p)f_{i-1}+pf_{i+1}\ (1) fi​=(1−p)fi−1​+pfi+1​ (1)
根据题目 f n + m = 1 f_{n+m}=1 fn+m​=1 我们采用倒推，假设 f i = k i f i + 1 f_i=k_if_{i+1} fi​=ki​fi+1​带入（1）式中得到 k i k_i ki​的递推关系式：
k i = p 1 − ( 1 − p ) k i − 1 ( 2 ) k_i=\frac{p}{1-(1-p)k_{i-1}}(2) ki​=1−(1−p)ki−1​p​(2)
∵ \because ∵ f 0 = 0 f 1 f_0=0f_1 f0​=0f1​ ∴ \therefore ∴ k 0 = 0 k_0=0 k0​=0
综上述可知答案为 f n = ∏ i = n n + m − 1 k i 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;
}