首页 > ACM题库 > HDU-杭电 > HDU 4043-FXTZ II-概率-[解题报告]HOJ
2015
04-16

HDU 4043-FXTZ II-概率-[解题报告]HOJ

FXTZ II

问题描述 :

Cirno is playing a fighting game called "FXTZ" with Sanae.
Sanae is a ChuShou(master) of the game while Cirno is a ShaBao(noob). Since Cirno is a ShaBao, she just presses a random key on the keyboard for every 0.5 second, expecting to make a BiShaJi.
The battle begins. Having tried exactly 9 times, she finally makes a BiShaJi! She find herself summoned N iceballs!!! Then Sanae’s HP decreases to 0 immediately….It should have been like that. But Cirno is too simple, always navie. She doesn’t know how to handle the iceballs, so she starts to press the keyboard at random, again.
Let’s see how the iceball damages. Each iceball has a fixed energy: the first ball’s energy is 2^0, the second ball’s energy is 2^1,…, and the N-th ball’s energy is 2^(N-1). The damage caused by an iceball is equal to its energy. Cirno will shoot N times. Since Cirno is pressing the keyboard at random, each time Cirno will choose exactly one iceball with equal possibility to shoot out. Once shot out, the iceball can’t be chosen again. And even worse, the target may be either her opponent or herself, with equal possibility(50%). What a big ShaBao she is. =_=
During shooting, once Cirno’s HP is less than Sanae’s, she will lose the game. Otherwise, she wins.
You may assume Sanae did nothing while Cirno’s shooting(all damages are caused by Cirno’s iceball), and their original HP are both 2^N (No one will die in the middle of the battle unless Cirno’s HP is less than Sanae’s).
Here comes the question: Can you calculate the possibility of Cirno’s victory?

输入:

The first line an integer C (C<=30), the number of test cases.
For each case, the only line contains one integer N(0<N<=500), indicating the number of iceballs.

输出:

The first line an integer C (C<=30), the number of test cases.
For each case, the only line contains one integer N(0<N<=500), indicating the number of iceballs.

样例输入:

2
1
4

样例输出:

1/2
35/128

比赛的时候愣是把规律给猜出来了,半写半猜吧。

不知道为什么,这种简单题一放在ACM上我就傻了,如果在试卷上我肯定一下子就做出来。

还是心理因素吧。当吴磊说人家16分钟就过了的时候,我就想这么简单啊。结果一两分钟就猜出了规律。而之前是没有一点头绪,心就焦急着,肿么也想不出来。

其实仔细想很简单,就是后一个状态和前一个状态的关系很大,这也是ACM当中一个很常见的思想。

看人家规律写的挺好,我就直接粘了。

        当n=1时,p1 = 1/2
        当n=2时,第一个技能伤害如果是2,只要第一个打出的技能打向A,则B必胜,这个事件发生的概率为1/2 * 1/2;第一个如果是1,那么只有两技能都打向A,B才能胜,事件发生 的概率为1/2 * 1/2 * 1/2;.则p2 =1/4 + 1/8 = 3/8
        当n=3时,伤害为4的技能如果为第一个技能,只要打向A,则B必胜,发生的概率为1/3 * 1/2;如果为第二个技能,则前一个技能和这个技能必须都打向A,B才能胜,概率为1/3 * 1/2 * 1/2;如果为第三个技能,则前两可如当n=2时的概率且第三个技能必须打向A,B才能,概率为1/3 * 3/8 *1/2.则
p3=1/3 * (1 + p1 + p2) * 1/2.
        同理,p4 = 1/4 * (1 + p1 + p2 + p3) * 1/2
        则 pn = 1/(2 * n) * (1 + p1 + p2 + … + p(n – 1)).
由上式可推得 pn = p(n-1) * (2 * n – 1)/(2 * n)(以下代码即用此式解答),
如果继续推,可推得pn = A(2n , n)/( 2^(2n) * n! )(其中,A(2n , n)为排列式)。

推出这样的式子应该想到数不够存的,应该用高精度

总结:

      what you have to defeat is yourself.

import java.util.*;
import java.math.*;

public class Main{//这个是类
	public static void main(String args[]){//这个是主函数
		Scanner cin = new Scanner(System.in);
		BigInteger[] ans1 = new BigInteger[505];
		BigInteger[] ans2 = new BigInteger[505];
		BigInteger tmp;
		ans1[1] = BigInteger.ONE;
		ans2[1] = BigInteger.valueOf(2);
		for(int i = 2; i <= 500; i ++){
			ans1[i] = ans1[i - 1].multiply(BigInteger.valueOf(2 * i - 1));
			ans2[i] = ans2[i - 1].multiply(BigInteger.valueOf(2 * i));
			tmp = ans1[i].gcd(ans2[i]);
			ans1[i] = ans1[i].divide(tmp);
			ans2[i] = ans2[i].divide(tmp);
		}
		int t,n;
		t = cin.nextInt();
		for(int i = 0; i < t; i ++){
			n = cin.nextInt();
			System.out.print(ans1[n]);
			System.out.print('/');
			System.out.println(ans2[n]);
		}
	}
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/julyana_lin/article/details/7885083


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.