Mr.K 018

本期是周末特辑，是今明两天的题目哦！ 今天的题目是BIT2018年校赛的A题。不出意外的话，下周的周末特辑会是B题，再下周C题，一直出到J题√ 据说那年A题是个签到题，不过毕竟是第一周嘛，就白给一下啦。下面看题： A 克鲁苏的呼唤（搬运工注：原文如此） 克苏鲁的眷族之一，隐藏在数字中的邪神，正在从宇宙深渊中复苏。 在他潜移默化的引导下，人类建立了自以为傲的计算机系统，而这，正是他复苏的物质基石。 是否经常因为代码而陷入疯狂？ 下降的san值（sanity，理智、精神正常）正是受到邪神启蒙的证明。 现在共有N种算法，学习算法i将会导致san值下降 初始san值是S，最多可以学习多少个算法还能保持san值大于0？ 输入 多组用例，以文件尾EOF结束输入，每组用例第一行两个整数N和S分别代表算法的数量和初始san值，第二行N个整数，第i个数代表学习算法i降掉的san值 输出 对于每组用例输出一个整数占一行，表示保持san值大于0的情况下，最多能学的算法数量 样例输入 1 1 1 5 10 1 2 3 4 5 样例输出 0 3 样例解释 对于第一组用例，学习算法1会使得san值变成0，故无法学习任何算法； 对于第二组用例，学习任意四个算法都会使得san值变成0，而学习算法1,2,3是可以的。

诶是吗！ 那怎么才能增加鉴黄功力呢

没发现啊？

诶？？？ 从哪里看出来的ghs之魂

touch openGL/失败是因为不能把openGL/识别为一个指向文件名的目录元素。touch openGL/lib.lib就可以执行 指令应该有一些原子性，如果执行失败，整个命令应该什么都不做 抱歉题目有一些不完整，我稍后做补充

这题是个模拟题啊，算法就是这么个算法 模拟题的性质就是几乎没有啥算法，难点全在复杂的程序逻辑（a.k.a.代码量）上面，因此这个题要到伪代码/代码层面才算数哦~

没错，这就是本题的全部算法 也正因为如此，本期算法po上来是不够的~

有一说一，这是个模拟题 而且就算用了操作系统API，本质上树还是那棵树啊（ 还是说能贪一行就贪一行wwwww

模拟，不真建文件 也不会有操作系统API供使用的（盯

这个题不是操作系统题哦~

第二期来啦！！！！！！！！ 本来打算放一道BIT校赛的题，搬运完后感觉有点难，于是留给周末两天做吧。 今天就换成了一道模拟题。模拟题不难，依题意模拟即可。 前排提示：这个题不是个操作系统题，原题是给大一同学（非ACM）做的寒假集训题 嘛 召唤阵忘掉了，这次就算了（ 第2期 Linux目录系统 众所周知，在没有图形用户界面的年代，想要做事情都得输入命令才行。时至今日在Linux中还可以选择“打开控制台”来输入命令，通过在控制台输入命令可以做到很多只点鼠标做不到的事情。今天我们模拟的主题是基于命令行的Linux目录系统。 Linux中目录和Windows中文件夹的概念差不多。但是和Windows中每个盘有一个根目录不同，这里的目录系统只有一个根目录，叫做/。子目录和父目录间用斜杠/隔开，形如：/usr/src。 程序执行时有一个“工作目录”的概念，表示现在执行的程序在哪个目录上执行。根据工作目录可以定义相对目录，如当前工作目录若是/home/MrK018，那么相对目录Desktop/dir1就表示/home/MrK018/Desktop/dir1这个目录。特别地，我们定义.表示当前目录，..表示当前目录的父目录。 不妨认为目录系统是存在于内存上的，初始时只有根目录/。请实现如下内容： cd 将工作目录变为另一个目录； mkdir 新建一个目录； touch 新建一个文件（放心，我们没有文件读写方面的需求） ls 列出当前目录的所有直接子目录和文件； rm 删除文件，若是目录则递归地删除所有子目录和下属文件； 目录应首先当作视为相对目录，不能视为相对目录再视为绝对目录。在cd,rm等命令中遇找不到目录或文件的，输出一行Error: not found。文件名不允许为空也不允许带有斜杠，若与无法解析的文件名，输出一行Error: invalid name。 输入 输入包含多行，请读入到文件尾。每一行包含一个命令。 输出 命令的输出结果。除错误信息和ls的输出外，没有其他输出。 样例输入 mkdir usr mkdir usr/src mkdir usr/lib cd usr/lib touch anode touch glibc mkdir Apple mkdir /home/K/Desktop ls touch /home/K/Desktop/hello.txt mkdir ../include cd . cd .. cd inc ls rm lib touch openGL/ ls cd / touch etc/driver/sda1 touch etc/driver/sda1 touch etc2/driver/ cd etc/driver/ ls 样例输出 anode Apple/ glibc Error: not found include/ lib/ src/ Error: invalid name include/ src/ Error: invalid name Error: invalid name sda1

