题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1027题意：你面前有n个门，每一个相应一个数字，若为正xi。代表xi分钟后你会从它走出迷宫，负数则说明你会在-xi分钟后回到出发点且失去记忆。求出去的时间的期望。代码：#include<iost...

题目大意：求(1^K+2^K+3K+…+N^K)%2^32解题思路：借用别人的图能够先打表，求出Cnm,用杨辉三角能够高速得到#include<cstdio>typedefunsignedlonglongll;constintN=55;constllmod=(1LL<<32);structMat...

题目链接：http://lightoj.com/volume_showproblem.php?problem=1043题意：一个三角形ABC，DE//BC。已知三角形ADE和四边形BDEC的面积的比，求AD的长度。解法：二分AD边就可以代码：#include<stdio.h>#include<ctim...

Oneofmyfriendsisalwaysdrunk.So,sometimesIgetabitconfusedwhetherheisdrunkornot.So,onedayIwastalkingtohim,abouthisdrinks!Hebegantodescribehiswayofdrinking.So,letm...

1027-ADangerousMazePDF(English)StatisticsForumTimeLimit:2second(s)MemoryLimit:32MBYouareinamaze;seeingndoorsinfrontofyouinbeginning.Youcanchooseanydooryoulike.T...

题目链接题意：　　击球训练中，你击中一个球的概率为p，连续击中k1个球，或者连续击空k2个球，则训练结束。　　求结束训练所击球次数的期望。 思路：　　设f[x]为连续击中x个球，距离结束训练所需要的期望　　设g[x]为连续击空x个球，距离结束训练所需要的期望　　　　f[x]=p*(f[x+1]+1)+(1-p...

题目链接题意：　　一副牌，每个花色13张牌，加上大小王，共54张。　　遇到大小王可以代替其中某种花色。　　给定C,D,H,S。　　每次抽一张牌，问抽到C张梅花，D张方块，H张红桃，S张黑桃所需要的最小次数的期望。 思路：　　用dp[c][d][h][s][staues]表示当前有c张梅花，d张方块，h张红桃，...

题目链接题意：　　给一个数据大小为S的数据包，每一次发送需要K秒（单向），现在要从节点0发送到节点n-1。　　其中有n-1条路径，每条路径都有一个传输成功率。　　问传输成功所需最小时间的期望。 思路：　　最小时间的期望，即最大的传输成功率，最小的传输次数，即只传输成功一次所需要的时间的期望。　　利用dijks...

题目链接题意：　　有N个人，M个篮框，每个人投进球的概率是P。　　问每个人投K次后，进球数的期望。 思路：　　每个人都是相互独立的，求出一个人进球数的期望即可。　　进球数和篮框的选择貌似没有什么关系，所以给的这个M并没有什么卵用。。。。　　每个人进球数的期望为：E=sigma（i*C(K,i)*p^i*(1-...

题目链接题意：　　有n个街口和m条街道，你后边跟着警察，你需要进行大逃亡（又是大爱的抢银行啊），在每个街口你都有≥1个选择， 　　1）停留在原地5分钟。　　2）如果这个街口可以到xi这个街口，并且，通过xi可以遍历完所有未走过的街口，那么就加入选择。　　每个选择都是等概率的。　　求警察抓住你所用时间的期...

题目链接题意：　　给一个X*Y*Z 的立方体，每个单位立方体内都有一盏灯，初始状态是灭的，你每次操作如下：　　1）选择一个点(x1,y1,z1)　　  再选择一个点（x2,y2,z2）　　  将这两个点所形成的立方体内所有的灯全部转换状态（灭的变亮的，亮的变灭的）　　问...

题目链接题意：　　在孤岛生存，孤岛上有t头老虎，d头鹿，每天会出现随机出现两只生物（包括你自己），如果出现了一只老虎，那么你将被吃掉，如果两只老虎，则两只老虎会同归于尽，其他情况你都将生存下来。　　当孤岛上没有老虎时，就视为你生存成功。　　问你生存成功的最大概率。　　思路：　　仔细想一想，生存下来其实只和老虎有关，因为...

题目链接题意：　　若一年有n天，问至少需要多少个人才能满足其中两个人生日相同的概率大于等于0.5？ 思路：　　经典问题：生日悖论　　换成其互斥事件：m个人，每个人生日都不相同的概率≤0.5时最小人数。　　这就是邮票收集问题的变形：每个邮票至少出现一次的概率小于等于0.5　　等价于：　　　　　　找到最小的...

题目链接题意：　　抢银行（这个背景最爱了），有n家银行，每家银行抢劫被抓的概率是p[i]，你认为当你被抓的概率低于P的时候是安全的。　　问，你最多能抢劫到多少money。 思路：　　抽象成背包问题，每家银行只有两种选择，要么抢，要么不抢。　　被抓的概率有点难求，因为还要考虑之前没有被抓。这里换成求互斥事件：不...

题目链接题意：　　给一个数n，每次操作是随机的选择一个[1,N]区间内能够被n整除的数进行除法，然后得到一个新的n。　　问n变成1时的期望操作次数。　　　　思路：　　设E[n]为当数为x时，变成1期望的次数，则有转移方程。　　E[n]=sigmaE[n/x[i]]/k+1（x[i]为能被n被整除的数），k为n在区间[1...