「BZOJ2318」SPOJ4060 game with probability Problem
Description
Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。
现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。
Input
第一行一个正整数t，表示数据组数。
对于每组数据，一行三个数n，p，q。
Output
对于每组数据输出一行一个实数，表示Alice胜利的概率，保留6位小数。
Sample Input
1
1 0.5 0.5
1 0.5 0.5
Sample Output
0.666667
HINT
数据范围：
1<=t<=50
0.5<=p,q<=0.99999999
对于100%的数据 1<=n<=99999999
题解
f[i]表示i个球A先投A获胜的概率，s[i]表示B先投A获胜的概率
然后利用等比数列什么的乱搞
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int T,n; double p,q; double get_AA,get_AB,get_BA,get_BB; double pop_AA,pop_AB,pop_BA,pop_BB; double f[105],s[105]; int main() { double k;scanf("%d",&T); while(T--) { f[0]=0;s[0]=1; scanf("%d%lf%lf",&n,&p,&q); if(n>100)n=100; k=1-(1-p)*(1-q); get_AA=p/k;get_AB=(1-p)*q/k; get_BB=q/k;get_BA=(1-q)*p/k; k=1-p*q; pop_AA=(1-p)/k;pop_AB=(1-q)*p/k; pop_BA=q*(1-p)/k;pop_BB=(1-q)/k; for(int i=1;i<=n;i++) if(f[i-1]<s[i-1]) { f[i]=get_AA*s[i-1]+get_AB*f[i-1]; s[i]=get_BA*s[i-1]+get_BB*f[i-1]; } else { f[i]=pop_AB*f[i-1]+pop_AA*s[i-1]; s[i]=pop_BB*f[i-1]+pop_BA*s[i-1]; } printf("%.6lf\n",f[n]); } return 0; } |
计数器 9786942
OI 课件=>
OI 课件=>
黄学长，这个状态不对吧