题目链接题意: 在孤岛生存,孤岛上有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被整除的数...
题目链接题意: 给一个质地均匀的n的骰子,求投掷出所有点数至少一次的期望次数。 思路: 这就是一个经典的邮票收集问题(CouponCollectorProblem)。 投掷出第一个未出现的点数的概率为n/n=1,因为第一次投掷必然是未出现的。 第二个未出现的点数第一次出现的概率为(...
题目链接题意: 地上有n种棍子,其中有两种类型,一种类型是可识别,一种类型是不可识别,每个棍子都有一个权值。 当你捡到可识别的,那么你以后就不会再捡这个棍子,如果是不可识别的,那么你有可能还会捡。 问将所有棍子收集完的权值的期望。 思路: 此题借鉴参考了此篇文章:Aladdinan...
上次比完赛就准备写了,结果懒癌发作了,拖到了现在。Problem_A:题意: 在一条x轴上有n座城市,每个城市之间的距离就是它们对应坐标的距离,现在求出每个城市到其他城市的最近距离和最远距离。 思路: 最远的必然在最左右端点产生,因为没有比它们还远的城市了。 最近的必然在相邻左右端点...
这次可以说是最糟糕的一次比赛了吧,心没有静下来好好的去思考,导致没有做好能做的题。Problem_A:题意: 你要听一首时长为T秒的歌曲,你点击播放时会立刻下载好S秒,当你听到没有加载到的地方时,就会重头听,直到可以听完整首歌, 由于网络堵塞,你在q秒内只有q-1秒用于下载,问需要重新多少次,第...
题目链接 题意: 在一个1XN的格子上,每个格子都有一定的黄金,你从第一个格子出发,问到最后一个格子得到黄金的期望。 每次前进使用骰子投点来决定前进步数,如果投出的点前进后会超过N,那么就重新投掷。 思路: 很直接的期望题。 概率dp求期望是从后往前求,每次的概率为1/6...
题目链接题意: 你在一个迷宫里,开始的时候你面前有n个门,选择每个门的概率相等,有两种结果: 1)回到|x|分钟之前(x为负时) 2)x分钟之后出迷宫(x为正时) 每次回到|x|分钟之前,你都记不得你曾经选过哪扇门 问走出迷宫所用时间的期望。 思路: 因为每次都不记得曾经的选择...
题目链接题意: 给一个文档,这个文档由yes、no组成,共有s个byte,共有n个yes、no。 假设yes的个数为yes_num,no的个数为no_num。 将这n个数进行排列,对于每个排列,将其右移一个结果,并在最左端补上yes,再将其与原排列进行对比,看有多少个不同的。 ...
SublimeText3,一款不错的文本编辑器,加上各种插件和IDE就能化身各种语言的编译器,界面以及多种插件的灵活组合搭配更是让程序员们在码代码这种枯燥的生活中增加一点调剂。 下载地址 点击DownLoad下的windowsorwindows64bit如果你的系统是32位,那么点击前者。 ...
题目链接题意: 给一个数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)n...
题目链接题意: 两个人坐火车,在某个城市到站的时间段分别为[t1,t2],[s1,s2],停在站台的时间均为w。 问,若两人能见面的概率。 思路: 一道基础的几何概型,p=s(m)/s(n)。 令x1=t1,x2=t2。 令y1=s1,y2=s2。 这样这四条直线就围成一个矩形...
题目链接题意: 你玩纸牌,如果当天晚上你赢的局数比例大于p,就去睡觉,第二天继续。如果小于等于p,就去睡觉,并且以后都不玩了。 每晚最多玩n局,每局赢的概率为p,求玩的天数的期望。 思路: 设dp[i][j]为玩了i局,赢了j局的概率。 则期望E=sigma(i=0,1,2,3,4...
指针生成网络(Pointer-Generator-Network)原理与实战 阅读目录 0 前言 1 Baseline sequence-to-sequence 2 Pointer-Generator-Network 3 Coverage mechanism 4 实战部分 4.1 DataSet 4.2 Experiments 4.3 Evaluation 4.4 Results 5 References 回到顶部 0 前言 本文主要内容:介绍Pointer-Gen...