hihoCoder 1383 : The Book List 北京网络赛

http://hihocoder.com/problemset/problem/1383?sid=950389

#1383 : The Book List

时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

The history of Peking University Library is as long as the history of Peking University. It was build in 1898. At the end of year 2015, it had about 11,000 thousand volumes of books, among which 8,000 thousand volumes were paper books and the others were digital ones. Chairman Mao Zedong worked in Peking University Library for a few months as an assistant during 1918 to 1919. He earned 8 Dayang per month there, while the salary of top professors in Peking University is about 280 Dayang per month.

Now Han Meimei just takes the position which Chairman Mao used to be in Peking University Library. Her first job is to rearrange a list of books. Every entry in the list is in the format shown below:

CATEGORY 1/CATEGORY 2/..../CATEGORY n/BOOKNAME

It means that the book BOOKNAME belongs to CATEGORY n, and CATEGORY n belongs to CATEGORY n-1, and CATEGORY n-1 belongs to CATEGORY n-2...... Each book belongs to some categories. Let's call CATEGORY1 "first class category", and CATEGORY 2 "second class category", ...ect. This is an example:

MATH/GRAPH THEORY
ART/HISTORY/JAPANESE HISTORY/JAPANESE ACIENT HISTORY
ART/HISTORY/CHINESE HISTORY/THREE KINDOM/RESEARCHES ON LIUBEI
ART/HISTORY/CHINESE HISTORY/CHINESE MORDEN HISTORY
ART/HISTORY/CHINESE HISTORY/THREE KINDOM/RESEARCHES ON CAOCAO

Han Meimei needs to make a new list on which the relationship between books and the categories is shown by indents. The rules are:

1) The n-th class category has an indent of 4×(n-1) spaces before it.
2) The book directly belongs to the n-th class category has an indent of 4×n spaces before it.
3) The categories and books which directly belong to a category X should be list below X in dictionary order. But all categories go before all books.
4) All first class categories are also list by dictionary order.

For example, the book list above should be changed into the new list shown below:

ART
    HISTORY
        CHINESE HISTORY
            THREE KINDOM
                RESEARCHES ON CAOCAO
                RESEARCHES ON LIUBEI
            CHINESE MORDEN HISTORY
        JAPANESE HISTORY
            JAPANESE ACIENT HISTORY
MATH
    GRAPH THEORY

Please help Han Meimei to write a program to deal with her job.

输入

There are no more than 10 test cases.
Each case is a list of no more than 30 books, ending by a line of "0".
The description of a book contains only uppercase letters, digits, '/' and spaces, and it's no more than 100 characters.
Please note that, a same book may be listed more than once in the original list, but in the new list, each book only can be listed once. If two books have the same name but belong to different categories, they are different books.

这题主要是考察坑爹点。

首先是用字典树解决的了。

我的做法比较复杂，因为一开始的时候没想到用map来离散那些字符串。

所以我的就是，在字典树中开多了个数组来保存字符串，

struct node {
　　char has[30 + 2][100 + 2]; //用来保存同一级目录下是否的字符串
　　int use; 　　　　　　　　　 //判断有多少个字符串了
　　struct node * pNext[30 + 2]; //然后第i个字符串的下一个是谁，相当于离散化了。
} tree[10000 + 2];

坑爹

1：用"0"结束，那么你判断name[1] == '0'就GG了，因为有可能是0ABC这样的数据。

2：目录和文件名是不同的，A/B 和 A 其中的A是不同的，因为是不同含义，第二个是文件名

3：相同的只算一次。

4：四个空格和一个不等价

还有就是一个很坑爹的地方，

就是样例那里了，为什么不是按字典序输出，而且有些比较长的目录优先输出。

这样的话，又要判断了，优先输出有孩子的那个。

我的代码看不懂的了，可以用来找样例吧，我给几组数据。

A
A
A
A/A
A/A/A
A/A/A
A/A/A/A/A
A/A/A/A/A/A
A
A/A/A
A/A/A/A/A
AA/A
0

A/B/C

A/B

我这里要倒这排序这些字符串，因为要解决

A/B

先插入A/B

还有判断优先输出有儿子的，有就是有，不管有多少个。取值为1 or 0

