Week9—A—咕咕东的目录管理器

题目描述：

Input：

输入文件包含多组测试数据，第一行输入一个整数表示测试数据的组数 T （T <= 20）；

每组测试数据的第一行输入一个整数表示该组测试数据的命令总数 Q （Q <= 1e5）；

每组测试数据的 2 ~ Q+1 行为具体的操作 （MKDIR、RM 操作总数不超过 5000）；

面对数据范围你要思考的是他们代表的 “命令” 执行的最大可接受复杂度，只有这样你才能知道你需要设计的是怎样复杂度的系统。

Output：

每组测试数据的输出结果间需要输出一行空行。注意大小写敏感。

时空限制：

Time limit 6000 ms
Memory limit 1048576 kB

sample input：

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

sample output：

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操作如果暴力的话，在极端情况下会超时：

   当 T = 20，numTrees = 5000，TREEs = 1e5 - 5000 = 1e5(近似)：
   
   如果用普遍前序遍历，遍历一遍需要5000的计算量，所以 t = 20 * 1e5 * 5000 = 1e10 >> 6000ms
   
   显然超时了
  

• 于是，学到了一种新方法：记忆化（缓存）

   在字典中设计：
   vector<string> pre, bck;//存前序的前面和后面的几个。
   
   bool tag;//标记是否被访问更新过
   因为对于目录相同的相同问题，是没必要重复访问的。
  

代码块：

//
// Created by 19703 on 2020/4/20.
//
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

map<string, int>cmp;
void mapp(){
    cmp["MKDIR"] = 1; cmp["RM"] = 2; cmp["CD"] = 3; cmp["SZ"] = 4; cmp["LS"] = 5; cmp["TREE"] = 6; cmp["UNDO"] = 7;
}
const int maxn = 1e5+5;
int T, Q;
vector<pair<string, pair<int, int> > >v;

