UVALive – 3703 Billing Tables Tire、字典树

Billing Tables Tire、字典树

 Source

UVALive - 3703,
UVA - 1385,
POJ - 3149

NEERC 2006

My Solution

题意：对于11位数字串(电话号码)，按优先级给定n个区间，每个区间有一个标记。若一个电话号码在某个区间内(如有多个则取优先级最高的区间)，则电话号码具有该区间的标记。求一个最小前缀与标记的对应表，使若一个号码的前面与某个前缀匹配，则该号码一定具有该前缀的标记，且不能再与其它前缀匹配。

Tire、字典树

把区间按照从上到下的顺序插入到Tire中，每个根到叶子节点的路径就是一个符合要求的前缀。每个节点都表示一个电话号码

前缀，若某一个节点被一个区间完全覆盖或者几个具有相同标记的区间完全覆盖，则可作为一个叶子节点，否则继续拓展。

每次拓展的时候，把原标记往下推，然后刷新当前节点的标记。

节点个数大于11*2*n，但不会特别大。

复杂度 略大于节点总数sum，O(T*sum)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e2 + 8;
const int MAX_SIZE = 12;
const int CHAR_SIZE = 10;
//Tire
int ch[100008][CHAR_SIZE], danger[100008], tot;
inline void _insert(char *s1, char *s2, int mark)
{
    int u1 = 0, u2 = 0, i, j, len = strlen(s1);
    for(i = 0; i < len; i++){
        for(j = 0; j < CHAR_SIZE; j++){ if(ch[u1][j] == 0) ch[u1][j] = ++tot; if(ch[u2][j] == 0) ch[u2][j] = ++tot; if(danger[u1] > 0) danger[ch[u1][j]] = danger[u1];
            if(danger[u2] > 0) danger[ch[u2][j]] = danger[u2];
        }
        danger[u1] = danger[u2] = 0;
        if(u1 == u2){
            //cout << s1[i] << " " << s2[i] << endl;
            for(j = s1[i] - '0' + 1; j < s2[i] - '0'; j++){
                danger[ch[u1][j]] = mark;
            }
        }
        else{
            for(j = s1[i] - '0' + 1; j < CHAR_SIZE; j++){
                danger[ch[u1][j]] = mark;
            }
            for(j = 0; j < s2[i] - '0'; j++){ danger[ch[u2][j]] = mark; } } u1 = ch[u1][s1[i]-'0']; u2 = ch[u2][s2[i]-'0']; } danger[u1] = danger[u2] = mark; } char str1[MAXN][MAX_SIZE], str2[MAXN][MAX_SIZE], plan[MAXN][2*MAX_SIZE]; int toplan[MAXN], ans; bool valid[MAXN]; void dfs1(int u) { if(danger[u] > 0){
        ans += valid
];
        return;
    }
    if(ch[u][0] == 0) return;
    bool f = true;
    for(int i = 0; i < CHAR_SIZE; i++){ dfs1(ch[u][i]); if(danger[ch[u][i]] != danger[ch[u][0]]) f = false; } if(f && valid
[0]]] && u){//! ans -= 9; danger[u] = danger[ch[u][0]]; } } char s[MAX_SIZE]; void dfs2(int u, int len) { if(danger[u] > 0){
        if(valid
]){
            for(int i = 0; i < len; i++){
                putchar(s[i]);
            }
            putchar(' ');
            printf("%sn", plan
]);
        }
        return;
    }
    if(ch[u][0] == 0) return;
    for(int i = 0; i < CHAR_SIZE; i++){
        s[len] = '0' + i;
        dfs2(ch[u][i], len + 1);
    }
}

int main()
{
    #ifdef LOCAL
    freopen("19.in", "r", stdin);
    //freopen("19.out", "w", stdout);

    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int T, n, i, j, len1, len2;
    bool f = true;
    while(scanf("%d", &n) != EOF){
        if(!f) putchar('n');
        else f = false;
        memset(ch, 0, sizeof ch);
        memset(valid, false, sizeof valid);
        memset(danger, 0, sizeof danger);
        ans = tot = 0;
        for(i = 1; i <= n; i++){ scanf("%s%*s%s%s", str1[i], str2[i], plan[i]); len1 = strlen(str1[i]); len2 = strlen(str2[i]); for(j = len2 - 1; j >= 0; j--) str2[i][len1-len2+j] = str2[i][j];
            for(j = 0; j < len1 - len2; j++) str2[i][j] = str1[i][j];
            if(strcmp(plan[i], "invalid") != 0) valid[i] = true;
            toplan[i] = i;
            for(j = 1; j < i; j++){ if(strcmp(plan[j], plan[i]) == 0){ toplan[i] = j; break; } } } for(i = n; i >= 1; i--){
            //printf("%s   %sn", str1[i], str2[i]);
            _insert(str1[i], str2[i], toplan[i]);
        }

        dfs1(0);
        printf("%dn", ans);
        dfs2(0, 0);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx