Mr.K 018

没人来看啊……感觉这个题应该没那么难了吧？

其实原则上不是，这里是为了出题做的简化 而且实际上不按顺序搭会带来其他问题……我这个K后来觉得还是一个个搭好一点

我在想，修改题目中的条件，改成不必只有最后才能回家，而是随时可以回家放东西，出来后身上的重量值回到1，这个题是变得简单了还是更复杂了

附加题是我真的想在生活中这么优化一下，所以并没有考虑复杂度（ 那这么看，恐怕只能分支限界一下

第24期终于来了…… 快到期末了，下一期啥时候能出还是个未知数…… 嘛，好歹这一期出来了不是么？ 今天这道题其实是个操作系统题，题本身不太难。 第24期 我的世界2 K上一次在MC里搭了个奇观（雕塑）之后，这次又想再搭一个奇观。这次他要搭一个像素画。他这个人其实没什么美术细胞，所以搭像素画的方式跟别人不太一样：首先写了个程序，用一些（可以再水出一期算法挑战的）技术手段导出了一张表格，告诉他每一格该搭什么方块。之后，把要搭的图像输入进去，拿到表格，对着表格搭像素画。 K按照表格搭像素画的时候，发现他的快捷栏不够大，只能容纳9个方块，因此下一个要搭的方块常常没有出现在快捷栏里面。这时只能去方块表里找，找到对应的方块之后再放在快捷栏里的某个位置（那个位置里如果原先有方块，就被换掉了）。众所周知从方块表里找一个特定方块是非常麻烦的，因此K打算尽可能减少从方块表里找方块的数量。 现在告诉你像素画某一行的各个方块分别是什么，快捷栏初始时是空的。试问K最少需要从方块表里找多少次方块？ 输入 第一行两个整数m n，m表示有多少种方块，n表示要处理的方块数量，即像素画这一行的长度。满足0<m<1000, 0<n<100 000。 （不要问为什么要摆那么多方块，问就是盖奇观） 接下来n行，每行一个整数a_n，表示这个位置的方块种类，满足0<=a_n<m。 输出 一个整数，表示找方块的最少次数。 以上。另外还有一道附加题，和上次一样，不保证存在多项式时间的解这个题根本就是不存在了吧（。 要从家里出去去若干个地方买东西。不妨认为家在(0,0)处，其余的商店都在平面上的某个位置。由于街巷和建筑物的限制，在两个点之间移动只能横平竖直地移动。出发时携带了质量为1单位的物品，每个商店都有一个质量值，表示到那个商店后身上另外携带的质量。从家里出发，要访问所有的商店后再回家。定义每段路的体力花费为路程和携带质量的乘积。 试求一个访问商店的序列，按这个顺序访问商店，总的体力花费最小。 --------------1705更新-------------- 经 @yhz012 的提醒，基本确定这个附加题是个NP完全问题

是的 空气阻力的话这次先这样吧2333

大家好我不是ZERC，但是我看最近每日挑战系列大家好像都没怎么更（对说的就是你，K018），所以我来越俎代庖，发一份数学挑战。（不，不是因为懒得动脑子） 众所周知我不是搞数学的，所以我是出不来那么难的题目的。本题的难度大概在真正的每日数学挑战的题目1和题目2之间。下面是题目： 有一门大炮，可以将炮弹以大小恒定的初速度v发射出去，v与地面的夹角θ可以调节。炮弹质量为m，受阻力与速度成正比，比值为k。本题中的地面是水平面，没有起伏。不妨认为大炮位于坐标原点，指向第一象限开炮，并令y轴正方向为上方。 1）炮弹的运动轨迹是什么？ 2）炮弹落点（轨迹与x轴交点）的横坐标？ 3）求一角度θ∈(0,π/2)，使得落点距离大炮的距离最远。

只能说…… 这个“凭什么”用的就很好，猜猜看这次疫情过后这个卡卡是会赖自己不争气还是会赖别人鼓捣出疫情来把他家毁掉？ 正常人都会选择后者吧，我看这位就算他们家是正常经营不善倒掉的，估计也赖不到自己头上 没有人是阿Q，又或者人人都是阿Q

的确，因为这个限制并不是我加的，而是客观要求，今天这个附加话题是某个更大话题的一部分

听上去不错，详细说说？

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

原则上没有

第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 附一个生成的文法树：