首页 > 代码库 > ACM-ICPC Beijing Online A The Book List

ACM-ICPC Beijing Online A The Book List

比赛的时候一眼就看出是字典树+DFS了,然而这题题意比较难理解,还有不少WA点。所以很快敲完之后和队友反复斟酌题意,修改代码。结果还是交了3发WA。最后猜测目录和书在同一个母目录域下同名是不同的,增加了状态标记才AC。

赛后觉得比赛的时候写得比较乱,所以抽空重构了一遍。

#include <iostream>#include <vector>#include <algorithm>#include <queue>#include <map>#include <string>using namespace std;struct kk//作为map的key,因为题目中,同名的书和目录是不同的,所以设置一个状态标记{    string s;    int f;    friend bool operator < (kk a,kk b)//设定重载一定要考虑状态标记,不然map在查找的时候会不考虑状态标记的区别    {        if(a.s==b.s)            return a.f<b.f;        return a.s<b.s;    }};struct node//字典树结构体,比赛的时候直接扔模板了,今天手写了一遍{    map<kk,node*> m;    string s;    void ini()    {        m.clear();    }}head;void Ins(vector<string> &s)//字典树的插入{    int f;    node* p=&head;    for(int i=0;i<s.size();i++)    {        if(i==s.size()-1) f=1;//除了最后一本都是目录        else f=0;        kk now={s[i],f};        //cout<<"test"<<endl;        if(p->m.find(now)!=p->m.end())            p=p->m[now];        else        {            node *makenode;            makenode = new node;            makenode->ini();            makenode->s=now.s;            p->m[now]=makenode;            p=makenode;        }    }}void print(node *p,int cnt){    for(int i=0;i<cnt;i++)        cout<<"    ";    cout<<p->s<<endl;}void dfs(node *p,int cnt)//用DFS输出结果{    if(p==NULL)        return ;    queue<node*> rec;    map<kk,node*> ::iterator it;    for(it=p->m.begin();it!=p->m.end();it++)    {        if(it->second->m.size())            print(it->second,cnt);        else            rec.push(it->second);//如果是书本,先推入队列,最后再输出        dfs(it->second,cnt+1);    }    while(!rec.empty())        print(rec.front(),cnt),rec.pop();}void Gs(string str,vector<string> &s)//字符串处理,分离出关键字并存入vector{    string te="";    for(int i=0;i<str.length();i++)    {        if(str[i]!=/)            te+=str[i];        else            s.push_back(te),te="";    }    s.push_back(te);}int main(){    cin.sync_with_stdio(false);    string str;    int cas=1;    head.ini();    vector<string> s;    while(getline(cin,str))    {        if(str=="0")        {            cout<<"Case "<<cas++<<":"<<endl;            dfs(&head,0);            s.clear();            head.ini();        }        else        {            Gs(str,s);            Ins(s);            s.clear();        }    }    return 0;}

 

ACM-ICPC Beijing Online A The Book List