{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"# 题面\n\n咕咕东的雪梨电脑的操作系统在上个月受到宇宙射线的影响,时不时发生故障,他受不了了,想要写一个高效易用零bug的操作系统 —— 这工程量太大了,所以他定了一个小目标,从实现一个目录管理器开始。前些日子,东东的电脑终于因为过度收到宇宙射线的影响而宕机,无法写代码。他的好友TT正忙着在B站看猫片,另一位好友瑞神正忙着打守望先锋。现在只有你能帮助东东!\n\n\n初始时,咕咕东的硬盘是空的,命令行的当前目录为根目录 `root`。\n\n目录管理器可以理解为要维护一棵有根树结构,每个目录的儿子必须保持字典序。\n\n![](https://s1.ax1x.com/2020/04/10/GojFbt.png)\n\n现在咕咕东可以在命令行下执行以下表格中描述的命令:\n\n| 命令 | 类型 | 实现 | 说明 |\n| :-------: | ---- | :----------------------------------------------------------: | :----------------------------------------------------------: |\n| MKDIR *s* | 操作 | 在当前目录下创建一个子目录 *s*,*s* 是一个字符串 | 创建成功输出 \"OK\";若当前目录下已有该子目录则输出 \"ERR\" |\n| RM *s* | 操作 | 在当前目录下删除子目录 *s*,*s* 是一个字符串 | 删除成功输出 \"OK\";若当前目录下该子目录不存在则输出 \"ERR\" |\n| CD *s* | 操作 | 进入一个子目录 s,*s* 是一个字符串(执行后,当前目录可能会改变) | 进入成功输出 \"OK\";若当前目录下该子目录不存在则输出 \"ERR\"\u003cbr /\u003e特殊地,若 *s* 等于 \"..\" 则表示返回上级目录,同理,返回成功输出 “OK”,返回失败(当前目录已是根目录没有上级目录)则输出 “ERR” |\n| SZ | 询问 | 输出当前目录的大小 | 也即输出 1+当前目录的子目录数 |\n| LS | 询问 | 输出多行表示当前目录的 \"直接子目录\" 名 | 若没有子目录,则输出 \"EMPTY\";若子目录数属于 [1,10] 则全部输出;若子目录数大于 10,则输出前 5 个,再输出一行 \"...\",输出后 5 个。 |\n| TREE | 询问 | 输出多行表示以当前目录为根的子树的前序遍历结果 | 若没有后代目录,则输出 \"EMPTY\";若后代目录数+1(当前目录)属于 [1,10] 则全部输出;若后代目录数+1(当前目录)大于 10,则输出前 5 个,再输出一行 \"...\",输出后 5 个。若目录结构如上图,当前目录为 \"root\" 执行结果如下,![](https://s1.ax1x.com/2020/04/10/GojYPU.png) |\n| UNDO | 特殊 | 撤销操作 | 撤销最近一个 \"成功执行\" 的操作(即MKDIR或RM或CD)的影响,撤销成功输出 \"OK\" 失败或者没有操作用于撤销则输出 \"ERR\" |\n\n# 输入\n\n输入文件包含多组测试数据,第一行输入一个整数表示测试数据的组数 T (T \u003c\u003d 20);\n\n每组测试数据的第一行输入一个整数表示该组测试数据的命令总数 Q (Q \u003c\u003d 1e5);\n\n每组测试数据的 2 ~ Q+1 行为具体的操作 (MKDIR、RM 操作总数不超过 5000);\n\n### 面对数据范围你要思考的是他们代表的 \"命令\" 执行的最大可接受复杂度,只有这样你才能知道你需要设计的是怎样复杂度的系统。\n\n# 输出\n\n每组测试数据的输出结果间需要输出一行空行。注意大小写敏感。\n\n# 时空限制\n\nTime limit 6000 ms\n\nMemory limit 1048576 kB\n\n# 样例输入\n\n```\n1\n22\nMKDIR dira\nCD dirb\nCD dira\nMKDIR a\nMKDIR b\nMKDIR c\nCD ..\nMKDIR dirb\nCD dirb\nMKDIR x\nCD ..\nMKDIR dirc\nCD dirc\nMKDIR y\nCD ..\nSZ\nLS\nTREE\nRM dira\nTREE\nUNDO\nTREE\n```\n\n# 样例输出\n\n```\nOK\nERR\nOK\nOK\nOK\nOK\nOK\nOK\nOK\nOK\nOK\nOK\nOK\nOK\nOK\n9\ndira\ndirb\ndirc\nroot\ndira\na\nb\nc\ndirb\nx\ndirc\ny\nOK\nroot\ndirb\nx\ndirc\ny\nOK\nroot\ndira\na\nb\nc\ndirb\nx\ndirc\ny\n```\n# hint\n英文原版题面:\n\n![](https://s1.ax1x.com/2020/04/14/JSPJG6.png)"}}]}