题目描述：
思路：
真的是不知道该说什么，因为我一直WA，简直要Crazy了....自己造数据对拍了很长时间，也没找到问题所在，后来（被迫）借鉴了标准代码，如果能找到测试点，则我的程序还能有救
但是还是要说一下主要的点：
- 查多改少，可以使用懒更新，或者说记忆化，防止重复计算；查多改少可以根据仔细分析数据范围得出
- 输出树的前五个节点比较容易，但是输出树的后五个节点就不那么容易，仍然可以使用递归，递归时要记录现在还需要输出多少个节点，不要使用引用而是使用传值
- 但是我是真的不知道，下述代码为什么WA...，毕竟这是道模拟，没有那么重要，等有机会重写一下，再研究
代码：
WA代码：
//可能连续多次UNDO,所以所有的操作命令都要存储
//1s , 1e8
//6s , 6e8
//很多次查询,要善于利用缓存的思想,因为计算已经知道的答案代价高
//特别是对于,查多改少(分析输入数据)的情况,记忆画能省很多时间
//考虑用这节课的动态分配内存去修改树和森林
//记录size? 遍历需要O(n),向上层更新需要O(h),可以都试试?
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
struct subTree
{
string name;
map<string,subTree*> children;
subTree *parent;
int treeSize;
bool dirty; //脏位
vector<string> tenChildren;
subTree(const string &ts,subTree *p) { dirty=1; treeSize=1; name=ts; parent=p; children.clear();tenChildren.clear(); }
};
class directory //目录是一层一层进入的,所以必须指明找到每个节点的路径,和DSA2略微不同?
{
protected:
subTree *root,*now;
stack< pair<int,string> > op; //执行过的操作,如果是删除目录,很可能把子目录也删除了,这时候删除的目录,只删除关系,不删除内存
stack<subTree*> trashBin;
void updateSize(int );
void preOutput(subTree *);
void preOutFirst(int ,subTree *);
void postOutLast(int ,subTree *);
public:
directory()
{
root=new subTree("root",nullptr);
now=root;
}
void makeDir(string &);
void removeDir(string &);
void cd(const string &);
int sizeOfNowDir() { return now->treeSize; }
void listNowDir();
void printNowDir();
void undo();
};
void directory::updateSize(int delta) //delta==Δ 没问题
{
now->treeSize+=delta;
now->dirty=1;
auto p=now->parent;
while(p!=nullptr)
{
p->dirty=1;
p->treeSize+=delta;
p=p->parent;
}
}
void directory::preOutput(subTree *p)
{
cout<<p->name<<endl;
now->tenChildren.push_back(p->name);
for(auto &child:p->children)
preOutput(child.second);
}
void directory::preOutFirst(int num,subTree *p)
{
now->tenChildren.push_back(p->name);
if(--num==0) return;
int n=p->children.size();
auto it=p->children.begin();
while(n--)
{
int sts=it->second->treeSize;
if(sts>=num)
{
preOutFirst(num,it->second);
return;
}
else
{
preOutFirst(sts,it->second);
num-=sts;
}
it++;
}
}
void directory::postOutLast(int num,subTree *p)
{
int n=p->children.size();
auto it=p->children.end();
while(n--)
{
it--;
int sts=it->second->treeSize;
if(sts>=num)
{
postOutLast(num,it->second);
return;
}
else
{
postOutLast(sts,it->second);
num-=sts;
}
}
now->tenChildren.push_back(p->name);
}
void directory::makeDir(string &ts) //没问题
{
if(now->children.find(ts)!=now->children.end())
{
//已经有这个目录
cout<<"ERR"<<endl;
return;
}
//新建一个目录
subTree *newNode=new subTree(ts,now);
now->children[ts]=newNode;
updateSize(1); //更新这层及上层节点数量
cout<<"OK"<<endl;
op.push(make_pair(1,ts)); //存储成功的操作
}
void directory::removeDir(string &ts) //没问题
{
if(now->children.find(ts)==now->children.end())
{
//如果要删除的目录不存在
cout<<"ERR"<<endl;
return;
}
//删除目录,把目录的内存放进垃圾桶trashBin
trashBin.push(now->children[ts]);
updateSize(-now->children[ts]->treeSize); //删除的是整个文件夹,包括子目录
now->children.erase(ts);
cout<<"OK"<<endl;
op.push(make_pair(2,ts));
}
void directory::cd(const string &ts) //没问题
{
if(ts=="..")
{
if(now==root) cout<<"ERR"<<endl;
else
{
//回到上层目录,则把当前的目录名存起来
op.push(make_pair(3,now->name));
now=now->parent;
cout<<"OK"<<endl;
}
return;
}
if(now->children.find(ts)==now->children.end())
{
cout<<"ERR"<<endl;
return;
}
op.push(make_pair(4,now->name)); //其实进入内层目录可以用父亲指针跳出来
now=now->children[ts];
cout<<"OK"<<endl;
}
void directory::listNowDir() //没问题
{
if(now->children.empty())
{
cout<<"EMPTY"<<endl;
return;
}
if(now->children.size()<=10)
{
for(auto x:now->children)
cout<<x.first<<endl;
return;
}
auto itb=now->children.begin(),ite=now->children.end();
for(int i=1;i<=5;i++)
{
cout<<itb->first<<endl;
++itb;
ite--;
}
cout<<"..."<<endl;
for(int i=1;i<=5;i++)
{
cout<<ite->first<<endl;
++ite;
}
}
void directory::printNowDir() //没问题
{
if(now->treeSize==1)
{
cout<<"EMPTY"<<endl;
return;
}
if(now->dirty==0)
{
for(auto x:now->tenChildren)
cout<<x<<endl;
return;
}
now->tenChildren.clear();
now->dirty=0;
if(now->treeSize<=10)
{
preOutput(now);
return;
}
//前序5个,后序五个
preOutFirst(5,now);
now->tenChildren.push_back("...");
postOutLast(5,now);
reverse(now->tenChildren.begin()+6,now->tenChildren.end());
for(auto x:now->tenChildren)
cout<<x<<endl;
}
void directory::undo()
{
if(op.empty())
{
cout<<"ERR"<<endl;
return;
}
auto t=op.top();
op.pop();
switch(t.first)
{
case 1:removeDir(t.second);break;
case 2: //把垃圾桶的东西整体回收
now->children[t.second]=trashBin.top();
cout<<"OK"<<endl;
updateSize(trashBin.top()->treeSize);
trashBin.pop();
break;
case 3:cd(t.second);break; //cd..的负操作
case 4:cd("..");break;
}
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
int T; cin>>T;
int first=1;
while(T--)
{
if(!first) cout<<endl;
directory C;
int Q; cin>>Q;
while(Q--)
{
string op,obj;
cin>>op;
if(op=="MKDIR") cin>>obj,C.makeDir(obj);
else if(op=="RM") cin>>obj,C.removeDir(obj);
else if(op=="CD")
{
cin>>obj;
C.cd(obj);
}
else if(op=="SZ")
cout<<C.sizeOfNowDir()<<endl;
else if(op=="LS") C.listNowDir();
else if(op=="TREE") C.printNowDir();
else if(op=="UNDO") C.undo();
}
first=0;
}
return 0;
}
AC代码：
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
char tmps[20];
struct Directory
{
string name;//当前目录的名字
map<string, Directory*>children;
Directory* parent;//以备CD.. 返回上级目录
int subtreeSize;//以备sz要输出子树大小
vector<string>* tenDescendants;//保存当前节点的十个后代
Directory(string name, Directory* parent)
{
this->name = name;
this->parent = parent;
this->subtreeSize = 1;
this->tenDescendants=new vector<string>;
}
bool updated;//记录当前节点的子孙有无变动，无变动则十个后代无需更新
public:
void maintain(int delta) //向上维护子树大小
{
updated = true;
subtreeSize += delta;
if (parent != nullptr)
parent->maintain(delta);
}
void tree()
{
if (subtreeSize == 1) printf("EMPTY
");
else if (subtreeSize <= 10)
{
if (this->updated)
{
tenDescendants->clear();
treeAll(tenDescendants);
this->updated = false;
}
for (int i = 0; i < subtreeSize; i++)
{
printf("%s
", tenDescendants->at(i).c_str());
}
}
else
{
if (this->updated)
{
tenDescendants->clear();
treeFirstSome(5, tenDescendants);
treeLastSome(5, tenDescendants);
this->updated = false;
}
for (int i = 0; i < 5; i++)
{
printf("%s
", tenDescendants->at(i).c_str());
}
printf("...
");
for (int i = 9; i >= 5; i--)
{
printf("%s
", tenDescendants->at(i).c_str());
}
}
}
Directory* getChild(string name) //取子目录并返回，不存在返回空指针
{
auto it = children.find(name);
if (it == children.end()) return nullptr;
return it->second;
}
Directory* mkdir(string name) //创建子目录并返回，创建失败返回空指针
{
if (children.find(name) != children.end()) return nullptr;
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 nullptr;
maintain(-1 * it->second->subtreeSize);
children.erase(it);
return it->second;
}
Directory* cd(string name)
{
if (".." == name)
{
return this->parent;
}
return getChild(name);
}
bool addChild(Directory* ch)//加入子目录并判断成功与否
{
if (children.find(ch->name) != children.end())
{
return false;
}
children[ch->name] = ch;
maintain(+ch->subtreeSize);
return true;
}
void sz()
{
printf("%d
", this->subtreeSize);
}
void ls()
{
int sz = children.size();
if (sz == 0) printf("EMPTY
");
else if (sz <= 10)
{
for (auto& entry : children)
{
printf("%s
", entry.first.c_str());
}
}
else
{
auto it = children.begin();
for (int i = 0; i < 5; i++, it++)
{
printf("%s
", it->first.c_str());
}
printf("...
");
it = children.end();
for (int i = 0; i < 5; i++) it--;
for (int i = 0; i < 5; i++, it++)
{
printf("%s
", it->first.c_str());
}
}
}
private:
void treeAll(vector<string>* bar) //更新全桶
{
bar->push_back(name);
for (auto &entry : children)
{
entry.second->treeAll(bar);
}
}
void treeFirstSome(int num, vector<string>* bar)//更新前序几个
{
bar->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->treeFirstSome(num, bar);
return;
}
else
{
it->second->treeFirstSome(sts, bar);
num -= sts;
}
it++;
}
}
void treeLastSome(int num, vector<string>* bar)//更新后序几个
{
int n = children.size();
auto it = children.end();
while (n--)
{
it--;
int sts = it->second->subtreeSize;
if (sts >= num)
{
it->second->treeLastSome(num, bar);
return;
}
else
{
it->second->treeLastSome(sts, bar);
num -= sts;
}
}
bar->push_back(name);
}
};
struct Command
{
int type;//命令的类型
string arg;//命令的参数
const string CMDNAMES[7] = { "MKDIR","RM","CD","SZ","LS","TREE","UNDO" };
Command(string s)
{//构造函数
for(int i=0;i<7;i++)
if (CMDNAMES[i] == s)
{
type = i;
if (i < 3) //MKDIR、RM、CD的参数后续读入
{
scanf("%s", tmps), arg = tmps;
}
return;
}
}
Directory* tmpDir;//记录刚刚操作涉及的目录节点
};
void solve()
{
int n;
cin>>n;
//scanf("%d",&n); //每组数据有m行命令
Directory *now = new Directory("root", nullptr);
vector<Command*>cmdList;//新增加的数组存成功执行的命令以备undo
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 == nullptr) printf("ERR
");
else
{
printf("OK
");
cmdList.push_back(cmd);
}
break;
}
case 1://RM
{
cmd->tmpDir = now->rm(cmd->arg);
if (cmd->tmpDir == nullptr) printf("ERR
");
else
{
printf("OK
");
cmdList.push_back(cmd);
}
break;
}
case 2://CD
{
Directory * ch = now->cd(cmd->arg);
if (ch == nullptr)printf("ERR
");
else
{
printf("OK
");
cmd->tmpDir = now;
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;//undo执行成功与否
while (!success && !cmdList.empty())
{
cmd = cmdList.back(); cmdList.pop_back();
switch (cmd->type)
{
case 0://UNDO MKDIR
success = now->rm(cmd->arg) != nullptr;
break;
case 1://UNDO RM
success = now->addChild(cmd->tmpDir);
break;
case 2: //UNDO CD
now = cmd->tmpDir;
success = true;
break;
}
}
printf(success ? "OK
" : "ERR
");
}
}
}
printf("
");
}
int main()
{
int T; cin>>T;
while(T--)
solve();
return 0;
}