首页 > ACM题库 > HDU-杭电 > HDU 1410 PK武林盟主-概率-[解题报告] C++
2013
12-09

HDU 1410 PK武林盟主-概率-[解题报告] C++

PK武林盟主

问题描述 :

枫之羽认为自己很强,想当武林盟主,于是找现任武林盟主氢氧化铜挑战。氢氧化铜欣然接受了挑战,两人约好于下个月的月圆之夜在HDU校园内的三根柱子上进行决战。这场PK赛肯定能吸引武林中所有人前来观战,所以他们找了有商业运作潜力的经济人你,让你来组织这场百年一见的世纪之战,假设两人都有一定的血HP1、HP2.HP1是枫之羽的,HP2是氢氧化铜的。他们也有一定攻击力AP1、AP2,AP1是枫之羽的,AP2是氢氧化铜的。当进行攻击时,对方的HP减少自己的攻击力,比如HP1=2 HP2=1 AP1=1 AP2=1,当氢氧化铜攻击枫之羽时,枫之羽的HP=2(原先的HP1)-1(氢氧化铜的AP2)=1。现在两个人对决很多回合,每回合不是枫之羽攻击氢氧化铜,就是氢氧化铜攻击枫之羽。求枫之羽能赢氢氧化铜成为下任武林盟主的的胜率。

输入:

该题含有多组测试数据,每行为HP1,HP2,AP1和AP2 (1<=HP1,HP2,AP1,AP2<=32767)

输出:

每组数据输出一行,为枫之羽赢氢氧化铜概率的值 (结果保留4位小数).

样例输入:

2 1 1 1

样例输出:

75.0000

题意: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;
}

解题报告转自:http://blog.csdn.net/u010724594/article/details/8981731


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  3. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts