程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 1385 - Billing Tables(字典樹)

uva 1385 - Billing Tables(字典樹)

編輯：C++入門知識

uva 1385 - Billing Tables(字典樹)

題目鏈接：uva 1385 - Billing Tables

題目大意：給定n個電話前綴，每個前綴是一個區域的前綴，現在要生成一個新的電話單，即對於每個電話號碼，從舊的電話單上從前向後遍歷，如果出現前綴匹配，則該電話號碼對應的即為當前的區號，要求生成的新電話單盡量小。

解題思路：用dfs建立字典樹，在區間范圍內的點對應均為對應的區號，注意如果70、71、72、...79都為SB的話，那麼可以合並成7，並且對應區號為SB。
注意合並的條件為區號相同即可，並不是說對應舊電話單匹配位置相同。
注意這組數據：0 - 9 all

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int sigma_size = 10;
typedef pair pii;

struct Node {
    int val;
    Node* next[sigma_size];

    Node() { 
        val = 0;
        memset(next, 0, sizeof(next));
    }
};

void clear(Node* &p);
void insert (Node* &p, int d, int L, int R, int tig);
void dfs(Node* p, string str);
int pushup(Node* &p, int tig);

map g;

int n, m;
string l, r, name[105];
Node* root = NULL;

vector vec;

void init () {
    vec.clear();
    g.clear();
    string tmp;

    for (int i = 1; i <= m; i++) {
        cin >> l >> tmp >> r >> name[i];

        tmp = "";
        int d = l.length() - r.length();

        for (int i = 0; i < d; i++)
            tmp += l[i];
        tmp += r;
        r = tmp;

        if (l > r)
            continue;

        int k = i;
        if (g.count(name[i]))
            k = g[name[i]];
        else
            g[name[i]] = i;

        insert(root, 0, 1, 1, k);
    }
}

int main () {
    int cas = 0;
    while (cin >> m) {
        if (cas++)
            cout << endl;

        init();
        pushup(root, m+1);
        dfs(root, "");
        clear(root);

        printf("%lu\n", vec.size());
        for (int i = 0; i < vec.size(); i++)
            cout << vec[i].first << " " << vec[i].second << endl;
    }
    return 0;
}

int pushup (Node* &p, int tig) {
    if (p == NULL) {
        p = new Node;
        return p->val = tig;
    }

    if (p->val)
        tig = p->val;

    int k = pushup(p->next[0], tig);
    for (int i = 1; i < sigma_size; i++) {
        if (k != pushup(p->next[i], tig))
            k = 0;
    }

    return p->val = k;
}

void dfs (Node* p, string str) {
    if (p != root && p->val) {
        if (p->val <= m && name[p->val] !=  "invalid")
            vec.push_back(make_pair(str, name[p->val]));
        return ;
    }

    for (int i = 0; i < sigma_size; i++) {
        if (p->next[i] != NULL) {
            char ch = '0' + i;
            dfs(p->next[i], str + ch);
        }
    }
}

void insert (Node* &p, int d, int L, int R, int tig) {
    if (p == NULL)
        p = new Node;

    if (p->val)
        tig = p->val;

    if (d >= l.length()) {
        p->val = tig;
        return;
    }

    if (L == 0 && R == 0) {
        p->val = tig;
        return;
    } else if (L == 0) {
        insert(p->next[r[d]-'0'], d + 1, 0, 1, tig);
        for (int i = 0; '0' + i < r[d]; i++)
            insert(p->next[i], d + 1, 0, 0, tig);
    } else if (R == 0) {
        insert(p->next[l[d]-'0'], d + 1, 1, 0, tig);
        for (int i = l[d] - '0' + 1; i < sigma_size; i++)
            insert(p->next[i], d + 1, 0, 0, tig);
    } else if (r[d] == l[d]) {
        insert(p->next[l[d]-'0'], d + 1, 1, 1, tig);
    } else {
        insert(p->next[l[d]-'0'], d + 1, 1, 0, tig);
        insert(p->next[r[d]-'0'], d + 1, 0, 1, tig);
        for (int i = l[d] + 1; i < r[d]; i++)
            insert(p->next[i-'0'], d + 1, 0, 0, tig);
    }
}

void clear(Node* &p) {
    for (int i = 0; i < sigma_size; i++) {
        if (p->next[i] != NULL)
            clear(p->next[i]);
    }
    delete p;
    p = NULL;
}