A - 咕咕东的目录管理器

题目描述

咕咕东的雪梨电脑的操作系统在上个月受到宇宙射线的影响，时不时发生故障，他受不了了，想要写一个高效易用零bug的操作系统 —— 这工程量太大了，所以他定了一个小目标，从实现一个目录管理器开始。前些日子，东东的电脑终于因为过度收到宇宙射线的影响而宕机，无法写代码。他的好友TT正忙着在B站看猫片，另一位好友瑞神正忙着打守望先锋。现在只有你能帮助东东！

初始时，咕咕东的硬盘是空的，命令行的当前目录为根目录 root。

目录管理器可以理解为要维护一棵有根树结构，每个目录的儿子必须保持字典序。

现在咕咕东可以在命令行下执行以下表格中描述的命令：

WEEK9 作业 A - 咕咕东的目录管理器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

题解

整个目录是一棵树形结构，每个节点包含当前目录的名字，子目录的集合（map<子目录名字，指针>，子目录是有序的），纸箱上一级目录的指针，子目录的数目，缓存十个后代目录列表（缓存全部（<=10）或前5个和后5个（>10），为懒更新做准备），该目录下的子列表有没有更新过的标志（为懒更新做准备，进行删除或者添加子目录时改为1，更新过后代目录列表后改为0）。

懒更新，每次运行tree时都重新遍历后代太复杂，会超时。所以我们采用懒更新的方法，在每次遍历完成后都将此时的后代储存起来，同时置updated为0，若有操作更新了此节点的后代则改为1，下次调用此节点的tree时，若updated为0则该节点的子树没有被更新过，直接输出即可，updated为1时则需重新遍历。

为了undo方便，在前三种操作中，如果操作成功了，就要将操作类型和改变的节点储存起来，mkdir的撤销可以直接调用rm，但是rm的撤销不可以直接调用mkdir，因为有可能删除的是一个带子目录的目录，需要将子目录与目录都加进目录列表才能变回原来的状态。因此我们将删除的目录储存起来（子目录仍然挂在目录下面）。

在for循环中用迭代器遍历数组时，i与it要同时++。

注意subtreeSize是本目录和所有子目录的集合。

代码

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
#include <map>
using namespace std;

char tmps[20];//辅助输入的字符数组  
struct directory{
	string name;//当前目录的名字
	map<string,directory*>children;//孩子目录
	directory*parent;
	int subtreeSize;//子树大小
	vector<string>*ten;//缓存0个后代 
	bool updated;//有没有被问过 
	directory(string name,directory*parent){
		this->name=name;
		this->parent=parent;
		this->subtreeSize=1;
		ten=new vector<string>;
		updated=1;
	} 
	bool addchild(directory*ch){
		if(children.find(ch->name)!=children.end()){return 0;}
		children[ch->name]=ch;
		maintain(+ch->subtreeSize);
		return 1;
	} 
	
	directory* getchild(string name){
		auto it=children.find(name);
		if(it==children.end()){return NULL;}
		else{return it->second;}
	}
	
	directory*mkdir(string name){
		if(children.find(name)!=children.end())
		{return NULL;}//已经有这个子目录,不创建 
		directory*ch=new directory(name,this);
		children[name]=ch;
		maintain(1);
		return ch; 
	}
		
	directory*rm(string name){
		auto it= children.find(name);
		if(it==children.end()){return NULL;}//不存在这个子目录,无法删除
		maintain(-1*it->second->subtreeSize);
		directory*temp=it->second;///本来没有这一步 
		children.erase(it);
		return temp; 
	} 
	
	directory*cd(string name){
		if(name==".."){return this->parent;}
		return getchild(name);//不存在会返回来NULL 
	}
	
	void maintain(int d){
		this->updated=1; 
		subtreeSize+=d;
		if(parent!=NULL){
			parent->maintain(d);
		}
	}
	
	void sz(){//输出当前目录的大小
		printf("%d\n",this->subtreeSize);
	}
		
	void ls(){//输出多行表示当前目录的 "直接子目录" 名
		int sz=children.size();//孩子数
		if(sz==0){printf("EMPTY\n");}
		else if(sz<=10){
			for(auto &i:children)
				printf("%s\n",i.first.c_str());
		}else{
			auto it=children.begin();
			for(int i=0;i<5;i++,it++)
				printf("%s\n",it->first.c_str());
			printf("...\n");
			it=children.end();
			for(int i=0;i<5;i++)it--;
			for(int i=0;i<5;i++){//一开始忘了it++ 
				printf("%s\n",it->first.c_str()); 
				it++;
			}
		}
	}
	
