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（必做）