yhz012

辛苦啦 我还是决定滚去python了（x 反正伪代码也可以，那我用py也没问题了吧（x 果然我已经是py的形状了 class node(object): #基类 def __init__(self, name, parent): super(node, self).__init__() self.name = name self.parent = parent if self.parent is not None: if hasattr(self.parent, 'childList'): self.parent.childList.append(self) else: print('Error: no childList') return class fileNode(node): #文件 def __init__(self, name, parent): super(fileNode, self).__init__(name, parent) self.isFolder = False return def remove(): self.parent.childList.remove(self) return class folderNode(node): #文件夹 def __init__(self, name, parent): super(folderNode, self).__init__(name, parent) self.isFolder = True self.childList = [] return def remove(): for child in childList: child.remove() self.parent.childList.remove(self) return class envTree(object): #环境 def __init__(self, localDir): super(envTree, self).__init__() self.root = localDir #根 self.localDir = localDir #当前相对路径 self.tempDir = self.localDir #临时工作路径 return def console(cmd): #解析命令 if cmd[:3] == 'cd ': tempFunction = self.moveDir name = cmd[3:] elif cmd[:6] == 'mkdir ': tempFunction = self.mkdir name = cmd[6:] elif cmd[:6] == 'touch ': tempFunction = self.touch name = cmd[6:] elif cmd == 'ls': self.ls() return elif cmd[:3] == 'rm ': tempFunction = self.rm name = cmd[3:] else: return #初始化工作路径 if name == '': return self.tempDir = self.localDir pathList = name.split('/') if pathList[0] == '': self.tempDir = self.root pathList.pop(0) if pathList[0] == '' and len(pathList) == 1: #处理根目录情况下会判定路径非法的bug pathList.pop(0) elif pathList[0] == '.': pathList.pop(0) elif pathList[0] == '..' if self.tempDir.parent is not None: self.tempDir = self.tempDir.parent: pathList.pop(0) else: print('Error: not found.') return #判定语法 for path in pathList: if path == '' or path == '.' or path == '..': print('Error: invalid name.') return else: tempFunction(pathList) return def ls(): for child in self.tempDir: if child.isFolder: print('/', end = '') print(child.name) return def _cd(path): for child in self.tempDir.childList: if child.name == path: if child.isFolder: self.tempDir = child return 0 #正常 else: return -2 #存在同名文件 else: return -1 #不存在路径 def cd(pathList): rtvl = 0 #移动临时工作路径 while pathList: rtvl = self._cd(pathList[0]) if rtvl == 0: pathList.pop(0) elif rtvl == -1: print('Error: not found.') return elif rtvl == -2: print('Error: not found.') return else: print('Error: unknown.') return #移动成功，改变环境 self.localDir = self.tempDir return def _mkdir(path): newFolder = folderNode(path, self.tempDir) self.tempDir = newFolder return def mkdir(pathList): rtvl = 0 #移动临时工作路径 while pathList: rtvl = self._cd(pathList[0]) if rtvl == 0: pathList.pop(0) elif rtvl == -1: break elif rtvl == -2: print('Error: not found.') return else: print('Error: unknown.') return #开始新建文件夹 for path in pathList: self._mkdir(path) return def _touch(name): for child in self.tempDir.childList: if child.name == path: if child.isFolder: return -2 #存在同名文件夹 else: return -1 #存在同名文件 else: newFile = fileNode(name, self.tempDir) return 0 def touch(pathList): if len(pathList) == 0: print('Error: invalid name.') return name = pathList.pop(-1) #移动临时工作路径 while pathList: rtvl = self._cd(pathList[0]) if rtvl == 0: pathList.pop(0) elif rtvl == -1: break elif rtvl == -2: print('Error: not found.') return else: print('Error: unknown.') return #开始新建文件夹 for path in pathList: self._mkdir(path) #新建文件 rtvl = self._touch(name) if rtvl == -2: print('Error: invalid name.') elif rtvl == -1: pass elif rtvl == 0: pass else: print('Error: unknown.') self._touch(name) return def rm(pathList): #移动临时工作路径，检查路径正确性 rtvl = 0 while pathList: rtvl = self._cd(pathList[0]) if rtvl == 0: pathList.pop(0) elif rtvl == -1: print('Error: not found.') return elif rtvl == -2: break else: print('Error: unknown.') return #检测路径完整性 if rtvl == -2: if len(pathList) != 0: print('Error: not found.') return self.tempDir.remove() return 我说实话我没测试，可能会有手滑的地方（逃 另外我假设不会出什么因为IO的问题导致合法的命令中途爆掉的情况，对于新建文件或者文件夹倒是好说，我在开始新建的地方记录一下，爆掉了就删回去就完了。不过如果是删除，我大概是填不回去了（笑） 2020-4-10 04:47:54 修了个根目录路径非法的bug 2020-4-10 04:51:20 处理了一些边界情况会越界的情况 2020-4-10 04:54:38 修了个全都判断好了就是忘了新建文件的智障错误……

