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的插入是讲顺序的

我们插入的son的值,是vector中的最后一个节点,所以要走到back()函数,进入这个新建立的节点


排序函数:

根据DIR的定义:

如果在同一棵树之中,两个节点都是目录或者都是书名,那么按照字典序排序

否则,目录优先,书名排后面

is这个bool值,代表当前的字符串是不是目录


总之呢

这个题的姿势很多,很奇怪,但是考到了很多STL的姿势好吧


全部评论

相关推荐

点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务