【模拟】咕咕东的目录管理器

本文主要是介绍【模拟】咕咕东的目录管理器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

咕咕东的雪梨电脑的操作系统在上个月受到宇宙射线的影响，时不时发生故障，他受不了了，想要写一个高效易用零bug的操作系统 —— 这工程量太大了，所以他定了一个小目标，从实现一个目录管理器开始。前些日子，东东的电脑终于因为过度收到宇宙射线的影响而宕机，无法写代码。他的好友TT正忙着在B站看猫片，另一位好友瑞神正忙着打守望先锋。现在只有你能帮助东东！
初始时，咕咕东的硬盘是空的，命令行的当前目录为根目录 root。
目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。

现在咕咕东可以在命令行下执行以下表格中描述的命令：
在这里插入图片描述

输入

输入文件包含多组测试数据，第一行输入一个整数表示测试数据的组数 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

思路

本题工作量巨大，这里只讲几个重要的步骤，在TREE的时候，对于大于十个的答案要进行后序遍历，将总数5从后向前分配给子树。注意，由于整个过程的最坏复杂度为 $O (n)$ ，n最大为5000，而tree的操作可能有很多，考虑到插入删除的操作个数不超过5000，所以可以记录结果，再变动时结果标记为失效，下一次TREE有效结果直接输出，否则求解一遍再输出。undo操作需要用栈记录每一次插入删除和cd操作的逆操作,然后undo时直接按照当前的逆操作调用相应的正操作函数即可。

亿点细节，此题最有效的总结方式就是以后有时间的时候再码一遍。

代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<set>
#include<vector>
#include<stack>
#include<map>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define mem(a,s) memset(a,s,sizeof(a))
const int N = 5e3 + 10;
class Dir{public:int f,sum;string name;map<string, int> child;vector<string> ans;bool up;void init(string s,int fa){f=fa;name=s;sum = 1;up = false;child.clear();ans.clear();}bool getChild(string s) {return child.find(s) == child.end() ? 0 : 1;}void outChild(){int len=child.size();if(len==0){cout << "EMPTY" << endl;return;}if(len<=10){for(auto it:child)cout << it.first << endl;return;}int j = 0;for(auto it:child){j++;cout << it.first << endl;if(j==5)break;}cout<<"...\n";auto it=child.end();rep(i,0,4)it--;rep(i, 0, 4)cout<< it->first << endl,++it;}
}node[N];
vector<pair<int, int>> st;
int tot,now;
//
void insert(int f,int c){node[f].child.insert({node[c].name, c});int p = node[c].f;while(p!=-1){node[p].sum += node[c].sum;node[p].up = 0;p = node[p].f;}
}
//
void erase(int f,int c){node[f].child.erase(node[c].name);int p = node[c].f;while(p!=-1){node[p].up = 0;node[p].sum -= node[c].sum;p = node[p].f;}
}
//
void init(){tot = now = 0;node[0].init("root",-1);st.clear();
}
void outAll(int x,int f){node[f].ans.push_back(node[x].name);for(auto it:node[x].child)outAll(it.second, f);
}
void preOrder(int num,int x,int f){node[f].ans.push_back(node[x].name);if(--num ==0)return;int n = node[x].child.size();auto it =node[x].child.begin();while(n--){int sl = node[it->second].sum;if(sl>=num){preOrder(num,it->second, f);return;}else{preOrder(sl, it->second, f);num -= sl;}it++;}
}
void postOrder(int num,int x,int f){int n = node[x].child.size();auto it = node[x].child.end();while(n--){it--;int sl = node[it->second].sum;if(sl>=num){postOrder(num,it->second, f);return;}else{postOrder(sl, it->second, f);num -= sl;}            }node[f].ans.push_back(node[x].name);
}
//
void make_node(string name,int f){node[++tot].init(name,f);}
void output(){Dir &dir = node[now];if (dir.sum == 1){cout << "EMPTY" << endl;return;}if(!dir.up){dir.up = 1;dir.ans.clear();if(dir.sum<=10){outAll(now, now);}else{preOrder(5,now,now);dir.ans.push_back("...");postOrder(5,now, now);reverse(dir.ans.begin()+6, dir.ans.end());}}for(auto it:dir.ans)cout << it << endl;return;          
}
//
void undo(){if(st.empty()){cout << "ERR" << endl;return;}cout << "OK" << endl;int op = st[st.size()-1].first, dir = st[st.size()-1].second;st.pop_back();switch (op){case 0:erase(now, dir);break;case 1:insert(now, dir);break;case 2:now = dir;break;}
}
int main(){//   freopen("in.txt","r",stdin);cin.sync_with_stdio(false);int T,Q;map<string, int> opt;opt["MKDIR"] = 0;opt["RM"] = 1;opt["CD"] = 2;opt["SZ"] = 3;opt["LS"] = 4;opt["TREE"] = 5;opt["UNDO"] = 6;cin>>T;while(T--){init();cin>>Q;while(Q--){string op,x;int num;cin >> op;switch(opt[op]){case 0:cin >> x;if(!node[now].getChild(x)){make_node(x, now);insert(now,tot);st.push_back({0,tot});cout << "OK" << endl;}elsecout << "ERR" << endl;break;case 1: cin>>x;if(node[now].getChild(x)){erase(now,num=node[now].child[x]);st.push_back({1, num});cout << "OK" << endl;}elsecout << "ERR"<<endl;break;case 2:cin >> x;if(x==".."){if(now==0){cout << "ERR" << endl;break;}num = now;now = node[now].f;}else{if(!node[now].getChild(x)){cout << "ERR" << endl;break;}num = now;now = node[now].child[x];}st.push_back({2, num});cout << "OK" << endl;break;case 3:cout << node[now].sum << endl;break;case 4:node[now].outChild();break;case 5:output();break;case 6:undo();break;}}if(T)cout << endl;}return 0;
}