Mr.K 018

听上去不错，详细说说？

确实 其实今天本来想出一个类似的题来着，但是就卡在这里，感觉没什么好方法

原则上没有

第23期哦！话不多说，看题： 第23期 倒饮料 MrK-018和MrK-019有一天出去吃饭，点菜的时候另点了一扎饮料。这两个人都比较抠，因为是AA制结账，所以两个人都想刚好喝到一半的饮料。桌上有两个形状不同的杯子没有用过，可以拿来倒饮料。两个杯子和装饮料的扎都没有刻度，因此只能把杯子/扎倒空或者倒满。 已知两个杯子和扎的容量（整数，单位为毫升），饮料送上来的时候扎是满的。试问，如何倒饮料，才能做到均分饮料（某一个容器中存放的饮料刚好是送上来的一半）？ 输入 一行三个整数a b c，分别表示扎和两个杯子的大小。 输出 若能做到，就输出一个可以均分饮料的倒饮料的序列，如下所示： a > b b > c 表示把饮料从扎里倒进杯子1，再从杯子1里倒进杯子2. 若不能做到，输出一行Not possible。 以上是今天的题目。另有一个我现在在考虑的问题，发出来供大家讨论： 给定一张带边权的有向图（保证边权都是正的），给定图上的某个顶点，试求一条经过这个顶点的环路，且途径边的边权的平均值最小。 附加题并不是在出之前已经想好答案或者确定有答案的，因此它可能有多项式时间的解也可能没有，请各位留意。

甚至不用维护closed list，反正不上多线程，直接在地图上修改就行了

这个题数据量没那么大，我记得正解就是布鲁特·福斯算法（

题意其实是输出操作序列，而不是out一个结果…… 不过挺不错的，程序也很完整

第22期！ 可怜的MrK-019又被汉化组抓住了，他能不能摆脱被吃的命运呢？救救019 保护019，人人有责 第22期 汉化组的吃人陷阱2 汉化组布下的上一个吃人陷阱没能成功地吃到MrK-019，这一次汉化组升级了他们的陷阱！ 汉化组布下的陷阱和上一次的差不多。一种格子迷宫，只有一个出口。迷宫大概是这样的： ###### #K...# ####.# #S...# ###### 如图所示，图上标为#的地方都是墙，标.的地方都是可以走的部分。MrK-019初始所在的地方也是可以走的部分。MrK-019一秒可以走一格。出口只在某一秒开放，平时都是不能走的墙；如果MrK-019在出口开放的那一秒到达出口，他就能逃脱汉化组的吃人陷阱，否则就会被抓住吃掉（指调教成无情的汉化机器）。同时，由于汉化组的人就在后面穷追不舍，MrK-019必须不停地移动才行！ 另外，汉化组升级了他们的陷阱，MrK-019走过的地方就不能再走！ MrK-019能不能再一次从汉化组的吃人陷阱中逃出来呢？ 输入 第一行是三个整数m,n,s，分别表示迷宫的长和宽，以及出口在第几秒开放。 接下来是一个m*n的字符矩阵，表示汉化组设下的迷宫。格式见题干和输入样例。 输出 如果MrK-019能逃出来，就输出一行Yes，否则输出一行No。 样例输入1 5 6 8 ###### #K...# ####.# #S...# ###### 样例输出1 Yes 样例输入2 5 6 10 ###### #K...# ###..# #S...# ###### 样例输出2 No

是吗？ 那我以后出简单一点吧

可是有一说一，我也没召来几个魔鬼啊…… 你看一共就四个人回，两个都是说骚话的，还有一个卖弱的

没事，不懂编译原理就用ANTLR硬上

这个题DFA实际上是不够的（笑 需要下推DFA才行，就是DFA加一个符号栈

没错，你已经在名单（指参与者名单）里了 这个题其实跟上一期是同一道题，区别无非是语法的复杂程度不同 当然，这并不意味着这个题是个表达式求值（

