Mr.K 018

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），然而没有哪些三角面可以构成封闭空间的相关信息 ……而且我觉得这个信息的输入是件非常可怕的事情啊，一个几何体的三角面是很多的

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

关于这个，我突然发现我编题的时候没有考虑STL本身是空心的情况 如果要求STL的空心搭出来还是空心（挤没了的不算）的话，平面截出来就会有大环套小环的问题。考虑在线段集里记录每个线段的法向？

这个方法我觉得可行，总结一下大概的思路： 1. 将STL中的几何体三角化，分割成一个四面体集； 2. 维护一个放置方块集（初始为空），对四面体集的每一个元素： 2.1 确定要判定的四面体涉及哪些方块（可以通过x,y,z三个轴的最小值、最大值来限定）； 2.2 对每个上一步中得出要考虑的方块，进行求交运算，若相交则入方块集合。 3. 输出方块集合的集合大小，结束。 我原先觉得这个问题应该先考虑表面再填充内部，后来发现这个方法好像不需要填充 下一个问题是复杂度，因为我们的目的不是非要找四面体而是找出一个凸的部分即可，现在分成基本的四面体的方法分的是否有些碎呢

有一说一质心坐标那里我还得研究研究，但是三角化算法应该是没有问题的，因为每一次切下一个四面体，剩余的部分必然还是（一个或两个）闭合的多面体，只不过需要看一下新增的两个三角面是不是已有的边界，如果不是再加入到三角面集合里去 而且用质心坐标的话，怎么解决方块的顶点和中心点都在几何体外，但方块本身却要算进去这种情况呢 （请脑补糖葫芦，山楂是方形的，就是MC中的方块，竹签是那个几何体）

这个题其实是个图形学相关的题，一时兴起就出了这么一道（笑