首页 > 代码库 > （字典树）HDU - 1671 Phone List
（字典树）HDU - 1671 Phone List
原题链接：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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。