开发
Codeforces Round #321 div2
好像前几场的题解忘记写了，Orz状态太差，平均出两题 都不好意思写了，连掉4场，都要哭晕了。很水的一场，写完ABC就去睡了 D题其实不难，E题研究Ing（已用一种奇怪的姿势AC了） Problem_A:题意： 给一个长度为n的序列，找出最长不下降子序列。 思路： 线性扫一遍，...
Codeforces Round #316 div2
一场充满血腥hack之战！！！Problem_A：题意： n个候选人在m个城市进行投票，每个城市选出票数最多的一个候选人为城市候选人，如果票数相同，则取编号小的候选人。 再从这m个城市候选人中选出重复次数最多的，如果有相同的，则取编号小的候选人。 思路： 选出每个城市的最高票数，然后找出重复次数最多的即...
LightOj_1364 Expected Cards
题目链接题意： 一副牌，每个花色13张牌，加上大小王，共54张。 遇到大小王可以代替其中某种花色。 给定C,D,H,S。 每次抽一张牌，问抽到C张梅花，D张方块，H张红桃，S张黑桃所需要的最小次数的期望。 思路： 用dp[c][d][h][s][staues]表示当前有c张梅花，d张方块，h张红桃，...
LightOj_1408 Batting Practice
题目链接题意： 击球训练中，你击中一个球的概率为p，连续击中k1个球，或者连续击空k2个球，则训练结束。 求结束训练所击球次数的期望。 思路： 设f[x]为连续击中x个球，距离结束训练所需要的期望 设g[x]为连续击空x个球，距离结束训练所需要的期望 f[x]=p*(f[x+1]+1)+(1-p...
LightOj_1321 Sending Packets
题目链接题意： 给一个数据大小为S的数据包，每一次发送需要K秒（单向），现在要从节点0发送到节点n-1。 其中有n-1条路径，每条路径都有一个传输成功率。 问传输成功所需最小时间的期望。 思路： 最小时间的期望，即最大的传输成功率，最小的传输次数，即只传输成功一次所需要的时间的期望。 利用dijks...
LightOj_1317 Throwing Balls into the Baskets
题目链接题意： 有N个人，M个篮框，每个人投进球的概率是P。 问每个人投K次后，进球数的期望。 思路： 每个人都是相互独立的，求出一个人进球数的期望即可。 进球数和篮框的选择貌似没有什么关系，所以给的这个M并没有什么卵用。。。。 每个人进球数的期望为：E=sigma（i*C(K,i)*p^i*(1-...
LightOj_1284 Lights inside 3D Grid
题目链接题意： 给一个X*Y*Z 的立方体，每个单位立方体内都有一盏灯，初始状态是灭的，你每次操作如下： 1）选择一个点(x1,y1,z1) 再选择一个点（x2,y2,z2） 将这两个点所形成的立方体内所有的灯全部转换状态（灭的变亮的，亮的变灭的） 问...
LightOj_1287 Where to Run
题目链接题意： 有n个街口和m条街道，你后边跟着警察，你需要进行大逃亡（又是大爱的抢银行啊），在每个街口你都有≥1个选择， 1）停留在原地5分钟。 2）如果这个街口可以到xi这个街口，并且，通过xi可以遍历完所有未走过的街口，那么就加入选择。 每个选择都是等概率的。 求警察抓住你所用时间的期...
LightOj_1265 Island of Survival
题目链接题意： 在孤岛生存，孤岛上有t头老虎，d头鹿，每天会出现随机出现两只生物（包括你自己），如果出现了一只老虎，那么你将被吃掉，如果两只老虎，则两只老虎会同归于尽，其他情况你都将生存下来。 当孤岛上没有老虎时，就视为你生存成功。 问你生存成功的最大概率。 思路： 仔细想一想，生存下来其实只和老虎有关，因为...
LightOj_1104 Birthday Paradox
题目链接题意： 若一年有n天，问至少需要多少个人才能满足其中两个人生日相同的概率大于等于0.5？ 思路： 经典问题：生日悖论 换成其互斥事件：m个人，每个人生日都不相同的概率≤0.5时最小人数。 这就是邮票收集问题的变形：每个邮票至少出现一次的概率小于等于0.5 等价于： 找到最小的...
LightOj_1079 Just another Robbery
题目链接题意： 抢银行（这个背景最爱了），有n家银行，每家银行抢劫被抓的概率是p[i]，你认为当你被抓的概率低于P的时候是安全的。 问，你最多能抢劫到多少money。 思路： 抽象成背包问题，每家银行只有两种选择，要么抢，要么不抢。 被抓的概率有点难求，因为还要考虑之前没有被抓。这里换成求互斥事件：不...
LightOJ_1038 Race to 1 Again
题目链接题意： 给一个数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...
LightOJ_1248 Dice (III)
题目链接题意： 给一个质地均匀的n的骰子，求投掷出所有点数至少一次的期望次数。 思路： 这就是一个经典的邮票收集问题（CouponCollectorProblem）。 投掷出第一个未出现的点数的概率为n/n=1，因为第一次投掷必然是未出现的。 第二个未出现的点数第一次出现的概率为(n-1)/n，因为有...
LightOj_1342 Aladdin and the Magical Sticks
题目链接题意： 地上有n种棍子，其中有两种类型，一种类型是可识别，一种类型是不可识别，每个棍子都有一个权值。 当你捡到可识别的，那么你以后就不会再捡这个棍子，如果是不可识别的，那么你有可能还会捡。 问将所有棍子收集完的权值的期望。 思路： 此题借鉴参考了此篇文章：AladdinandtheMagica...
Codeforces Round #Pi (Div. 2)
上次比完赛就准备写了，结果懒癌发作了，拖到了现在。Problem_A：题意： 在一条x轴上有n座城市，每个城市之间的距离就是它们对应坐标的距离，现在求出每个城市到其他城市的最近距离和最远距离。 思路： 最远的必然在最左右端点产生，因为没有比它们还远的城市了。 最近的必然在相邻左右端点产生，因为有没比它们...