提个问题，mkdir是可以一个命令建立多层文件夹的，但是touch看起来是不能连带着文件夹一起建立文件的？ 比如说 touch openGL/ 这句话，是因为不存在openGL这个文件夹，所以认为 openGL/ 整个是个文件名，带了反斜杠所以失败了 还是因为后面的文件名为空失败了？ 换句话说，如果用的是 touch openGL/a.txt 怎么处理？ 以及对于mkdir一个命令建立多层文件夹，如果其中出现了非法文件夹名，怎么处理，把之前的新建文件夹全都撤销掉，还是建了的保留？ 举例来说 原来只有根目录的情况，执行 mkdir /a/b/../c 中间的..是非法文件夹名的吧？ 这种情况下，我需要把文件夹a和文件夹b也一起撤销掉吗？还是说留着/a/b就可以了？

写C系的好累，我还是决定滚去用py写了（x 艹，等下，py没有指针有点烦（x 那我还是滚去用带类C的C++写好了（x

看了一下，感觉最暴力的方法就是维护一个树结构 struct node{ bool folderFlag; char nameLen; char name[128]: struct node *parent; struct node *childrenListHead; struct node *next; }; 层间用树结构组织，层内用循环链表组织大概就可以了吧……

第一眼看是操作系统题，溜了溜了.jpg 第二眼看大概还好，感觉还能做 感觉基本就是构建一个树就可以了……？

我决定用后面的这个代码了，因为一开始为了求B数组实在是太疼了1e8级别的跑起来真的太疼了

引理2的B和C都是和题目中的A一样的数组 其中B是A的子集，同时B中的每一个元素都可以在C中找到一个对应，这个对应要满足 b >= c 此外C中的元素全部唯一，没有重复元素 你可以理解为B是早苗的人头实际来源，C是早苗拿人头的回合 这点我同意，但是我头疼的是30-35有1个意味着我实际上是有，比如说30, 31, 32, 34, 35这样的一组数据的如果这时候我有一个重复35的要控血到33，我需要控2次就好了 但是如果我原来是30, 32, 33, 34, 35，我就需要控4次了…… 感觉还是卡在了哪里…… 啊我理解了，我实际上保存key-value对就好了，key是连续空白最后的位置，value是连续空白的长度 比如我写一个数组，里面存放这个key-value对，slot[(lastPos, size)] 这样我倒序的话，每次使用最大key的key-value对，消耗掉相应的value并降低key，value归零就丢掉这个kv对就完了 因为kv对是连续的，所以最坏被分割出(N+1)个kv对 判断对应slot是否被用了就直接找第一个大于index的key，然后看key-value是不是小于value就完了

是的，这里我看着就疼，填格子的部分倒是可以先把B构造成key-value对，然后根据value sort一下然后能把下面的循环时间压到O(|A|)，上面的循环我还得考虑下…… 某种意义上第一个求补刀数可以删掉，但是这样就要增加后面循环的量了…… 后面的循环直接 A.sort() A.reverse() #降序 usedSlot = {} step = 0 #补刀数 slotNum = A[0] #总格子数 while A and slotNum >= step + 1: #A非空就继续填格子,或者所有格子填满了 for a in A: #倒序遍历 if a - step not in usedSlot: #有空位 if slotNum > step + 1: #能补过来 usedSlot = usedSlot + {a - step} #人头占位 A.remove(a) #考虑过了，之后不用再看了 score = score + 1 slotNum = slotNum - (step + 1) else: #补不过来了，之后肯定都补不过来了 return score else: #没空位，留着下一轮继续判断 pass