	void tree(){
		if(subtreeSize==1)printf("EMPTY\n");
		else if(subtreeSize<=10){//误以为+1 
			if(this->updated){//更新过 
				ten->clear();
				treeAll(ten);
				this->updated=0; 
			}
			for(int i=0;i<subtreeSize;i++){
				printf("%s\n",ten->at(i).c_str());
			}
		}else{
			if(this->updated){//更新过 
				ten->clear();
				treeFirst(5,ten);
				treeLast(5,ten);
				this->updated=0; 
			}
			for(int i=0;i<5;i++){
				printf("%s\n",ten->at(i).c_str());
			}
			printf("...\n");
			for(int i=9;i>=5;i--){
				printf("%s\n",ten->at(i).c_str());
			}
		}
	}
private:
	void treeAll(vector<string>*v){
		v->push_back(name);
		for(auto &i:children){
			i.second->treeAll(v);
		}
	}
	void treeFirst(int num,vector<string>*v){
		v->push_back(name);
		if(--num==0){return;}
		int n=children.size();
		auto it=children.begin();
		while(n--){
			int sts=it->second->subtreeSize;//孩子的大小 
			if(sts>=num){
				it->second->treeFirst(num,v);
				return;
			} else{
				it->second->treeFirst(sts,v);错写为num 
				num-=sts; 
			}
			it++;
		}
	}
	void treeLast(int num,vector<string>*v){
		int n=children.size();
		auto it=children.end();
		while(n--){
			it--;
			int sts=it->second->subtreeSize;//孩子的大小 
			if(sts>=num){
				it->second->treeLast(num,v);
				return;
			} else{
				it->second->treeLast(sts,v);
				num-=sts; 
			}
		}
		v->push_back(name);
	}	
};

struct Command{
	const string CMD_NAMES[7]={"MKDIR","RM","CD","SZ","LS","TREE","UNDO"}; 
	int type;//命令的类型 0->mkdir 1->rm 2->cd
			 //3->sz 4->ls 5->tree 6->undo  
	string arg;//命令参数
	directory*tmpdir;//刚刚操作涉及的目录节点 
	Command(string s){//构造函数 
		tmpdir=NULL;
		for(int i=0;i<7;i++)if(CMD_NAMES[i]==s){
			type=i;
			if(type<3){scanf("%s",tmps);arg=tmps;}
			return;
		} 
	} 
};
vector<Command*>cmdlist;//已经成功的命令

void solve(){//对每一组测试数据 
	int n; scanf("%d",&n);//每组数据有n行
	directory*now=new directory("root",NULL);
	vector<Command*>cmdlist;//已经成功的命令
	while(n--){ 
	 	scanf("%s",tmps);
	 	Command*cmd=new Command(tmps);
	 	switch(cmd->type)
		{
	 	case 0:{//mkdir
	 		cmd->tmpdir=now->mkdir(cmd->arg);
	 		if(cmd->tmpdir==NULL){printf("ERR\n");}
			else{
				printf("OK\n");
				cmdlist.push_back(cmd); 
			}
			break;
		}
	 	case 1:{//rm
	 		cmd->tmpdir=now->rm(cmd->arg);
	 		if(cmd->tmpdir==NULL){printf("ERR\n");}
			else{
				printf("OK\n");
				cmdlist.push_back(cmd); 
			}
			break;
		}
	 	case 2:{
		 	//cd
	 		directory*ch=now->cd(cmd->arg);//
	 		if(ch==NULL){printf("ERR\n");}
			else{
				printf("OK\n");
				cmd->tmpdir=now;//将当前目录存起来，undo直接回这里 
				now=ch;//进入新目录 
				cmdlist.push_back(cmd); 
			}
			break;
		}
	 	case 3://sz
			now->sz();break;
	 	case 4://ls
			now->ls();break;
	 	case 5://tree
	 		now->tree();break;
	 	case 6:{//undo
			bool success=false;
			if(!cmdlist.empty()){//一开始这里是while 
				cmd=cmdlist.back();cmdlist.pop_back();
				switch(cmd->type){
					case 0:success=now->rm(cmd->tmpdir->name)!=NULL;break;
					case 1:success=now->addchild(cmd->tmpdir)!=NULL;break;
					case 2:now=cmd->tmpdir;success=1;break;
				} 
			} 
			printf(success?"OK\n":"ERR\n");
			break;
		}
		}
	} 
}

int main(int argc, char** argv) {
	int t;scanf("%d",&t);
	while(t--){solve();}
	return 0;
}

WEEK9 作业 A - 咕咕东的目录管理器A - 咕咕东的目录管理器

A - 咕咕东的目录管理器

题目描述

Input

Output

限制

Sample Input

Sample Output

题解

代码

继续阅读

WEEK4 csp模拟 A-咕咕东的奇遇A-咕咕东的奇遇

WEEK4 csp模拟 B-咕咕东想吃饭B-咕咕东想吃饭

WEEK12 csp模拟 T4 咕咕东学英语

程序设计与实践 week13 T1T2专练ABCE

WEEK11 作业 C - 必做题11-3C - 必做题11-3

WEEK12 作业 C - 必做题3C - 必做题3

WEEK13 作业 A - TT 的神秘任务1（必做）A - TT 的神秘任务1（必做）