uva 1385 - Billing Tables(字典树) - c++编程基础

TOP

uva 1385 - Billing Tables(字典树)

2015-07-20 17:45:12 来源: 作者: 【大中小】浏览:2次

题目链接：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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVA 10746 Crime Wave ? The Sequ..	下一篇：poj 3693 Maximum repetition sub..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: