题面
咕咕东的雪梨电脑的操作系统在上个月受到宇宙射线的影响，时不时发生故障，他受不了了，想要写一个高效易用零bug的操作系统 —— 这工程量太大了，所以他定了一个小目标，从实现一个目录管理器开始。前些日子，东东的电脑终于因为过度收到宇宙射线的影响而宕机，无法写代码。他的好友TT正忙着在B站看猫片，另一位好友瑞神正忙着打守望先锋。现在只有你能帮助东东！
初始时，咕咕东的硬盘是空的，命令行的当前目录为根目录 root。
目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。
现在咕咕东可以在命令行下执行以下表格中描述的命令：
命令
类型
实现
说明
MKDIR s
操作
在当前目录下创建一个子目录 s，s 是一个字符串
创建成功输出 “OK”；若当前目录下已有该子目录则输出 “ERR”
RM s
操作
在当前目录下删除子目录 s，s 是一个字符串
删除成功输出 “OK”；若当前目录下该子目录不存在则输出 “ERR”
CD s
操作
进入一个子目录 s，s 是一个字符串（执行后，当前目录可能会改变）
进入成功输出 “OK”；若当前目录下该子目录不存在则输出 “ERR”
特殊地，若 s 等于 “…” 则表示返回上级目录，同理，返回成功输出 “OK”，返回失败（当前目录已是根目录没有上级目录）则输出 “ERR”
SZ
询问
输出当前目录的大小
也即输出 1+当前目录的子目录数
LS
询问
输出多行表示当前目录的 “直接子目录” 名
若没有子目录，则输出 “EMPTY”；若子目录数属于 [1,10] 则全部输出；若子目录数大于 10，则输出前 5 个，再输出一行 “…”，输出后 5 个。
TREE
询问
输出多行表示以当前目录为根的子树的前序遍历结果
若没有后代目录，则输出 “EMPTY”；若后代目录数+1（当前目录）属于 [1,10] 则全部输出；若后代目录数+1（当前目录）大于 10，则输出前 5 个，再输出一行 “…”，输出后 5 个。若目录结构如上图，当前目录为 “root” 执行结果如下，
UNDO
特殊
撤销操作
撤销最近一个 “成功执行” 的操作（即MKDIR或RM或CD）的影响，撤销成功输出 “OK” 失败或者没有操作用于撤销则输出 “ERR”
输入
输入文件包含多组测试数据，第一行输入一个整数表示测试数据的组数 T （T <= 20）；
每组测试数据的第一行输入一个整数表示该组测试数据的命令总数 Q （Q <= 1e5）；
每组测试数据的 2 ~ Q+1 行为具体的操作 （MKDIR、RM 操作总数不超过 5000）；
面对数据范围你要思考的是他们代表的 “命令” 执行的最大可接受复杂度，只有这样你才能知道你需要设计的是怎样复杂度的系统。
输出
每组测试数据的输出结果间需要输出一行空行。注意大小写敏感。
时空限制
Time limit 6000 ms
Memory limit 1048576 kB
样例输入
1
22
MKDIR dira
CD dirb
CD dira
MKDIR a
MKDIR b
MKDIR c
CD …
MKDIR dirb
CD dirb
MKDIR x
CD …
MKDIR dirc
CD dirc
MKDIR y
CD …
SZ
LS
TREE
RM dira
TREE
UNDO
TREE
样例输出
OK
ERR
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
OK
9
dira
dirb
dirc
root
dira
a
b
c
dirb
x
dirc
y
OK
root
dirb
x
dirc
y
OK
root
dira
a
b
c
dirb
x
dirc
y
解题思路：
首先对每条指令，每个指令有指令的类型以及MKDIR,RM,CD三个指令还有参数，所以用Command结构体进行封装。又因为目录管理器是一棵目录树的数据结构，所以需要维护该树，又因为要求字典序，所以要用map<string,目录>，它可以根据key也就是string 在内部进行排序,用类Directory表示。
具体指令：
MKDIR 查找目标目录，存在则输出 “ERR”，创建目录，往map里插入，成功输出 “OK”；往前调用函数更改 snum值
RM 查找目标目录，不存在则输出 “ERR”，删除成功输出 “OK”；记录命令
CD 查找目标目录，不存在则输出 “ERR”，否则更改workdir 记录命令
SZ 直接返回 workdir->snum
LS 若没有子目录，则输出 “EMPTY”；若子目录数属于 [1,10] 则全部输出；若子目录数大于 10，则前序输出前 5 个，再输出一行 “…”，后序输出后 5 个。
TREE 若没有后代目录，则输出 “EMPTY” ，若后代目录数+1（当前目录）属于 [1,10] 则全部前序输出，若后代目录数+1（当前目录）大于 10，则前序输出前 5 个，后序遍历后5个 加上缓存
UNDO 取出满足条件的最后一条命令，还原。mk->rm rm->mk，注意的是取出原先删除的结点 cd->直接还原工作目录
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
struct ptrcmp {
bool operator()(const char* s1, const char* s2) const {
return strcmp(s1, s2) < 0;
}
};
struct dirnode {
char * name;
dirnode* up;
map<char *, dirnode*,ptrcmp> sub;
int snum;
vector<char*> qianxu;
vector<char*> houxu;
int updated;
dirnode(dirnode* up, char * name) :up(up), name(name) {
snum = 1;
updated = 1;
}
};
struct opcode {
char * name;
int optype;
dirnode* olddir;
opcode(char * name, int optype) :name(name), optype(optype) {
olddir = NULL;
}
opcode(char * name, int optype, dirnode* olddir) :name(name), optype(optype), olddir(olddir) {}
};
class dir {
public:
dir() {
char* root = new char[10];
strcpy(root, "root");
workdir = new dirnode(NULL, root);
rmdir = NULL;
}
void touched(int num) {
dirnode* thisnode = workdir;
while (thisnode != NULL) {
thisnode->snum += num;
thisnode->updated = 1;
thisnode = thisnode->up;
}
}
void mkdir(char * s) {
map<char *, dirnode*,ptrcmp>::iterator it = workdir->sub.find(s);
if (it != workdir->sub.end()) {
printf("ERR\n");
return;
}
dirnode* newnode = new dirnode(workdir, s);
workdir->sub.insert(make_pair(s, newnode));
history.push_back(opcode(s, 1));
touched(1);
printf("OK\n");
return;
}
void rm(char * s) {
map<char *, dirnode*,ptrcmp>::iterator it = workdir->sub.find(s);
if (it == workdir->sub.end()) {
printf("ERR\n");
return;
}
rmdir = it->second;
workdir->sub.erase(it);
history.push_back(opcode(s, 2, rmdir));
touched(0-rmdir->snum);
printf("OK\n");
return;
}
void cd(char * s) {
if (s[0] == '.' && s[1] == '.' && s[2] == '\0') {
if (workdir->up == NULL) {
printf("ERR\n");
return;
}
history.push_back(opcode(s, 3, workdir));
workdir = workdir->up;
printf("OK\n");
return;
}
map<char *, dirnode*,ptrcmp>::iterator it = workdir->sub.find(s);
if (it == workdir->sub.end()) {
printf("ERR\n");
return;
}
history.push_back(opcode(s, 3, workdir));
workdir = it->second;
printf("OK\n");
return;
}
int sz() {
return workdir->snum;
}
void ls() {
if (workdir->sub.empty()) {
printf("EMPTY\n");
return;
}
if (workdir->sub.size() <= 10) {
for (auto it = workdir->sub.begin(); it != workdir->sub.end(); it++) {
printf("%s\n", it->first);
}
return;
}
int count = 1;
for (auto it = workdir->sub.begin(); it != workdir->sub.end(); it++) {
printf("%s\n", it->first);
if (count == 5) {
printf("...\n");
break;
}
count++;
}
count = 1;
vector<char*> toput;
for (auto it = workdir->sub.rbegin(); it != workdir->sub.rend(); it++) {
toput.push_back(it->first);
if (count == 5) {
break;
}
count++;
}
for (int i = 4; i >= 0; i--) {
printf("%s\n", toput[i]);
}
toput.clear();
return;
}
void undo() {
if (history.empty()) {
printf("ERR\n");
return;
}
opcode* ccode = &history.back();
if (ccode->optype == 1) {
map<char *, dirnode*,ptrcmp>::iterator it = workdir->sub.find(ccode->name);
workdir->sub.erase(it);
history.pop_back();
touched(-1);
printf("OK\n");
return;
}
else if (ccode->optype == 2) {
map<char *, dirnode*,ptrcmp>::iterator it = workdir->sub.find(ccode->name);
workdir->sub.insert(make_pair(ccode->name, ccode->olddir));
history.pop_back();
touched(ccode->olddir->snum);
printf("OK\n");
return;
}
else if (ccode->optype == 3) {
workdir = ccode->olddir;
history.pop_back();
printf("OK\n");
return;
}
history.pop_back();
printf("ERR\n");
}
void tree() {
if (workdir->sub.empty()) {
printf("EMPTY\n");
return;
}
if (sz() <= 10) {
if (workdir->updated) {
workdir->qianxu.clear();
preorderall(workdir,&workdir->qianxu);
workdir->updated = 0;
}
for (int i = 0; i < workdir->qianxu.size(); i++) {
printf("%s\n", workdir->qianxu[i]);
}
return;
}
if (workdir->updated) {
workdir->qianxu.clear();
workdir->houxu.clear();
int count = 5;
preorder(workdir, count, &workdir->qianxu);
count = 5;
postorder(workdir, count,&workdir->houxu);
workdir->updated = 0;
}
for (int i = 0; i < 5; i++) {
printf("%s\n", workdir->qianxu[i]);
}
printf("...\n");
for (int i = 4; i >= 0; i--) {
printf("%s\n", workdir->houxu[i]);
}
}
void preorderall(dirnode* cnode, vector<char*>* qianxu) {
qianxu->push_back(cnode->name);
for (auto it = cnode->sub.begin(); it != cnode->sub.end(); it++) {
preorderall(it->second,qianxu);
}
}
void preorder(dirnode* cnode, int& remain,vector<char*>* qianxu) {
if (remain < 1) return;
qianxu->push_back(cnode->name);
remain--;
for (auto it = cnode->sub.begin(); it != cnode->sub.end() && remain > 0; it++) {
preorder(it->second, remain,qianxu);
}
}
void postorder(dirnode* cnode, int& remain, vector<char*>* houxu) {
for (auto it = cnode->sub.rbegin(); it != cnode->sub.rend() && remain > 0; it++) {
postorder(it->second, remain,houxu);
}
if (remain < 1) return;
houxu->push_back(cnode->name);
remain--;
}
private:
dirnode* workdir;
dirnode* rmdir;
vector<opcode> history;
};
void mainloop() {
int q;
scanf("%d", &q);
dir d;
char op[8];
char * s;
for (int qi = 0; qi < q; qi++) {
scanf("%s", op);
if (op[0] == 'M') {
s = new char[24];
scanf("%s", s);
d.mkdir(s);
}
else if (op[0] == 'R') {
s = new char[24];
scanf("%s", s);
d.rm(s);
}
else if (op[0] == 'C') {
s = new char[24];
scanf("%s", s);
d.cd(s);
}
else if (op[0] == 'S') {
printf("%d\n", d.sz());
}
else if (op[0] == 'L') {
d.ls();
}
else if (op[0] == 'T') {
d.tree();
}
else if (op[0] == 'U') {
d.undo();
}
}
}
int main()
{
int t;
scanf("%d", &t);
for (int ti = 0; ti < t; ti++) {
mainloop();
if (ti != t - 1) {
printf("\n");
}
}
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
