ACM

CodeForces - 148D Bag of mice(概率dp)

CodeForces - 148D Bag of mice(概率dp)
题目意思是,公主和龙比赛从一个具有w个白老鼠,b个黑老鼠的袋子里拿老鼠出来。如果公主从袋子里拿出白老鼠就算公主赢。但是每次龙拿出一只老鼠时还会跳出一只老鼠,跳出的老鼠不管是黑是白都与这次谁输赢无关,但是如果最后公主都没抓到白老鼠,那么龙赢。设dp[i][j]为目前剩下i只白老鼠,j只黑老鼠时公主赢的概率。那么当j==0时,公主必赢,否则就有几种情况。dp[i][j] = ∑(公主直接拿到... 继续阅读 »
ACM

CodeForces 540D Bad Luck Island(概率dp)

CodeForces 540D Bad Luck Island(概率dp)
题目意思,剪刀,石头,布生活在一起,但是剪刀遇见石头石头会死掉,石头遇见布布会死掉,布遇见剪刀剪刀会死掉。给出你r,s,p分别代表剪刀、石头、布的数量。分别求剪刀石头布存在的概率。设dp[i][j][k]为目前还剩下i个石头,j个剪刀,k个布。此时存活的概率都是1。如果其中一种已经消失,那么剩下两个物种便可以肯定谁会存活。然后循环状态转移:double tot=i*j+j*k+k*i;dp[i-1... 继续阅读 »
ACM

HDU - 4089 Activation(概率dp,迭代)

HDU - 4089 Activation(概率dp,迭代)
题目的意思是,Tomato在排队激活游戏,有四种情况:1、注册失败,但是不影响队列顺序 ,概率为p12、连接失败,队首的人排到队尾,概率为p23、注册成功,队首离开队列,概率为p34、服务器崩溃,激活停止,概率为p4现在给出总排队人数n,Tomato排在第m个,一个数k,然后是四种情况的概率p1-p4;如果Tomato前面在k-1个人之内,并且服务器崩溃了,那么这种情况Tomato认为服务器是很l... 继续阅读 »
ACM

HDU 4336 Card Collector(概率dp,状态压缩)

HDU 4336 Card Collector(概率dp,状态压缩)
题目意思是,收集卡片,收集每张卡片的概率已经给出,并且所有的概率之和小于或等于1,问你收集完所有卡片的零食袋数的期望。这题很6啊,状态压缩,利用二进制的特性来枚举,但是有个坑啊,输出要是保留4位小数啊,题目最后说了啊(the standard answer is no more that 10^-4.)。假设现在一共要收集4张卡。那么:1111就代表收集了4张卡,1001就代表收集到了第一张和第四... 继续阅读 »
ACM

ZOJ 3380 Patchouli's Spell Cards(概率dp,组合数学)

ZOJ 3380 Patchouli's Spell Cards(概率dp,组合数学)
题目的意思是,给你m种元素,他们每个元素有n种不同的相位,如果相位相同则可以组合在一起发动一次魔法攻击(当然,一个也可以)。问你发动一次魔法至少有l种元素组合的概率?首先我是自己想的去找这些可能性,总数比较好找,就是n^m,但是发现当l>m/2时会有重复,而且不好去除。所以就看了题解。。。大家都是按照自己的理解为球填色。我是这样理解的,先画图:各个变量标识和题目意思相同,途中第一条黄色箭头代... 继续阅读 »
ACM

HDU3853 LOOPS(概率dp)

HDU3853 LOOPS(概率dp)
题目意思是一个人要拯救世界,穿过一个迷宫才可以。这个迷宫分为R*C个房间。你在每个房间里面施放一次魔法消耗两点魔法能量,然后有一定的概率在原地呆着,有一定概率往右走,有一定概率往下走。问你最后走出迷宫消耗魔力的期望值。简单dp,递推式:dp[i][j] = dp[i][j]*p[0] + dp[i+1][j]*p[1] + dp[i][j+1]*p[2];dp[i][j]代表当前处于第i行第j个格... 继续阅读 »
ACM

HDU 4405 Aeroplane chess(概率dp)

HDU 4405 Aeroplane chess(概率dp)
题目意思就是,你在下一盘飞行棋,飞行棋大家都下过吧。现在有n个点从1-N标号,你在0点,给你一个骰子,你抛出得到一个值就可以走到当前坐标+骰子的值的位置。但是有些地方是可以飞过去的。现在给出这些飞过去的坐标,问你走到终点n或者n+投骰子的期望?我们可以用一个数组保存航班信息,fly[i]=j,代表从i可以飞到j。同样扔出点数为x的概率为p,也就是1/6,递推式是:dp[i] = dp[fly[i]... 继续阅读 »
ACM

zoj 3329 One Person Game(带环概率dp,转化)

zoj 3329 One Person Game(带环概率dp,转化)
题目意思是你现在有三个骰子,die1,die2,die3,如果抛出die1=a,die2=b,die3=c,那么你你的积分清零,否则你的积分加上这个三个骰子之和。求你的积分大于n的期望?这个题比较有意思,就算你想到了递推式也很难想到转化,哈哈。首先我们假定当前积分是i,那么有递推式:E[i] = ∑(E[i+k]*p[k]) + E[0]*p[0] + 1     &... 继续阅读 »
ACM

POJ 3744 Scout YYF I(概率dp,递推,矩阵快速幂)

POJ 3744 Scout YYF I(概率dp,递推,矩阵快速幂)
题意:YYF要深入敌后,现在要经过一条地雷路,这些路上有很多的地雷(这些地雷都是长在地图上的,看得到,不用怕)。然后YYF有p的概率走一步,有1-p的概率跳两步。现在问你他安全走过雷区的概率是多少?自己先在草稿纸上画画就能推出递推式,比如我是这样画的:x ox _ ox _ _ o。。。。。。(注意,题目给的数据必定无序,所以先排序)x代表安全起点,o代表地雷,然后手动模拟概率就可以得出递推式:d... 继续阅读 »
ACM

POJ 2096 Collecting Bugs(概率dp)

POJ 2096 	Collecting Bugs(概率dp)
题目意思是有个人喜欢收集bug,然后现在的收集规则是这样的:一个软件的bug分为n类,软件还有s种子组件,找到一个bug有可能是n种分类中的一种并且还属于s种子组件里面的其中一个组件。问题是求:找出的bug有n种分类并且还存在于s种子组件里面。我们可以定义下一次找到bug的情况的四种概率(i为分类的变量,j为子组件的变量):下一个bug属于已经找到的i种分类,j种子组件 :p1= i*j/n*s;... 继续阅读 »