yhz012

艹233居然真的开始炼丹了 感觉似乎可以跑，不过感觉可能很容易卡在suboptimal里 常规方法的话，作为提示，先考虑下如果早苗只能挖2个陷阱的时候，参拜客有2条命，要怎么挖？ 然后扩展成3陷阱，2命的情况 最后是5陷阱，2命 实际上计算复杂度还是能在O(n^5)的级别，只是比之前的O(n^5)的系数要大很多

从实验结果来说其实除了最后一道题，其他的问题可以比这个限制的更多。但是问题还是必须要严格证明才能用这个性质…… 对于单个坑很显然会趋于2/7，但是多个坑的情况前面会影响后面的坑，这里就不是很好说了……

问题是你要证明增加台阶后面的概率也不会超过前面，举例来说，如果我只有5个台阶，那挖2个陷阱的答案和6个台阶挖2个陷阱的答案（挖5、6）肯定不一样，因为根本就没有第六个台阶。 数学一点的说法就是你要证明这个函数在某一点之后是凸的，或者至少是不大于之前的最大值的。我个人从结果来看证明是凸的可行性似乎比较大

实际上2、3问我就是这么算的（x 规律这事，你也需要证明这个规律对于任意更多的台阶也一样符合

实话来说我现在用的方法是O(n^5)的，不过从结果来看应该有变成常数级的方法，但是应该要一些数学基础证明一些性质

算了一下，如果我没算错的话，并不是第5个台阶和第6个台阶 我index标歪了，非常抱歉，答案是对的

那么p'[k][j]要怎么求呢？

猜对了233居然反倒这个问题先被猜出来了答案233

第一问没问题 第二问和第三问是有精确解的，贪心取第一个之后，“去掉这一个解”的意思是？另外如果要用贪心的话，需要先证明贪心的正确性，即部分最优是全局最优？ 第四问第五问和23问还是有一些区别的，2、3问的情况是一次就会死，所以不需要考虑连续踩坑的问题，但是4和5就不得不考虑了 极端一点的例子是，假设我埋6个坑，那1命的情况下，毫无疑问连挖6坑是最优解，但是2命的情况或许并不是最优解？

第一期 年久失修的博丽神社 为了争取更多的信徒，东风谷早苗决定在博丽神社外的台阶上挖陷阱来阻碍人们前往博丽神社。现已知博丽神社外台阶共有100阶，参拜客从山脚下（即第0个台阶）开始上山，每次有各1/6的概率爬1、2、3、4、5、6阶。 1. 早苗是在凌晨3点想到的这个巧妙的办法，到日出之前只够挖1个陷阱的时间，请问早苗应该把这个陷阱挖在第几个台阶才更可能坑到参拜客？ 2. 早苗决定等第二天晚上用一整晚时间挖陷阱，她一晚上可以挖2个陷阱，请问早苗应该把这两个陷阱分别挖在第几个台阶才更可能坑到参拜客？ 3. 早苗决定利用河童重工的技术，一晚上挖5个陷阱，请问早苗应该把这些陷阱分别挖在第几个台阶才更可能坑到参拜客？（显然挖6个的话连挖6个肯定就坑死人了，所以5个是最复杂的情况了） 4. 众所周知，幻想乡是有残机这个概念的，被陷阱坑了一次也不会没命。假设参拜客都是被坑了两次才会没命，请问早苗应该把这5个陷阱分别挖到第几个台阶才更可能坑到参拜客？ 5. 如果参拜客被坑3次才会没命的话，请问早苗应该把这5个陷阱分别挖在第几个台阶才更可能坑到参拜客？ 运算量估计会比较大，不要求给出精确解，给出具体计算思路（或者伪代码）即可。 召唤阵 @Mr.K 018 @ZERC @alan00290

R x D y不算三目吧，某种意义上你可以把r丢掉，视作x D y这个运算，就是正常的中间运算了 换个说法 s R x D y t= s (x) D y t，就是把r和d之间加个括号，然后d视为双目运算符就可以了

正好明天北京时间中午12点我DDL结束，然后可以开始摸鱼（x