struct Dict{
    string name;//节点名称
    map<string, int> mp;//子节点建立名称->编号的映射
    int fa, sz;//父亲节点、子树
    vector<string> pre, bck;//存先序遍历的前几个、后几个
    bool tag;//是否被更新过
};
int now = 0;
Dict node[maxn];
int tot = 0;
void init(){
    tot = 0;
    now = 0;
    node[now].name = "root";
    node[now].fa = -1;
    node[now].sz = 1;
    node[now].tag = 0;
    node[now].pre.clear();
    node[now].bck.clear();
    node[now].mp.clear();
    v.clear();
}
void update(int id, int num){
    while(id != -1){
        node[id].tag = 0;
        node[id].sz += num;
        id = node[id].fa;
    }
}
void mkdir(string nm){
    if(node[now].mp.count(nm)){
        cout << "ERR" << endl;
        return;
    }
    node[now].mp[nm] = ++tot;
    node[tot].name = nm;
    node[tot].fa = now;
    node[tot].sz = 1;
    node[tot].tag = 0;
    node[tot].pre.clear();
    node[tot].bck.clear();
    node[tot].mp.clear();
    update(now, 1);
    v.push_back(make_pair("MKDIR", make_pair(now, tot)));
    cout << "OK" << endl;
}
void RM(string nm){
    if(!node[now].mp.count(nm)){
        cout << "ERR" << endl;
        return;
    }
    int u = node[now].mp[nm];
    update(now, (-1) * node[u].sz);
    node[now].mp.erase(nm);
    v.push_back(make_pair("RM", make_pair(now, u)));
    cout << "OK" << endl;
}
void CD(string nm){
    if(nm == ".." && node[now].fa == -1){
        cout << "ERR" << endl;
        return;
    }else if(nm == ".."){
        v.push_back(make_pair("CD", make_pair(now, node[now].fa)));
        now = node[now].fa;
        cout << "OK" << endl;
        return;
    }
    if(!node[now].mp.count(nm)){
        cout << "ERR" << endl;
        return;
    }
    else {
        int u = node[now].mp[nm];
        v.push_back(make_pair("CD", make_pair(now, u)));
        now = u;
        cout << "OK" << endl;
    }
}
void SZ(){
    cout << node[now].sz << endl;
}
void ls(){
    int t = node[now].mp.size();
    if(t == 0){
        cout << "EMPTY" << endl;
        return;
    }
    auto pos = node[now].mp.begin();

    if(t >= 1 && t <= 10){
        while( pos != node[now].mp.end()){
            cout << pos->first << endl;
            pos++;
        }
        return;
    }
    for(int i = 1; i <= 5; ++i){
        cout << pos->first << endl;
        pos++;
    }
    cout << "..." << endl;
    pos = node[now].mp.end();
    for(int i = 0; i < 5; ++i)pos--;
    for(int i = 0; i < 5; ++i){
        cout << pos->first << endl;
        pos++;
    }
}
void UNDO(){
    if(v.empty()){
        cout << "ERR" << endl;
        return;
    }
    auto e = v[v.size() - 1];
    v.pop_back();
    int tmp = now;
    if(e.first == "MKDIR"){
        now = e.second.first;
        int u = node[now].mp[node[e.second.second].name];
        update(now, (-1)*node[u].sz);
        node[now].mp.erase(node[u].name);
        now = tmp;
    }else if(e.first == "RM"){
        now = e.second.first;
        int u = e.second.second;
        update(now, node[u].sz);
        node[now].mp[node[u].name] = u;
        now = tmp;
    }else{
        now = e.second.first;
    }
    cout << "OK" << endl;
}
void pushdown(int id);
void pretrack(int id){
    node[id].pre.push_back(node[id].name);
    if(node[id].sz == 1)return;
    if(node[id].sz <= 10){
        for(auto i:node[id].mp){
            if(!node[i.second].tag)pushdown(i.second);
            node[id].pre.insert(node[id].pre.end(), node[i.second].pre.begin(), node[i.second].pre.end());
        }
        return;
    }
    int cnt = 1;
    for(auto i:node[id].mp){
        if(!node[i.second].tag)pushdown(i.second);
        for(auto j:node[i.second].pre){
            node[id].pre.push_back(j);
            ++cnt;
            if(cnt >= 5)break;
        }
        if(cnt >= 5)break;
    }
}
void bcktrack(int id){
    int cnt = 0;
    auto iter = node[id].mp.end();
    --iter;
    for(;;--iter){
        if(!node[iter->second].tag)pushdown(iter->second);
        int u = iter->second;
        for(int i = node[u].bck.size() - 1; i >= 0; --i){
            node[id].bck.push_back(node[u].bck[i]);
            ++cnt;
            if(cnt >= 5){
                reverse(node[id].bck.begin(), node[id].bck.end());
                break;
            }
        }
        if(cnt >= 5)break;
        if(iter == node[id].mp.begin())break;
    }
}
void pushdown(int id){
    node[id].pre.clear();
    node[id].bck.clear();
    pretrack(id);
    if(node[id].sz > 10)bcktrack(id);
    else node[id].bck = node[id].pre;
    node[id].tag = 1;
}
void tree(){
    if(!node[now].tag)pushdown(now);
    if(node[now].sz == 1) cout << "EMPTY" << endl;
    else if(node[now].sz > 1 && node[now].sz <= 10){
        for(int i = 0; i < node[now].pre.size(); ++i)cout << node[now].pre[i] << endl;
    }
    else{
        for(int i = 1; i <= 5; ++i)cout << node[now].pre[i-1] << endl;
        cout << "..." << endl;
        for(int i = 5; i >= 1; --i)cout << node[now].bck[node[now].bck.size() - i] << endl;
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    mapp();
    cin >> T;
    while(T--){
        string sign, sname;
        cin >> Q;
        init();
        while(Q--){
            cin >> sign;
            switch (cmp[sign]){
                case 1:
                    cin >> sname;
                    mkdir(sname);
                    break;
                case 2:
                    cin >> sname;
                    RM(sname);
                    break;
                case 3:
                    cin >> sname;
                    CD(sname);
                    break;
                case 4:
                    SZ();
                    break;
                case 5:
                    ls();
                    break;
                case 6:
                    tree();
                    break;
                case 7:
                    UNDO();
                    break;
            }
        }
    }
    return 0;
}