首页 > 代码库 > （字典树）HDU - 1671 Phone List

（字典树）HDU - 1671 Phone List

2024-08-13 10:12:16   214人阅读

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1671

题意：给很多电话号码，如果在拨号的时候，拨到一个存在的号码，就会直接打出去，以致以这个号码为前缀的所有其他比这个号码长的号码将不能拨出，问是不是所有的号码都能拨。

分析：可以直接建立字典树，节点中用boolean变量表示当前是否组成电话号码，一旦在遍历完某条号码之前，已经出现存在号码，则发现问题，返回false，否则true。

我使用了一个反过来的方法，即只统计前缀出现次数，遍历完某条号码，如果在当前节点前缀出现的次数cnt>1，则说明还有比这个它更长的号码。

理论上，这两种方法都是可行的，下面贴出第二种方法。

代码：

  1 #include <set>  2 #include <map>  3 #include <list>  4 #include <cmath>  5 #include <queue>  6 #include <vector>  7 #include <bitset>  8 #include <string>  9 #include <cctype> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <iostream> 14 #include <algorithm> 15  16 using namespace std; 17  18 typedef long long ll; 19 typedef unsigned long long ull; 20 #define inf (0x3f3f3f3f) 21 #define lnf (0x3f3f3f3f3f3f3f3f) 22 #define eps (1e-8) 23 int sgn(double a){return a < -eps ? -1 : a < eps ? 0 : 1;} 24  25 //-------------------------- 26  27  28 struct  Trie_node { 29     int cnt; 30     int next[26]; 31 }tree[400010]; 32 int nxt; 33  34 int  createTrieNode() { 35     memset(&tree[nxt], 0, sizeof(Trie_node)); 36     return nxt++; 37 } 38  39 void Trie_insert(char* word) { 40     int rt=0; 41     int len=strlen(word); 42     for(int i=0;i<len;i++){ 43         int id = word[i] - ‘0‘; 44         if(!tree[rt].next[id]){ 45             tree[rt].next[id]=createTrieNode(); 46         } 47         rt=tree[rt].next[id]; 48         tree[rt].cnt++; 49     } 50 } 51  52 int Trie_search(char* word) { 53     int rt=0; 54     int len=strlen(word); 55     for(int i=0;i<len;i++){ 56         int id=word[i]-‘0‘; 57         if(!tree[rt].next[id])return 0; 58         rt=tree[rt].next[id]; 59     } 60     return tree[rt].cnt; 61 } 62  63 void init(){ 64     nxt=1; 65     memset(&tree[0],0,sizeof(Trie_node)); 66 } 67  68 char word[10010][11]; 69  70 void solve() { 71     int t; 72     scanf("%d",&t); 73     while(t--){ 74         int n; 75         scanf("%d",&n); 76         init(); 77         for(int i=0;i<n;i++){ 78             scanf("%s",word[i]); 79             Trie_insert(word[i]); 80         } 81         bool flag=1; 82         for(int i=0;i<n;i++){ 83             if(Trie_search(word[i])>1){ 84                 flag=0; 85                 break; 86             } 87         } 88         if(flag)puts("YES"); 89         else puts("NO"); 90     } 91 } 92  93  94  95  96 int main() { 97  98 #ifndef ONLINE_JUDGE 99     freopen("in.txt", "r", stdin);100     //freopen("out.txt", "w", stdout);101 #endif102     //iostream::sync_with_stdio(false);103     solve();104     return 0;105 }

 

（字典树）HDU - 1671 Phone List


联系
我们