不过我预定的第一期大概会合你之前出的飞行棋会有很大相关（笑 预计会有3个子问题？ 所以说，叫八云紫的时候千万不要叫紫ma@(#*&)

别啊，真的会死人的，而且汇编我真的是本科唯一一科差一点挂了的课啊

数学就是魔法（指让人头疼的程度 下一题就变成把java翻译成汇编了吧

单说表达式求值其实倒是能改写成逆波兰表示法然后用栈带走吧……

其实就是出题大失败www 所以我决定今天先来个简单点的问题好了（x 什么，今天已经有编程挑战了？那我就先咕几天（x

三门的话，其实另外一个符合常识的理解是 蕾米莉亚碰到的不是读心妖怪古明地觉，而是幕后黑手八云紫。 蕾米莉亚现在有两种选择： 1.装作无事发生，直接去已经选定的地下室。 2.和八云紫说，“我现在随机在3个地方选了一个，是地下室。紫你用隙间去这三个地方看一下我是不是猜对了。” 如果炸弹不在地下室，那八云紫会直接告诉蕾米炸弹真正的位置。但是如果炸弹在地下室，八云紫会觉得自己的每日24小时精致睡眠被打扰了，所以会暴揍蕾米一顿，顺手亲自把红魔馆拆了。 显然一开始选对了的概率只有1/3。所以这时候选1只有1/3概率避免红魔馆被爆破，而选2除非炸弹真的在地下室（概率1/3），不然（概率2/3）八云紫会帮忙拆炸弹。 实际上选项1就是不换门，而选项2就是换门。

所以我题干没有表现出古明地觉是随机的在没选中，也没炸弹的地方随机说了一个 以及蕾米最开始选地下室也应该是随机的 本来我是想描述成三门的，看来正式题我应该尽量避免这种比较容易歧义的描述方法了 是咱描述的锅，咱背锅 你看看蕾米已经抱头蹲防了，放过红魔馆吧（x 实际上我是想试水的就是问三门问题的分析啦www

是我表述不清楚，因为三门实际上非常依赖1.主持人是否知道奖品在哪，2.主持人是否避开奖品开门，3.主持人是否避开选择的门开门。但是我忘了说本身主持人开门要在不是奖品或选择的门里面去随机挑了

等下我觉得我大概要重修语文了，我实际想描述的其实是三门啊…… 下次出题我应该控制一下情景表述了 这句话我本来想表达的就是在没被选择的（除了地下室之外），里面打开一个确定是羊（没有炸弹）的门……

为什么会变成这个样子呢.jpg 为什么会变成千层面呢 车万角度论述有理有据，回答正确（艹

老千层面了，下次我应该换恋恋出来说，这样就避免了千层面的结局 不小心二连了，抱歉 或者我应该改标题叫 每 周 博 弈 挑 战

为了避免场景误导，你可以假设魔理沙在3个地方放炸弹的概率是一样的 不存在为了之后继续偷书不舍得炸图书馆的情况 古明地觉是读心的妖怪，所以她知道蕾米莉亚要去地下室 古明地觉刚才见过了魔理沙，也知道了魔理沙把炸弹放在了哪里 古明地觉想看爆炸，所以她不会告诉蕾米莉亚炸弹是否在地下室 古明地觉又觉得蕾米莉亚太可怜了，所以告诉她剩下的图书馆和门卫室这两个选项里，图书馆是没有炸弹的

毫无价值的前言 不出意外的话，以下规则适用于之后的每一期（如果有的话） 1. 解析解数值解均可 2. 解析解需要给出公式推导 3. 数值解要给出数值解的计算方法（有伪代码或者代码最好） 所以今天就先来试个水，出个经典问题好了 第零期：今天红魔馆炸了吗 为了掩盖自己盗书的罪证，魔理沙在红魔馆安放了定时炸弹。威严满满的蕾米莉亚准备亲自拆炸弹，她发现一共有3处可疑的地方，分别是门卫室、图书馆和地下室。爱妹心切的蕾米莉亚正准备前往地下室时，路过的古明地觉看到蕾米莉亚正准备前往地下室去找炸弹。古明地觉告诉蕾米莉亚，她刚才遇到了魔理沙，所以知道定时炸弹在哪。她也知道蕾米莉亚正要去地下室找炸弹，不过她又想看每天一次的炸红魔馆，所以她不会说炸弹在不在地下室。不过又觉得无辜的蕾米莉亚只能抱头蹲防的样子太可怜了，所以可以告诉蕾米莉亚，在剩下两个地方里，图书馆是肯定没有炸弹的。请问这时候，蕾米莉亚为了避免红魔馆被爆破，她应该去门卫室呢，还是该去地下室呢？ 召唤阵 @Mr.K 018 @ZERC @alan00290