C++
uva_1422 Processor
题目链接题意： 有n个任务，每个任务要在规定的时间[l,r]内完成，工作量为w，每个任务可以分开完成。 求，使得所有任务都完成的最大速度的最小值。 思路： 最大值最小问题，二分。 因为是要完成所有任务，所以先按开始时间排序，接下来二分速度。 因为任意两个任务之间的关系只有两种，1）相交或者包含2）相...
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_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座城市，每个城市之间的距离就是它们对应坐标的距离，现在求出每个城市到其他城市的最近距离和最远距离。 思路： 最远的必然在最左右端点产生，因为没有比它们还远的城市了。 最近的必然在相邻左右端点产生，因为有没比它们...
Codeforces Round #315 (Div. 2)
这次可以说是最糟糕的一次比赛了吧，心没有静下来好好的去思考，导致没有做好能做的题。Problem_A:题意： 你要听一首时长为T秒的歌曲，你点击播放时会立刻下载好S秒，当你听到没有加载到的地方时，就会重头听，直到可以听完整首歌， 由于网络堵塞，你在q秒内只有q-1秒用于下载，问需要重新多少次，第一次点击播放也算。&...
LightOj_1030 Discovering Gold
题目链接 题意： 在一个1XN的格子上，每个格子都有一定的黄金，你从第一个格子出发，问到最后一个格子得到黄金的期望。 每次前进使用骰子投点来决定前进步数，如果投出的点前进后会超过N，那么就重新投掷。 思路： 很直接的期望题。 概率dp求期望是从后往前求，每次的概率为1/6. dp[i]=1...
Uva_11762 Race to 1
题目链接题意： 给一个数n，每次从小于等于n的素数里选一个P，如果能被n整除，那么就n就变成n/P。 问：n变成1的期望。 思路： 设小于等于n的素数有p个，其中是n的约数的有g个。 则E[x]=1+1/p*(1-g/p)+sigma(i=0,1,2, g)num[i]*1/p。...
Uva_11427 Expect the Expected
题目链接题意： 你玩纸牌，如果当天晚上你赢的局数比例大于p，就去睡觉，第二天继续。如果小于等于p，就去睡觉，并且以后都不玩了。 每晚最多玩n局，每局赢的概率为p，求玩的天数的期望。 思路： 设dp[i][j]为玩了i局，赢了j局的概率。 则期望E=sigma(i=0,1,2,3,4,........)...
Codeforces Round #313 (Div. 2)
大半年没有打Codeforces，昨天开始恢复打Codeforces，简直是，欲语泪先流啊。手残到爆的写错了范围，手残的数漏了条件，简直不能直视，最坑爹的是，E题没时间写代码了。题目链接Problem_A: 题意： 给n个数，每个数可以用无限次，求用这些数的和表示不出来的最小的正整数，没有则输出-1.思...