这个usedSlot我觉得不用保存成集合，我们可以只知道当前有多少个slot可以用就能进行下去了。 （删掉了一些错误信息） 我们只要保存每个血量段有多少个slot可以用，比如10血到20血的分段我有3个slot可以用，20-30没有，30-35有1个这样等等 分段的依据是怪，比如上例中这么分段的原因会是因为有10血、20血、30血、35血的怪。控血+打怪的时候，要优先选取离当前血量近的段，比如打35血怪要优先选取30-35段的那一个slot这样。 这样一来，程序的复杂度应该就降到n^2了？我肉眼看是n^2

呃，嗯…… 算法没问题没错，但是最大血量可以到1e8（盯 这个算法都到这了，我觉得优化一下没啥问题，因为我们不在乎每一个slot被用来干啥了，只关心有多少slot可以用，这样的话是能把存储量压到1e5的

不矛盾啊 相当于提前决定在216的时候控217，3和4的时候控那个7

这个引理我觉得很重要，怎么打怪就变成了怎么往slot里塞东西，也就是说要把一个个怪“摊”到这个怪血量之前的那些slot上 然后，我觉得可以从控0次血开始一点点向上摊，先摊派控0次的，之后是控1次，直到无穷；如果发现有哪个怪摊不完所有的控血+击杀，就撤销这个怪的所有摊派（这个怪就不打了）

没事没事，说出来也可以让大家来一起打磨啊

别嘛wwww 来康康题嘛，做一做你不会吃亏，做一做你不会上当（笑

所以说，弄清楚贪心怎么做了么（笑

华生你发现了盲点：问题的实质在于构造尽可能两两不相同的怪物残机数数列 顺带一提，这个题是个贪心题哦~

阁下的思路是？

好像昨天的公测太数学了，今天题目简单一点！ 第1期 异变退治 本题来源：HDU4976, 由BIT112013****改编 在一次异变中，早苗酱和灵梦展开退治大赛。假设现在一共有N个妖怪，每个妖怪残机数为A。由早苗酱开始两个人轮流行动。早苗酱每次能伤害至多一个妖怪，将其残机数减一（也可以选择不作为）；灵梦每次一定会伤害所有妖怪，全体残机数减一。当有一个妖怪的残机数在某人的回合被减至0或更少时，这个妖怪被退治（消失），同时该人得一分。现在早苗想知道自己最多能拿多少分（补刀数）。 输入 只有一组测试用例，第一行为N()，表示妖怪的个数，接下来一行有N个数，分别表示每个妖怪的初始残机数A()。 输出 输出一行，其中有一个整数，表示早苗最高可能的得分。 给出算法的同时，试一试证明算法的正确性！ 才发现自己忘掉了什么，赶紧补上 召唤阵： @ZERC @inuisanaa @随性而为 @NianRuoshui @魍魉QAQ @提辖

这期其实是公测啦，没那么正式，你看我糖才发了不到20（笑 其实我手头的题不是无限多的，这次随手想到一个（当时觉得）有趣的问题，就把它写出来了 以后要是有心血来潮的话也会自己出一点的，也欢迎大家来向我提供题目√

嗯，那啥…… 我今天题是不是出难了（笑 没想到图形学这个题来的都喊难，是因为里面有数学么2333

这个的话，原本的STL文件中三角面的存储是有序的（遵循右手法则），可以提供一些关于法向的信息（遗憾的是，本题中不一定这么存储www），然而没有哪些三角面可以构成封闭空间的相关信息 ……而且我觉得这个信息的输入是件非常可怕的事情啊，一个几何体的三角面是很多的

编程题一般都是题文无关（笑