我似乎知道我智障在哪了 A.sort() #升序排列 slotNum = A[-1] #拿到A里最大的元素值，作为总的格子数 #计算各元素需要补刀数量 B = empty_like(A) #记录各元素需要补刀数 freeSpaceList = [] #记录可用划水位 index = 0 for value in range(1, slotNum + 1): #遍历A中的所有元素值，耗时O(|A| + max(A)) if A[index] > value: #空，加入到划水位 freeSpaceList.append(value) else: #A中值为value的第一个元素 B[index] = 0 #不需要补刀 index = index + 1 #移动到下一个元素 while A[index] == value: #A中值为value的重复元素 if freeSpaceList: #还有空余划水位可用 lastFreeSpace = freeSpaceList.pop() B[index] = value - lastFreeSpace #计算补刀数 else: #没空位我有什么办法嘛，这个人头彻底放弃了 B[index] = -1 index = index + 1 #移动到下一个元素 #开始填格子 tempLastIdx = 0 #记录目前预计最后一个人头的位置 tempFreeSpaceSize = 0 #记录目前可以操作的空间 score = 0 #记录目前的得分 for value in range(0, max(B) + 1): #从最好拿人头的（0补刀）开始，逐渐增加补刀数 for index in range(len(B)-1, -1, -1): #倒序遍历所有元素 if B[index] == value: #可以考虑拿人头了 if tempLastIdx < index: #更新最后一个人头的位置 tempFreeSpaceSize = tempFreeSpaceSize + (index - tempLastIdx) #因为最后一个人头位置增加了，增加了更多的操作空间 tempLastIdx = idx if tempFreeSpaceSize > B[index] + 1: #有位置补刀+收人头 tempFreeSpaceSize = tempFreeSpaceSize - (B[index] + 1) score = score + 1 else: #没位置了，再往前也是一样要补刀的个数，一样不会有位置的 break 基本算是按照py的语法写的，应该稍微改一些细节就能直接跑了，不过感觉应该有不少优化空间，这大循环写的我看着就疼

这个不影响，我姑且认为你的例子可能有一点点偏差，因为为了拿全所有人头你列的人头需要5个滑水位，所以我稍微改一下变成1,2,6,7,7,...,214,217,217。 你可以理解为假定我现在确定要拿1,2,6,7,214,216,217的人头那么我需要补刀1次，所以我需要在217前完成总计1次补刀就好了，至于在哪补，并不重要，这是我引理2说的内容 同理，如果我为了拿1,2,5,6,7,214,216,217，那我就需要在217前补3次，显然我现在有3,4,215给我补，至于具体我怎么补，根据引理2，肯定有方案补（即优先把前面的补了就好）

具体数据结构其实我倒是觉得影响不大，我只需要这个数据结构可以支持以下行为即可： 1. 对内部元素根据value升序排序（可以不稳定排序，因为任何同value元素都是完全等价的） 2. 降低内部元素的value 1 3. 删除最小元素 最好做的方法大概是优先队列，一般最好做的实现方法是二叉堆？ （艹等下我怎么觉得好像有点邪道解法） 想多了，不存在的 这句话我在考虑……或许这句话是做成贪心算法的关键……

我们可以把早苗的行动分为3种 1.抢人头→打1残怪就完了 2.滑水→什么都不做 3.控血→打非1残怪，目的是让这个怪的残机数降低到一个空白的残机数的位置上，每次实际上是对数组内的某一个元素值-1 目前可以确定的是，如果可以抢人头，那么优先抢人头必然不亏 —— 引理1 （需要注意的是引理1只是不亏，或许不这么关注引理1有利于更好地构造算法） 另外对于灵梦的操作，我们可以用另一个角度看待，可能会方便理解一些 早苗的操作只会降低数组A内的元素值 灵梦的操作实际上可以视为在第k回合，把数组头移动到第一个大于k的元素上 首先毫无疑问我们可以把所有的不是空白的位置上标记为抢人头，而空白的位置上标记为滑水。这是我上面说的最平凡的解 根据引理1，我们知道如果要控血k次后得分，我们需要k个控血回合和1个抢人头回合，即共计k+1个回合原来是滑水的，我们需要从头开始把这k个原来是滑水的回合填上控血，然后第k+1个滑水的回合填上抢人头。 假定我们确实拿到了x个人头在位置C上（显然C内所有元素唯一），来源是A的子集B（显然BC的大小相等），我们必然需要控血sum(B)-sum(C)，且控血顺序不重要 —— 引理2 早苗打最高残机的怪血亏 —— 引理3 这个显然 引理3告诉我们，以理解为有max(A)个slot，然后往slot里塞上面3个行动就完了