dfs输出的时候，可以用cur表示再它前面已经输出了多少个，那么输出对应空格即可。

感觉我这个字典树用的还是比较6的，不过细节那么多，做了很久。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>

struct bookList {
    char name[100 + 20];
    bool operator < (const struct bookList & rhs) const {
        return strcmp(name + 1, rhs.name + 1) > 0;
    }
} book[300 + 2];
struct node {
    char has[30 + 2][100 + 2];
    int use;
    struct node * pNext[30 + 2];
} tree[10000 + 2];
struct TT {
    int id;
    int nextChild;
    bool operator < (const struct TT & rhs) const {
        if (nextChild != rhs.nextChild) return nextChild > rhs.nextChild;
        else return id > rhs.id;
    }
}FOR[1000 + 2][30 + 2];
int all;
int t;
struct node * create() {
    struct node * p = &tree[t++];
    p->use = 0;
    for (int i = 1; i <= 30; ++i) {
        memset(p->has[i], 0, sizeof p->has[i]);
        p->pNext[i] = NULL;
    }
    return p;
}
void insert(struct node **T, char str[], int lenstr) {
    struct node * p = *T;
    if (p == NULL) {
        *T = p = create();
    }
    str[lenstr + 1] = '/';
    char sub[222];
    int lensub = 0;
    for (int i = 1; i <= lenstr + 1; ++i) {
        if (str[i] == '/') {
            sub[lensub + 1] = '';
            bool flag = false;
            for (int j = 1; j <= p->use && i != lenstr + 1; ++j) {
                if (strcmp(sub + 1, p->has[j] + 1) == 0) {
                    p = p->pNext[j];
                    flag = true;
                    break;
                }
            }
            if (flag == false) {
                p->use++;
                strcpy(p->has[p->use] + 1, sub + 1);
                p->pNext[p->use] = create();
                p = p->pNext[p->use];
            }
            lensub = 0;
        } else sub[++lensub] = str[i];
    }
}
int liu;
char str1[111], str2[111];
void dfs(struct node *T, int cur, struct TT tosort[]) {
    if (T == NULL) return;
    struct node *p = T;
    for (int i = 1; i <= p->use; ++i) {
        tosort[i].id = i;
        tosort[i].nextChild = p->pNext[i]->use > 0;
    }
    sort(tosort + 1, tosort + 1 + p->use);
    for (int i = 1; i <= p->use; ++i) {
        for (int j = 1; j <= cur; ++j) {
            for (int k = 1; k <= 4; ++k) printf(" ");
        }
        printf("%s
", p->has[tosort[i].id] + 1);
        dfs(p->pNext[tosort[i].id], cur + 1, FOR[++liu]);
    }
}
int f = 0;
void work() {
    while (gets(book[++all].name + 1) != NULL && strcmp(book[all].name + 1, "0") != 0) ;
    all--;
    sort(book + 1, book + 1 + all);
//    for (int i = 1; i <= all; ++i) {
//        printf("%s
", book[i].name + 1);
//    }
//    printf("
");
    struct node *T = NULL;
    memset(str1, 0, sizeof str1);
    memset(str2, 0, sizeof str2);
    strcpy(str2 + 1, book[1].name + 1);
    for (int i = 1; i <= all; ++i) {
//        printf("%s %s
", str1 + 1, str2 + 1);
        if (strcmp(str1 + 1, str2 + 1) == 0) {
            strcpy(str1 + 1, str2 + 1);
            strcpy(str2 + 1, book[i + 1].name + 1);
            continue;
        }
        strcpy(str1 + 1, str2 + 1);
        strcpy(str2 + 1, book[i + 1].name + 1);
        insert(&T, book[i].name, strlen(book[i].name + 1));
    }
    printf("Case %d:
", ++f);
    liu = -1;
    dfs(T, 0, FOR[++liu]);
}
int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    while (gets(book[++all].name +1) != NULL && strcmp(book[all].name + 1, "0") != 0) {
        work();
//        printf("
");
        all = 0;
        t = 0;
//        memset(tree, 0, sizeof tree);
//        memset(FOR, 0, sizeof FOR);
//        memset(book, 0, sizeof book);
    }
    return 0;
}

View Code