Mr.K 018

模拟，不真建文件 也不会有操作系统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中的方块，竹签是那个几何体）

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

好，第0期发了！ https://sstm.moe/topic/252752-每-日-算-法-挑-战-【第0期，有红包】/ 今天这个问题是个图形学的问题，我一个小时之内想出来的（ 有一说一 我觉得应该有现成算法，但我没有查2333

好的！经过一个晚上的商讨，我们的每日算法挑战要和大家见面了！ 如标题所示本期是第0期，就是每日算法挑战的公测。下面放上简介！ 1 这是什么？ 每日算法挑战本质上不就是拿来热版的花招么 每日算法挑战，顾名思义，就是每天会po一道算法相关的题目，来让大家讨论讨论，做一做。当然了，这个每日算法挑战并不是什么ACM之类的算法题，各位就算交了代码也没有用。因此，大家只要说说算法和思路，最多给出伪代码就可以了。伪代码写得也可以随便一点，但是太过耍赖的“伪代码”也是不行的哦！比如这样的伪代码: 输入本题的所有数据； 解题； 输出结果 这样的伪代码说的就太模糊了，有点耍赖。我们约定除了众所周知的少数算法（如排序）之外，伪代码也要由常数时间内就能做完的动作（或自己定义的过程调用）组成。同样地，对于自定义数据结构也尽可能写的清楚一点为好。 如果觉得伪代码要求太复杂了，其实也不用非得写伪代码，只要能说明白算法的大致实现过程也可以。写得详细的可以拿到和伪代码一样的奖励哦！ 2 有奖励吗！ 有啊，当然有了！我们欢迎所有形式的讨论，尤其会对这样的贴子发放奖励： 首先给出了正确答案（或者相对本题可以接受的答案）的，可以拿到最多的奖励！ 虽然不是首先给出答案，但是有一些新内容的（比如新方法啊，复杂度等等的讨论啊，算法思路的说明啊，以及正确性证明等等）； 参与讨论，有一些新颖的见解或者指出了其他人答案的bug的。 顺带一提，三种奖励可以叠加！ 今天作为公测，我先放出来一道我随便杜撰的题吧! 第0期 我的世界 K想要在MC里搭一个雕塑。他手头有一个STL文件，里面保存了这个雕塑的样子。 题目中为了简化，认为STL文件由若干三角面组成，每个三角面由九个实数组成，前三个、第4-6个和第7-9个实数分别定义了三角面的三个顶点。可以认为每个STL文件中的各个三角面能围成一个封闭的几何体。 我们规定，对于每个MC中的方块区域，只要三角面穿过了这个区域，就要在那里搭上方块，并且这个雕塑是实心的，即几何体的内部也要填上方块。 K在搭建雕塑之前，首先要知道他要准备多少个方块，来计划挖矿（指给苦力ABCDE等人安排挖矿任务）。现在他想问问你，修雕塑要多少方块呢？ 输入 第一行是一个整数n，表示这个STL文件中的三角面个数。 接下来有n行，每行有9个实数，分别表示三角面中的三个顶点，顺序是X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3。 输出 输出一行，其中有一个整数，表示雕塑需要多少方块。 嗯……这个题是我杜撰的，因此没有预设的正确答案，大家可以畅所欲言。

@萨卡 诶，你也是萨卡

emmm说起来有点不好意思，这两天现实中比较肝，那个坑好几天没怎么动了