感觉似乎找到了方向，但是很快我就能举出来反例说明子问题的定义是不能保证全局最优的，感觉我似乎错过了什么关键证明

贪心就可以了么……那大概是我子问题定义错了……感觉我现在的定义没法保证单步最优必然全局最优…… 我大概知道贪心的子问题是啥了…… 不对好像还有点问题……

问下变量i是什么？数组A的长度？

艹，越共大欢喜，让我仔细看看 感觉因为灵梦每回合必定全体攻击1次所以反倒似乎没有博弈的问题了？似乎变得简单了？ 最简单的情况考虑 早苗看到有k个1残机，能拿到1分，灵梦拿到k-1分 所以对于早苗来说，最好的情况是让残机保持1的等差数列 所以先sort一下应该是不亏的 另一种说法就是sort之后，退一万步说，早苗至少能拿到数列中不同元素个数的得分，这是最平凡的下限 sort之后如果有1残，那直接打了是绝对不会亏的（证明↓） 反之有2残打2残是不会赚的（证明↓） 但是对于2以上的残机，需要进一步判断 假定现在在j残机处有k个相同残机的妖怪，前一个空缺（指不存在该残机数妖怪）为i残机，那么早苗为了多拿1分，需要打j-i次 显然地，如果j>2i，早苗是拿不到这1分的，因为没等打过去呢，灵梦就先打没了 更进一步地，早苗如上所说的做法，只是为了多拿1分，因此在这个过程中，除非该回合拿不到分数，否则是不赚的 即，早苗为了多拿这1分，需要x回合 其中x == x以内不同元素个数 + (j - i)，换句话说就是为了多拿这1分，需要前面 (j - i)个空缺。顺带，从这句话可以得出，第一个出现重复妖怪的位置上是永远只能拿到1分的。我智障了，应该说第一个空缺是永远没法拿到分的。感觉似乎可以规约01背包了…………？ 这个过程中，该妖怪一共掉残机 x + (j - i)，所以如果j 比 x + (j - i) 小，即x > i，则可以直接放弃这个妖怪了 最坏情况就可以用暴力动态规划了

我觉得是因为很多人不想用暴力解法吧 毕竟直观来看如果我们能把所有三角面都放上方块，那接着如果我们有方法再判断一下一个方块是不是在体内，就不需要这么暴力的方法了 更进一步地，如果我把所有三角面的边上都放上方块，那接着如果我有办法判断一下这个方块是否在这个边界内，那我就能把三角面都放上方块了 直观来看是这样，但是判断内部这件事我还真的没想到什么可以不暴力的方法……

那东西其实是用来快速判定某一点是否在凸多边形/多面体的，实际上和上面的等效。 对于二维情况，三角形只要解3个线性方程，但是如果环很大，比如说是n个顶点，那就要解n个线性方程。求n*n矩阵的逆还是饶了计算机吧（笑），不如上面说的判定右转来的快。 当然对于三维情况，就没法用上面的判定右转了。不过实际上如果已知凸多边形，选面abc，再取一顶点d，直接判断x是否和d在面同一侧。用这个方法遍历所有面也可以判断。

已知环，可以再判断一下环是否是凸多边形，假设环的点我们是按照逆时针顺序排列（这个很简单判定），假设环上连续3个顶点是abc，计算ab与bc的向量积在单位z向量上的数量积，如果是正则b点为凹点，负则为凸点（实际上就是利用了向量积的右手性质来判断abc是“往左转”还是“往右转”） 假设b为凹点，那么沿着ab射线，必然和环相交一点，设为d，那么就可以用线段bd把环分成2个子环，继续判定凸性，直到所有子环为凸 接着给定一个凸环，以及另外一点x，假设环上相邻的两顶点为ij，那么继续求ij和jx的向量积在z方向的数量积，如果始终都是“往右转”，那么x就在凸环内了 另外实际上我的方案其实就是暴力破解，只是给这个暴力破解的过程提供一个判定该方块在多面体内的方法

