关键词:
1.codevs1060 搞笑世界杯
搞笑世界杯的球票出售方式也很特别,它们只准备了两种球票.A 类
票------免费球票 B 类票-------双倍价钱球票.购买时由工作人员通过掷硬币决定,投到正面
的买A类票, 反面的买B类票.并且主办方不可能倒贴钱,所以他们总是准备了同样多的A类票和B类票
你和你的朋友想计算一下排在队尾的两个人同时拿到一种票的概率是多少
(包括同时拿A 类票或B类票) 假设工作人员准备了2n 张球票,其中n 张A类票,n 张B类票,并且排在队伍中的人每人必须且只能买一张球票(不管掷到的是该买A 还是该买B).
思路:先说一个比较坑爹的事情,读入的是2n,不是n。f[i][j]表示第i人买票时买了j张A票的概率。对于j有三种情况:
1)j=0:f[i][j]=f[i-1][j]*0.5; 2)0<j<n:f[i][j]=(f[i-1][j]+f[i-1][j-1])*0.5; 3)j=n:f[i][j]=f[i-1][j]+f[i-1][j-1]*0.5。
初始化f[0][0]=1;输出f[n*2-2][n]*2(因为最后两张可以全是A或B);
#include<iostream> #include<cstdio> #include<cstring> using namespace std; double f[3000][3000]; int main() { int n,i,j; scanf("%d",&n);n/=2; f[0][0]=1; for (i=1;i<=2*n;++i) for (j=0;j<=n;++j) { if (j>i) continue; if (j==0) f[i][j]=f[i-1][j]*0.5; else { if (j<n) f[i][j]=(f[i-1][j]+f[i-1][j-1])*0.5; else f[i][j]=f[i-1][j]+f[i-1][j-1]*0.5; } } printf("%.4f ",f[n*2-2][n]*2); }
hdu4405概率期望dp
有0到n个格子。掷骰子走路,求出到终点的数学期望,有飞行的路线。dp[i]存储在i位置走到终点的期望。转移方程dp[i]=(dp[i+1]---->dp[i+6])/6+1; 有飞行路线则直接赋值#include"stdio.h"#include"string.h"dou... 查看详情
[填坑]期望概率dp入门级别
poj2096 CollectingBugs期望DP这道题是最入门的期望DP,然而我并不是很会做,甚至连题都没看懂。。(其实是English不好相信我)题解:在这里有s,n两个变量,假设dp[i][j]表示已经发现i种bug存在j个系统到期望天数所需要的天数,显... 查看详情
整理数学期望和概率dp
数学期望P=Σ每一种状态*对应的概率。因为不可能枚举完所有的状态,有时也不可能枚举完,比如抛硬币,有可能一直是正面,etc。在没有接触数学期望时看到数学期望的题可能会觉得很阔怕(因为我高中就是这么认为的,... 查看详情
poj2096collectingbugs(数学期望,概率dp)
问题:Ivanisfondofcollecting.Unlikeotherpeoplewhocollectpoststamps,coinsorothermaterialstuff,hecollectssoftwarebugs.WhenIvangetsanewprogram,heclassifiesallpossiblebugsintoncategories.Eachdayhediscoversex 查看详情
poj2096collectingbugs(概率dp,求期望)
CollectingBugsIvanisfondofcollecting.Unlikeotherpeoplewhocollectpoststamps,coinsorothermaterialstuff,hecollectssoftwarebugs.WhenIvangetsanewprogram,heclassifiesallpossiblebugsintoncategories.Eachdayhe 查看详情
codeforces-1264c-beautifulmirrorswithqueries-概率期望dp
一道挺难的概率期望dp,花了很长时间才学会div2的E怎么做,但这道题是另一种设法。https://codeforces.com/contest/1264/problem/C要设为(dp_i)表示第(i)个格子期望经过多少次,所以(dp_n+1=1)。https://www.cnblogs.com/suncongbo/p/11996219.html 查看详情
hdu4405-aeroplanechess(概率dp求期望)
Hzzlovesaeroplanechessverymuch.ThechessmapcontainsN+1gridslabeledfrom0toN.Hzzstartsatgrid0.Foreachstephethrowsadice(adicehavesixfaceswithequalprobabilitytofaceupandthenumbersonthefacesare1,2,3,4,5,6). 查看详情
hello2019d素因子贡献法计算期望+概率dp+滚动数组(代码片段)
...之后留下的n的期望,每次操作n随机变成一个n的因数题解概率dp计算出每个素因子留下的概率,乘以这个素因子的值就是这个素因子的贡献期望定义\(dp[i][j]\)为第i次操作后剩下j个素因子的概率,概率dp顺着推\(dp[i][j]->dp[i+1][k](k<= 查看详情
uva10529dumbbones(概率与期望,期望dp)带公式推导的题解(代码片段)
...r]最后一项是放置(+1)的骨牌所需要的次数,这里应用了“概率倒 查看详情
xsy1528azelso-概率期望dp(代码片段)
...行了。。。设$f_i$表示从$i$出发不回到$i$直接到达终点的概率,显然期望步数就是$frac1f_i$;考虑转移,设下一个事件概率为$p$,则如果下一个事件是敌人:$f_i=f_i+1*p$如果下一个事件是旗子:$f_i=(1-p)*( 查看详情
poj3071football(概率期望dp)
FootballTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 5620 Accepted: 2868DescriptionConsiderasingle-eliminationfootballtournamentinvolving2n teams,denoted1, 查看详情
cf148dd.bagofmice(概率dp||数学期望)
ThedragonandtheprincessarearguingaboutwhattodoontheNewYear‘sEve.Thedragonsuggestsflyingtothemountainstowatchfairiesdancinginthemoonlight,whiletheprincessthinkstheyshouldjustgotobedearly.Theyaredespera 查看详情
概率dp——逆推期望+循环迭代zoj3329(代码片段)
首先要推出dp[i]的期望方程,会发现每一项都和dp[0]相关,那我们将dp[i]设为和dp[0]有关的式子dp[i]=a[i]*dp[0]+b[i],然后再回代到原来的期望方程里然后进行整理,可以发现两个系数a[i],b[i]是可以逆推的,并且通过求出a[0],b[0]可以求出... 查看详情
概率期望dp
...你的朋友想计算一下排在队尾的两个人同时拿到一种票的概率是多少 查看详情
hdu4336cardcollector(状压+概率dp期望)题解(代码片段)
题意:每包干脆面可能开出卡或者什么都没有,一共n种卡,每种卡每包爆率pi,问收齐n种卡的期望思路:期望求解公式为:$E(x)=\\sum_i=1^kpi*xi+(1-\\sum_i=1^kpi)*[1+E(x)]$,即能转换到x情况的期望+x情况原地踏步的期望。因为n比较小,... 查看详情
poj3682kingarthur'sbirthdaycelebration(数学期望||概率dp)
KingArthurisannarcissistwhointendstosparenocoinstocelebratehiscoming K-thbirthday.TheluxuriouscelebrationwillstartonhisbirthdayandKingArthurdecidestoletfatetellwhentostopit.Everydayhewilltossacoi 查看详情
sgu495kidsandprizes期望概率dp(代码片段)
...盒子,每个盒子里面有一个披萨,现在进行m次放回的等概率拿取,若某一次拿到的盒子里有披萨就拿走披萨,但是空盒子仍然放回,问最后拿到披萨数目的期望数 由于正向考虑需要计算放回,故反向考虑。 对于每个盒... 查看详情
概率&&期望dp入门(代码片段)
~待填坑~ 先来了解一点儿概率和期望的基本知识:样本空间.事件和概率样本空间:样本空间$S$是一个集合,它的元素成为基本事件。样本空间的一个子集被称为事件,根据定义,所有基本事件互斥。概率:如果有一种事... 查看详情