现在的位置: 首页 > 综合 > 正文

hdu-1410-PK武林盟主

2019年02月10日 ⁄ 综合 ⁄ 共 939字 ⁄ 字号 评论关闭

题意: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;
}
【上篇】
【下篇】

抱歉!评论已关闭.