我也在担心这个问题，但是我需要有比较方便的方法判定一个多面体是凸的 当然也有类似地暴力的分割方案，就是像上面说的对z轴（或者x轴y轴，反正选一个）进行切片，切片的坐标在所有输入的z坐标 然后根据该z坐标相邻的三角面的情况进行判断，类似于下图的3D版，不过感觉分情况讨论会有点痛苦…… 是的，我是假设了这个几何体是单连通的…… 如果是多联通情况，大概是真的要求法向了…… 如果确定是单连通，那么即使是大圈套小圈也能确定最外面的圈内一定是放方块，然后里面一层是不放，再里面是放，以此类推 如果是多联通，我的感觉是也会一样的效果，但是我需要仔细考虑下

求环不难，举例来说现在你有集合S为在z面上的所有截取线段集合 circleList = [] while not S[i].isEmpty(): circle = [] a, b = S[i].pop() circle = circle + [a, b] c, d = None, None while c != a and d != a: for line in S[i]: c, d = line if c == b: S[i] = S[i] - {line} circle = circle + [d] b = c elif d == b: S[i] = S[i] - {line} circle = circle + [c] b = d circleList = circleList + [circle] 唯一可能出现的问题是有可能存在类似于“8”这样的环，不过这个在之后再判定一下就好了

如果按照我robotics的方案就是暴力分小块……直到一般认为不会再有可能插在中间为止，这是暴力解决方案 或者考虑求四面体的4个面对立方体的6个面的交线，如果有交线则应当放置方块 这样的话可以把问题规约到已知两个凸几何体，求两几何体是否相交 需要判定 1. 几何体A的顶点是否在几何体B内→质心坐标可解 2. 几何体B的顶点是否在几何体A内→质心坐标可解 3. 几何体A的面是否与几何体B的面存在交线→求两面相交直线 以上三个任何一个为真，则相交 似乎二连了，抱歉

我主要担心的就是可能会重复，或者更准确说是切到了几何体外面，因为可能正好这俩三角面是凹进去的，感觉还是有点问题 至于质心坐标，如果已经确定是四面体的话，应该是能找到现成的公式求坐标的

最平凡的情况是如果多面体确定为凸，那么文件内所有点当做顶点，直接用barycentric coordinates（翻译好像叫重心坐标？） 通过求判定点到各顶点距离反过来解线性方程组能得到barycentric coordinates，然后判定坐标的各分量是否在01之间，如果是，则在体内，否则在体外 然后对于非凸的情况就可以做分割得到凸多面体来带走了 暴力一点的分割凸多面体方案可以是拿出一个三角面，找和该三角面有公用边的另一个三角面（存在性需要证明，不过目测应该是必然存在的） 这两个三角面构成四面体，为凸，同时得到另外2个新三角面，加入到三角面列表 把所有pair遍历之后应该就能把整个几何体给三角化了 感觉这个三角化有点问题，不过已知顶点集（即输入文件），肯定有三角化的算法，翻一下工具书或者面向github编程一下就可以了吧（ 看了一下因为涉及到坐标取整问题，所以大概对于同一个方块需要判定8次（即方块的8个顶点坐标），只要有一个在体内就判定这个方块是在体内 为了避免暴力遍历所有方块，可以用类似二分的方式先取(min x: max x, min y: max y, min z: max z)范围内的方块 然后均匀3刀得到8个小方块分别判定 1.小方块的8个顶点存在至少一个在几何体内， 2. 几何体的所有顶点存在至少一个在小方块内（直接判断xyz范围就好）。这两个条件任意满足则继续细分。如果两个都不满足直接丢了就好，肯定这个区域内没方块要放的 感觉应该还有不少可以优化的地方 另外前面有人提到的沿某个轴做切割也可以，切割的点选取输入文件中的全部z坐标，这样可以避免漏掉某些小三角形 这样在每个切面能够确定地得到一集合的线段 对该集合取出一个线段，找能接上该线段的线段，直到完成一个环 如果集合非空，继续重复完成环 最后会得到切面上的一集合的环 接着判定方块是否在任意一个环内就完了 规约到了2D，判定点在封闭多边形内，暴力三角化然后直接判断点在三角内就完了

是计算几何，正好是我ddl要干的活，我死了 看了一下，可以理解为是判定点是否在多面体内？ 然后这个多面体应该认为可以是非凸的