题意:
样例输入:
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
时空限制:
Time limit 6000 ms
Memory limit 1048576 kB
思路:
初见题意,操作非常多。共有7个操作,为了实现这些操作,我们设立一个目录结构体Directory,里面的数据变量有当前目录的名字,他的子目录,由于题目要求子目录必须按照名字的字典序排列,因此我们可以使用map结构,map结构内部实现一棵红黑树保证其有序,并且map提供一对一的hash,这对我们找到目录的某个子目录非常有用,map< string, Directory* >children这样我们便可以通过子目录的名字直接找到对应的子目录,Directory里的数据变量还有他的父节点目录指针,以及他所在的子目录的目录数目,还有一个用来存储最多包含他在内的最多十个目录名字的缓存,以及表示缓存是否更新的bool变量。
我们开始看操作。对于操作我们也需要设立一个结构体来方便管理,共7个操作我们可以设立一个字符数组来帮我们判断是哪个操作,以及为前三个操作设立的一个参数argument,由于我们可能会undo,所以对这个操作的目标目录我们需要设立一个指针指向它,方便撤回操作。
由于操作可能会改变目录里的东西,可能会改变子目录的数目,因此我们设立一个由下往上维护大小的函数void maintain(int del),来帮助我们改变大小。二可能进行的undo操作,则要求我们将类型是前三个的操作用数组记录下来方便我们撤回。
第一个操作“MKDIR s”,是在当前目录下设立一个子目录名为s,我们首先啊判断当前目录有没有一个名为s的目录,若是已有返回NULL用来判断失败,若是没有,则在这个目录的子目录中加入新的目录,即map对象children里加入,并且将这个新的目录返回指针,用来给这个操作对象的目标目录指针赋值,接着将他记录在操作数组里。第二个"RM s"操作则要求我们删除子目录,同样是先判断有没有,有则删除,无则返空,成功的话也要记录下来。第三个"CD s"则操作时进入新的目录中,若是参数时“. .”,则要判断父节点是不是空,若是其他则要判断有没有这个子目录名,成功进入的操作要记录在操作数组里。第四个是"SZ",我们直接输出结构体里表示目录数目的对象即可,第五个是"LS",我们需要分两种情况,若是他直接孩子目录数目在10以内则直接输出,否则遍历前五个和后五个输出。第七个操作是“UNDO”,我们就从之前的指令数组中取出指令,删除了的话则添加,添加了的就删除,进入的就出去。
第六个操作tree操作要非常注意,通过观察题目数据,我们可以看到MKDIR和RM操作非常少,其他的操作很多,这就意味着节点数远远小于tree操作数,可能会有重复操作的情况,因此对于没有改变的情况下,tree的计算过程应该只有一次,因此我们设立了一个最多记录10个目录的数组用作缓存,以及表示更新的bool变量,缓存的更新情况是在MKDIR和RM指令时,而这两个指令会调用maintain函数,所以可以在maintain里设置变量更新为true表示缓存已经更新过,若是缓存没有更新过,那么直接输出,否则则需要重新遍历计算。
总结:
对于这种复杂的模拟题,我们可以先不管细节,先理清整体思路;
对于题目要求我们要注意利用技巧减少时间耗时,如题目中利用缓存技巧;
设计树形数据结构时比起O(n) 用map 可以O(logn) 来找子目录;
注意:复制粘贴是原罪,即使指示重复的几行代码,负值粘贴过去就很有可能导致有些地方没改出错,又很难找出来。。。
代码:
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<string.h>
using namespace std;
char tms[20];
struct Directory;
struct command
{
const string CMD_NAMES[7] = { "MKDIR","RM","CD","SZ","LS","TREE","UNDO" };
int type;
string argument;
Directory* target_dir;
command(string& t)
{
for (int i = 0; i < 7; i++)if (t == CMD_NAMES[i])type = i;
if (type < 3)
{
scanf("%s", tms);
argument = tms;
}
}
};
struct Directory
{
string name;
map<string, Directory*>children;
Directory* parent;
int subtreeSize;
vector<string>* tenDescend;
bool update;
Directory(string _name, Directory* _parent)
{
name = _name;
parent = _parent;
subtreeSize = 1;
update = true;
tenDescend = new vector<string>;
}
Directory* makedir(string &x);
Directory* getchild(string& x);
Directory* rm(string &x);
Directory* cd(string &x);
void maintain(int x);
void ls();
void sz()
{
printf("%d\n", subtreeSize);
};
void tree();
Directory* addchild(Directory* x);
void treeall(vector<string>* x);
void treeFirstFive(int n, vector<string>* x);
void treeLastFive(int n, vector<string>* x);
};
Directory* Directory::getchild(string& x)
{
map<string, Directory*>::iterator iter = children.find(x);
if (iter == children.end())return NULL;
else
return iter->second;
}
Directory* Directory::cd(string& x)
{
if (x == "..")
return parent;
else return getchild(x);
}
Directory* Directory::makedir(string& x)
{
map<string, Directory*>::iterator iter = children.find(x);
if (iter != children.end())return NULL;
Directory* te= new Directory(x, this);
children[x] = te;
maintain(1);
return te;
}
Directory* Directory::addchild(Directory* x)
{
map<string, Directory*>::iterator iter = children.find(x->name);
if (iter != children.end())return NULL;
else children[x->name] = x;
maintain(1 * x->subtreeSize);
return x;
}
Directory* Directory::rm(string& x)
{
map<string, Directory*>::iterator iter = children.find(x);
if (iter == children.end())return NULL;
maintain(-1 * iter->second->subtreeSize);
Directory* temptt = iter->second;
children.erase(iter);
return temptt;
}
void Directory::maintain(int del)
{
update = true;
subtreeSize += del;
if (parent != NULL)parent->maintain(del);
}
void Directory::ls()
{
int size = children.size();
if (size == 0)printf("EMPTY\n");
else
{
if (size <= 10)
{
map<string, Directory*>::iterator iter = children.begin();
for (; iter != children.end(); iter++)
{
printf("%s\n", iter->first.c_str());
}
}
else
{
map<string, Directory*>::iterator iter = children.begin();
for(int pl = 0;pl<5;pl++,iter++)
printf("%s\n", iter->first.c_str());
printf("...\n");
iter = children.end();
for (int pl = 0; pl < 5; pl++)iter--;
for (int pl = 0; pl < 5; pl++, iter++)
printf("%s\n", iter->first.c_str());
}
}
}
void Directory::tree()
{
if (subtreeSize == 1)
{
printf("EMPTY\n");
}
else
{
if (subtreeSize <= 10)
{
if (update)
{
tenDescend->clear();
treeall(tenDescend);
update = false;
}
int sz = tenDescend->size();
for (int i = 0; i < sz; i++)
{
printf("%s\n", tenDescend->at(i).c_str());
}
}
else {
if (update)
{
tenDescend->clear();
treeFirstFive(5,tenDescend);
treeLastFive(5, tenDescend);
update = false;
}
for (int i = 0; i < 5; i++)
{
printf("%s\n", tenDescend->at(i).c_str());
}
printf("...\n");
for (int i = 9; i >= 5; i--)
{
printf("%s\n", tenDescend->at(i).c_str());
}
}
}
}
void Directory::treeall(vector<string>* x)
{
x->push_back(name);
for (map<string, Directory*>::iterator iter = children.begin(); iter != children.end(); iter++)
{
iter->second->treeall(x);
}
}
void Directory::treeFirstFive(int n, vector<string>* x)
{
x->push_back(name);
if (--n == 0)return;
int size = children.size();
map<string, Directory*>::iterator it = children.begin();
while (size--)
{
int sizet = it->second->subtreeSize;
if (sizet >= n)
{
it->second->treeFirstFive(n, x);
return;
}
else
{
it->second->treeFirstFive(sizet, x);
n -= sizet;
}
it++;
}
}
void Directory::treeLastFive(int n, vector<string>* x)
{
int size = children.size();
map<string, Directory*>::iterator it = children.end();
while (size--)
{
it--;
int sizet = it->second->subtreeSize;
if (sizet >= n)
{
it->second->treeLastFive(n, x);
return;
}
else
{
it->second->treeLastFive(sizet, x);
n -= sizet;
}
}
x->push_back(name);
}
void solve()
{
long long n;
scanf("%lld", &n);
Directory* now = new Directory("root", NULL);
vector<command*>cmdlist;
for (int i = 0; i < n; i++)
{
scanf("%s", tms);
string x = tms;
command* cmd = new command(x);
switch (cmd->type)
{
case 0:
{
cmd->target_dir = now->makedir(cmd->argument);
if (cmd->target_dir == NULL)printf("ERR\n");
else
{
printf("OK\n");
cmdlist.push_back(cmd);
}
break;
}
case 1:
{
cmd->target_dir = now->rm(cmd->argument);
if (cmd->target_dir == NULL)printf("ERR\n");
else
{
printf("OK\n");
cmdlist.push_back(cmd);
}
break; }
case 2: {
Directory*te = now->cd(cmd->argument);
if(te == NULL)printf("ERR\n");
else {
printf("OK\n");
cmd->target_dir = now;
now = te;
cmdlist.push_back(cmd);
}
break; }
case 3:now->sz(); break;
case 4:now->ls(); break;
case 5:now->tree(); break;
case 6: {
bool judge = false;
if(!cmdlist.empty())
{
cmd = cmdlist.back(); cmdlist.pop_back();
switch (cmd->type)
{
case 0:
if (now->rm(cmd->target_dir->name) != NULL)judge = true; break;
case 1:
if (now->addchild(cmd->target_dir) != NULL)judge = true; break;
case 2:
now = cmd->target_dir; judge = true; break;
default:
break;
}
}
if (judge)printf("OK\n"); else printf("ERR\n");
}
default:
break;
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T-- != 0)
{
solve();
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)