hihoCoder #1383 : The Book List 【2016北京网赛】模拟

#1383

吐槽一下北京网赛，感觉又是跟去年一样的风格

两个模拟，手速快的可以进，然而弱wa了全场

赛后补题补了这个，觉得学到了很多字符串模拟和STL的姿势

先说说题意：把用/分开的目录按照缩进的方式排列好

优先级的定义为：有目录的优先把目录放前面（有目录的时候，也是按照字典序的优先级），如果没有目录，按照字典序的优先级

然后呢，这个题可以当作linux的树状结构来说

虚拟建立一个根节点：作为一开始的树根root节点来做，避免讨论起点到底先输出哪个

剩下的细节，先贴代码再来分析吧

#include<bits/stdc++.h>
using namespace std;

#define LL long long

const int maxn=1e3+50;
char s[maxn];

struct DIR{
    string name;
    vector<DIR*> son;
    bool ismulu;
    DIR(string s,bool is=false){
        name=s;
        ismulu=is;
    }
    void init(){
        son.clear();
    }
};

DIR *root=new DIR("root");

bool cmpX(DIR *a,DIR *b){
    if (a->ismulu==b->ismulu)
        return a->name<b->name;
    return a->ismulu>b->ismulu;
}

void out(DIR *p,int len){
    for(int i=0;i<len;i++) printf("    ");
    printf("%s\n",p->name.c_str());
    sort(p->son.begin(),p->son.end(),cmpX);
    for(int i=0,SZ=p->son.size();i<SZ;i++)
        out(p->son[i],len+1);
}

void outAns(int T){
    printf("Case %d:\n",T);
    DIR *p=root;
    sort(p->son.begin(),p->son.end(),cmpX);
    for(int i=0,SZ=p->son.size();i<SZ;i++)
        out(p->son[i],0);
    root->init();
}

void solve(){
    char *p=s;
    int ln=0;
    char dirname[maxn];
    DIR *dr=root;
    while(1){
        if (*p==0) break;
        sscanf(p,"%[^/]%n",dirname,&ln);
        p+=ln;
        bool ml=0;
        if (*p=='/') ml=1;
        int t=-1;
        for(int i=0,SZ=dr->son.size();i<SZ;i++)
            if (strcmp(dr->son[i]->name.c_str(),dirname)==0&&ml==dr->son[i]->ismulu)
                t=i;
        if (t==-1)
            dr->son.push_back(new DIR(dirname,ml)),dr=(dr->son.back());
        else
            dr=dr->son[t];
        ++p;
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    int T=0;
    memset(s,0,sizeof(s));
    while(gets(s)){
        if (strcmp(s,"0")==0)
            outAns(++T);
        else
            solve();
        memset(s,0,sizeof(s));
    }
    return 0;
}

首先说根节点root：为了避免一开始的讨论，自己定义一个根节点

再来说说solve函数：

对两个函数进行知识补充：

sscanf：sscanf高级用法

你会发现，【^/】就是从第一个有意义的目录或者书名开始，读到非/或者读到字符的末尾

ln返回的是dirname有多长

那么如果判断是/还是末尾返回的呢？很简单：判断一下是不是/就好了，用个bool数组记录：同时可以标记当前的字符串是目录，还是书名

再来分析t这个值

很明显就是判断当前的目录或者书名是不是在当前的树中出现过

如果是目录，而且出现过，那么可以走进去；否则呢，就要重新建点，然后再进去

vector：vector高级用法

看到这个里面的back（）函数，因为vector的插入是讲顺序的