第21期来啦！本题是接着第20期继续出的一道题，所以本题要连着20期的题干一起读。 第21期 冰系魔法2b 各位已经见过了基本款的魔法骰子。实际上，魔法骰子还有更多改进款，支持很多更为复杂的功能。之前说的异世界来客就有这么一款骰子，她向我们展示了这个骰子的用法。 这个骰子依然可以像前一款那样计算表达式。它一次可以顺序处理多个掷骰表达式，每个掷骰表达式都需要用分号;结尾。同时，这个骰子还支持流程控制（不愧是魔法师的骰子），就是if，while和for语句。同时，多个语句还可以用大括号括起来，成为一个语法上的整体。它们的语法也不复杂，上例子： r1d6; if (r1d6-3) { while(r1d6-3) 15; (r3d20)*(r1d6); } else for(r1d6) if(r12d10-60) 1+1; r2d6; for (5) { r1d2; } 我们的异世界来客是个冰元素使，这个魔法骰子的语法和她魔法咒语的语法很接近，所以她很喜欢这个骰子。唯一美中不足的是，这个骰子没有判断输入是否合法的能力。如果输入了不正确的掷骰程序，魔法骰子就可能坏掉。因此，她打算编制一个魔法，可以预先判断输入是不是合法的。 输入 一段魔法骰子的输入程序。 输出 如果输入程序合法，就输出一行OK，否则输出一行Fail。 样例输入 r1d6;if (r1d6-3){while(r1d6-3) 15; (r3d20)*(r1d6);}else for(r1d6) if(r12d10-60) 1+1;r2d6;for (5){ r1d2;} 样例输出 OK 读到这里的朋友，是不是觉得这个题里魔法骰子的语法似曾相识？没错，这个语法是有意仿照C语言函数定义的部分来编制的。把rd运算符改成别的C语言运算符之后，甚至可以在C语言里跑起来（当然，要放在某个函数的函数体里才行，而且后面要加上return）。其实C语言的语法没那么难，不是么？ 另外，总觉得今天这道题，非相关专业的学生应该不太好答出来了……那么，如果觉得自己不太会答这个题，那么可以试试ANTLR4. 微型召唤阵： @yhz012

这就是为啥我要设置一个运算符rd（笑 没错，就是为了给标准的表达式求值板子制造困难

我本来想说这里有一个文法二义性的问题来着，后来拿antlr4跑了一遍发现其实没有 因为运算符rd的优先级没有运算符*高，所以*会先算，因此实际运算是2 附一个生成的文法树：

看大佬讨论问题，流下了不懂数学的泪水…… 前三问都可以直接计算的，大不了O(n^5)嘛，有些情况下多项式时间已经不错了，参考我上午的回答和其他人的讨论 后面两问暂时没想出来有效的算法，因此考虑走个邪道：GA 先随机初始化n个解当作初始种群，然后迭代执行以下操作： 1. 对种群中的每个解打分 2. 按一定比例去掉打分最低的解。设去掉了n个解 3. 进行n次繁殖，补回去掉的解。繁殖方法可以是随机抽取两个解（解的评分越高，被抽中的概率也应越高），两个解的编码做适当的交叉互换，并按一定概率突变以后作为新的解加入到种群中。 重复以上迭代操作直至收敛或执行完了指定的轮数或时间为止。 要解决以下几个问题： 1)评分算法。考虑进行若干次模拟，统计因中陷阱而GG的情况的占比，作为评分。考虑到计算代价，模拟次数似乎不必做特别多，几十次就行？ 2)解的编码。假设要挖出k个坑，考虑将每个坑的位置用一个整数表示。不必从小到大排列。 3)交叉互换和突变。考虑将交叉互换算法设置为：对每一个子代基因编码中的整数，均随机地从两个亲本的对应数字中抽出一个。如果出现重复数字，则将其中一个赋随机值。突变可考虑设置为将某一个数字赋上随机值。 --- 这个算法不知道行不行得通，但是调参多半是没跑了

（尴尬） emmm好像是这样的

其实一样，把d当成一个优先级比加减号还低的运算符就行

p'[k][j]求法跟p[k]差不多，唯一的区别是到p'[k][k]的值强行设为0，跟其他地方的运算规则不一样 同样的道理适用于p(n)[k]1[k]2⋯[k]n

第一问跟楼上说的一样，设p[k]表示踏上第k个台阶的概率，dp一下取出最大的那个就行。 第二问我觉得可以把第一问的算法做修改，设p‘[k][j]表示在已知第k个台阶没有被踏上的情况下，第j个台阶被踏上的概率。这样，假设要在k,j位置挖坑，那么访客掉坑里的概率就是p[k]+(1-p[k])p'[k][j]。O(n^2)搞定 我觉得推广到埋n个坑的情况应该也差不多 如果在上文看到了i，请把它理解成k（ 是否可以尝试证明用这种方法连续挖六个坑肯定能行呢？正在尝试，感觉能行

仅就这个题而言，可以把所有的r都丢掉，然后把d当成运算符 冰系魔法系列的题实际上都是编译原理来着。刚学数据结构的话，可以考虑把整个表达式当成一颗树来看待 另外，不要忘记数字有两种表示方式哦

那行，那明天我就不出算法挑战21了，计划通（不是 期待明天的概率论

什么，你要出概率挑战？那正好我咕几天（x

确实，我马上改