题目来源&＃xff1a;http://poj.org/problem?id&＃61;1056
http://poj.org/problem?id&＃61;3630
两题非常类似&＃xff0c;所以在这里一并做了。
1056题目大意&＃xff1a;
如果一组编码中不存在一个编码是另一个编码的前缀的情况&＃xff0c;我们就称这组编码是“可立即解码的”(immediately decodable)。我们假定编码都是二进制的&＃xff0c;一组编码中没有相同的码。每个编码长度都不超过10&＃xff0c;每组编码数目都在2到8之间。
比如&＃xff0c;一组二进制编码&＃xff1a;{A, B, C, D},其中&＃xff1a;A: 01 B: 10 C: 0010 D: 0000&＃xff0c;这组编码是immediately decodable的&＃xff1b;另一组编码&＃xff1a;A: 01 B: 10 C: 010 D:0000 则不是immediately decodable的&＃xff0c; 因为A是C的前缀。
写一个程序判断一组编码是不是immediately decodable的。
输入&＃xff1a;由一组0和1组成的二进制码组成&＃xff0c;以一个9表示一组编码的输入结束。
输出&＃xff1a;格式见sample。
Sample Input
01
10
0010
0000
9
01
10
010
0000
9
Sample Output
Set 1 is immediately decodable
Set 2 is not immediately decodable
本题数据类型简单&＃xff0c;数据规模小&＃xff0c;暴力其实就可以过。但是本题如果不用前缀树做就显得没有价值了。
Trie树&＃xff0c;又称前缀树或字典树。Trie一词本来源于retrieval&＃xff0c;发音[tri]&＃xff0c;但似乎更多人读为[trai]。看一下维基上的示意图应该很容易理解。
Trie树是一种用于快速检索的多叉树结构&＃xff0c;如上图所示的Trie树中&＃xff0c;用11个节点保存了8个字符串(to, tea, ted, ten, A, I, in, inn). 如果两个词具有相同前缀&＃xff0c;那么从根节点到两词对应的节点的路径在公共前缀部分是重合的。显然这种数据结构非常适合这道题的实现&＃xff0c;用一棵二叉trie树即可。每读入一个新的编码便插入树中&＃xff0c;如果插入过程中发现当前已存在某编码是该码的前缀或该码是已存在的某码的前缀&＃xff0c;侧该组编码不是immediately decodable的。
1 ////
2 // POJ1056 IMMEDIATE DECODABILITY
3 // Memory: 144K Time: 0MS
4 // Language: C&＃43;&＃43; Result : Accepted
5 ////
6
7 #include
8 #include
9 using namespace std;
10
11 struct Node {
12 int child[2];
13 int is_leaf;
14 };
15 Node tree[1000];
16 int tree_pointer &＃61; 1;
17 bool flag &＃61; true;;
18
19 bool insertNode (char * s, int index) {
20 if (tree[index].is_leaf &＃61;&＃61; 1) {
21 return false;
22 }
23 if (*s &＃61;&＃61; 0) {
24 if (tree[index].child[0] &＃61;&＃61; 0 && tree[index].child[1] &＃61;&＃61; 0) {
25 tree[index].is_leaf &＃61; 1;
26 return true;
27 } else {
28 return false;
29 }
30 }
31 while (*s) {
32 int d &＃61; *s - &＃39;0&＃39;;
33 if (tree[index].child[d] &＃61;&＃61; 0) {
34 tree[index].child[d] &＃61; tree_pointer&＃43;&＃43;;
35 }
36 return insertNode(s &＃43; 1, tree[index].child[d]);
37 }
38 }
39
40
41 int main(void) {
42 char buf[1000];
43 int case_no &＃61; 0;
44 tree[0].is_leaf &＃61; 0;
45 while (scanf("%s", buf) !&＃61; EOF) {
46 if (buf[0] &＃61;&＃61; &＃39;9&＃39;) {
47 if (flag &＃61;&＃61; true) {
48 printf("Set %d is immediately decodable\n", &＃43;&＃43;case_no);
49 } else {
50 printf("Set %d is not immediately decodable\n", &＃43;&＃43;case_no);
51 }
52 tree_pointer &＃61; 1;
53 memset(tree, 0, sizeof(tree));
54 flag &＃61; true;
55 continue;
56 }
57 if (flag) {
58 flag &＃61; insertNode(buf, 0);
59 }
60 }
61 }
然后看一下3630.
题目大意&＃xff1a;
给出一些电话号码&＃xff0c;判断是否存在一个号码是另一个号码前缀的情况, 如果不存在说明这些号码是consistent的。
输入&＃xff1a;多个case组成&＃xff0c;每个case第一行为号码数n, 接下来的n行每行为一个电话号码。
输出&＃xff1a;对于每个case&＃xff0c;若是consistent的输出YES, 否则输出NO。
Sample Input
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
Sample Output
NO
YES
两题几乎是一样的&＃xff0c;把上题里的二叉树改为十叉树即可。
1 //
2 // POJ3630 Phone List
3 // Memory: 2992K Time: 157MS
4 // Language: C&＃43;&＃43; Result: Accepted
5 //
6
7 #include
8 #include
9 using namespace std;
10
11 struct Node {
12 int child[10];
13 int flag; //0 非叶子节点&＃xff1b;1 未标记的叶子节点&＃xff1b;2 标记的叶子节点
14 };
15 Node tree[1 <<16];
16 int tree_pointer &＃61; 1;
17 bool flag &＃61; true;;
18
19 bool insertNode (char * s, int index) {
20 if (tree[index].flag &＃61;&＃61; 2) {
21 return false;
22 }
23 if (*s &＃61;&＃61; 0) {
24 if (tree[index].flag &＃61;&＃61; 1) {
25 tree[index].flag &＃61; 2;
26 return true;
27 } else {
28 return false;
29 }
30 }
31 while (*s) {
32 int d &＃61; *s - &＃39;0&＃39;;
33 if (tree[index].child[d] &＃61;&＃61; 0) {
34 tree[index].child[d] &＃61; tree_pointer&＃43;&＃43;;
35 tree[tree_pointer - 1].flag &＃61; 1;
36 }
37 tree[index].flag &＃61; 0;
38 return insertNode(s &＃43; 1, tree[index].child[d]);
39 }
40 }
41
42
43 int main(void) {
44 char buf[11];
45 int case_num;
46 scanf("%d", &case_num);
47 for (int case_no &＃61; 0; case_no
48 int n;
49 tree_pointer &＃61; 1;
50 memset(tree, 0, sizeof(tree));
51 flag &＃61; true;
52 scanf("%d", &n);
53 for (int num_id &＃61; 0; num_id
54 scanf("%s", buf);
55 if (flag) {
56 flag &＃61; insertNode(buf, 0);
57 }
58 }
59 if (flag &＃61;&＃61; true) {
60 printf("YES\n");
61 } else {
62 printf("NO\n");
63 }
64 }
65 }
京公网安备 11010802041100号