Consistency Checker LightOJ - 1129

题目链接

LightOJ-1129

题解

字典树的简单应用。
见AC代码注释。

WA

没有使用字典树。建立了sets数组记录字符串中字母是否出现，对每一个字符串，遍历其所有的字符并在sets中将该字符位置设置为true。
由于在这之前对所有的字符串按长度进行了排序，故只需要判断第一个字符串之外的所有字符串的字符位置是否全部为true即可。

问题所在：

3
911
912
111

对于这一组样例将返回错误的结果。

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int const LEN = 10001;
bool sets[LEN][10];

bool cmp(const string &a, const string &b) {
    if (a.length() == b.length()) return a < b;
    return a.length() > b.length();
}

int main() {
    int _;
    cin >> _;
    for (int t = 1; t <= _; t++) {
        memset(sets, false, sizeof(sets));
        int n;
        cin >> n;
        vector<string> v(n);
        for (int i = 0; i < n; i++) { cin >> v[i]; }
        sort(v.begin(), v.end(), cmp);
        bool YES = true;
        for (int i = 0; i < n; i++) {
            bool flag = false;
            for (int j = 0; j < v[i].size(); j++) {
                if (!sets[j][v[i][j] - '0']) flag = true;
                sets[j][v[i][j] - '0'] = true; // ERROR!
            }
            if (!flag) {
                YES = false;
                break;
            }
        }
        cout << "Case " << t << ": ";
        if (YES) cout << "YES\n";
        else cout << "NO\n";
    }
}

MLE

使用了动态建立字典树的方法，建立过程中有想到在之后的处理中直接设置为nullptr将导致过多垃圾内存堆积的问题，但是没有处理。果然炸了。

#include <iostream>
#include <cstring>

using namespace std;

struct Node {
    int flag;
    bool son;
    Node *nxt[10];

    Node() {
        for (int i = 0; i < 10; i++) nxt[i] = nullptr;
        flag = 0;
        son = false;
    }
};

Node *root;

void init() {
    root = new Node();
}

void insert(char *s) {
    Node *now = root;
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        int idx = s[i] - '0';
        if (now->nxt[idx] == nullptr) now->nxt[idx] = new Node();
        now->son = true;
        now = now->nxt[idx];
    }

    now->flag += 1;
}

int find(char *s) {
    Node *now = root;
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        int idx = s[i] - '0';
        if (now->nxt[idx] == nullptr) return 0;
        now = now->nxt[idx];
    }

    return now->son;
}

char str[10010][20];

int main() {
    int _;
    scanf("%d", &_);
    for (int cas = 1; cas <= _; cas++) {
        init();
        int N;
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%s", str[i]);
            insert(str[i]);
        }
        printf("Case %d: ", cas);
        bool flag = true;
        for (int i = 0; i < N; i++) {
            if (find(str[i])) {
                flag = false;
                break;
            }
        }
        if (flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

AC

使用了字典树，在代码末尾添加了clear函数处理内存。

#include <iostream>
#include <cstring>

using namespace std;

// 字典树节点
struct Node {
    int flag; // 记录以当前节点结尾的字符串的数量。在该题目中由于每个字符串都是唯一，故可以改为bool类型。
    bool son; // 针对该题，son用于判断该节点是否有子节点。如果该节点有子节点那么说明当前以当前节点结尾的字符串作为了另一个字符串的前缀。唔，当时并没有考虑重复字符串的问题，读题可以发现每个字符串都是唯一的。
    Node *nxt[10]; // 子节点，大小根据题目而定。在本题中由于只有十个字符，故设置为10.

    Node() { // 初始化
        for (int i = 0; i < 10; i++) {
            nxt[i] = nullptr;
        }
        flag = 0;
        son = false;
    }
};

Node *root; // 根节点

void init() {
    root = new Node();
}

void insert(char *s) {
    Node *now = root;
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        // hash函数，一一映射
        int idx = s[i] - '0';
        // 若当前字符节点不存在，则建立新节点
        if (now->nxt[idx] == nullptr) now->nxt[idx] = new Node();
        // 标志当前节点存在子节点
        now->son = true;
        // now指针后移
        now = now->nxt[idx];
    }
	// 当前字符结尾的字符串“喜加一”
    now->flag += 1;
}

// 查找函数，根据题意进行了部分变动
int find(char *s) { 
    Node *now = root;
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        int idx = s[i] - '0';
        // 若当前字符不存在，则说明查找失败，在本题中，该代码的做法不会出现这种情况，因为在查找之前将所有的字符都进行了插入。
        if (now->nxt[idx] == nullptr) return 0;
        now = now->nxt[idx];
    }
    // 在一般的字典树中此处应该返回now节点的flag成员以表明有多少该字符串，此处改为son表明该字符串是否为其他字符串的前缀。
    return now->son;
}

void clear(Node *tmp) {
    for (int i = 0; i < 10; i++) {
        if (tmp->nxt[i] != nullptr) clear(tmp->nxt[i]);
    }
    delete tmp;
}

char str[10010][20];

int main() {
    int _;
    scanf("%d", &_);
    for (int cas = 1; cas <= _; cas++) {
        init();
        int N;
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%s", str[i]);
            insert(str[i]);
        }
        printf("Case %d: ", cas);
        bool flag = true;
        for (int i = 0; i < N; i++) {
            if (find(str[i])) {
                flag = false;
                break;
            }
        }
        if (flag) puts("YES");
        else puts("NO");
        clear(root);
    }
    return 0;
}