题意:A有hp1点血,ap1点攻击里;B有有hp2点血,ap2点攻击里,回合制,一个回合内只有一个人进行攻击,两人攻击是的概率是等可能的,问A胜的概率;
解法:
A能打B a(hp2/ap1+!!(hp2%ap1))下;
B能打A b(hp1/ap2+!!(hp1%ap2))下;
如果A胜,则B必然被打a下,A则可被打0~(b-1)下
设 A 被打N下 且B被打死(故最后一下一定是A打B)的概率为 C(N,b+N-1)*pow(0.5,b+N);
所以A胜的概率为 sum(C(i,b+i-1)*pow(0.5,b+i)) 0<=i<a;复杂度O(n^2) maxn = 3w;超时
不难发现
C(i,b+i-1) = C(i-1,b+i-1-1)*(b+i-1)/i;
所以 用 tmp*=(b+i-1)/i 累乘的方式计算出各级C(i,b+i-1);
因为乘的太多, double精度会丢失,导致WA所以用log10()优化一下
tmp *= log10(b+i-1)-log10(i);
ans+=pow(10,tmp)*pow(0.5,b+i) = pow(10,tmp+(b+i)*log(0.5));
//code
#include<iostream> #include<cmath> #include<cstdio> using namespace std; double C(int m, int n) { double ans =1.0; for(int i=1; i<=n; i++) { if(i<=m) ans/=1.0*i; else if(i>=n-m) ans*=i; } return ans; } int main() { int h1,h2,a1,a2; while(cin>>h1>>h2>>a1>>a2) { double ans = 0.0; int a = h1/a2+!!(h1%a2); int b = h2/a1+!!(h2%a1); double w1, w2; ans = pow(0.5,b); double tmp=0.0; for(int i=1; i<a; i++) { tmp += log10((b-1+i)*1.0)-log10(1.0*i); ans += pow(10,tmp+(b+i)*log10(0.5)); } printf("%.4lf\n", 100.0*ans); } return 0; }