ICPC2019上海区域赛 B-Prefix-Code题解

迈不过友情╰ 2022-12-28 11:17 116阅读 0赞

### 文章目录 ###

*  题目描述（翻译版）
 *   *  输入描述
     *  输出描述
     *  输入
     *  输出
 *  算法分析
 *  代码分析
 *  解题代码
 *  错题分析

--------------------

链接：https://ac.nowcoder.com/acm/contest/4370/B  
来源：牛客网

# 题目描述（翻译版） #

前缀代码是一种通过拥有“前缀属性” 来区分的代码系统，它要求系统中没有完整的代码字，而不是系统中任何其他代码字的前缀（初始段）。

对于定长代码，这确实很简单，因此，在变长代码中，只有一点要考虑，例如，带有代码字的代码 `{9，55}` 具有prefix属性；由以下代码组成的代码 `{9，5，59，55}` 并非如此，因为`“5”`是`“59”`的前缀，也是`“55”`的前缀。前缀代码是唯一可解码的代码：给定完整而准确的序列，接收方可以识别每个单词而无需在单词之间需要特殊的标记，但是，存在不是前缀代码的可唯一编码的代码；例如，前缀代码的反向仍然是唯一可解码的（它是后缀代码），但不一定是前缀代码。  
前缀代码也称为无前缀代码，前缀条件代码和瞬时代码。尽管霍夫曼编码只是众多导出前缀代码的算法之一，但前缀代码也被广泛称为“霍夫曼代码’’，即使该代码不是由霍夫曼算法生成的。无逗号代码一词有时也用作无前缀代码的同义词，但在大多数数学书籍和文章中，无逗号代码用于表示自同步代码，即前缀代码的子类。  
使用前缀代码，可以将消息作为一系列连接的代码字进行传输，而无需在单词之间使用任何带外标记或（或者）特殊标记来构筑消息中的单词。接收者可以通过重复查找和删除形成有效代码字的序列来明确解码消息。例如，对于缺少前缀属性的代码，这通常是不可能的 `{0，1，10，11}` ：接收机在代码字的开头读取“1”将不知道它是完整的代码字`“1”`，还是仅是代码字`“10”`或`“11”`的前缀’; 因此，字符串`“10”`可以解释为单个代码字，也可以解释为单词`“ 1”` 然后是`“0”`的串联。  
变长霍夫曼代码，国家/地区代码，ISBN的国家/地区和发布者部分， UMTS W-CDMA 3G无线标准中使用的辅助同步代码，  
前缀代码不是纠错代码。在实践中，消息可能先用前缀码压缩，然后再在传输之前用信道编码（包括纠错）再次编码。  
对于任何唯一可解码的代码，都有一个具有相同代码字长的前缀代码。卡夫（Kraft）的不等式表征了唯一可解码代码中可能存在的代码字长集。

在这个问题上，你可以给一个代码 `N` 个代码字。每个单词只包含数字 `{0，1，2，3，4，5，6，7，8，9}` 。您需要检查代码是否可以满足prefix属性：系统中没有完整的代码字，没有其他任何代码字的前缀。

## 输入描述 ##

> 输入的第一行给出了测试用例的数量， **Ť（1 ≤ Ť ≤ 100 ）**。随后是 **T** 个测试用例。
> 
> 每个测试用例由一行和一个整数组成 **N（1≤ N ≤ 10,000）**，代码字的数量。  
> 然后跟随 **N** 行，每行一个代码字。一个代码字是一个
> 
> 最多十位数的序列。

## 输出描述 ##

> 对于每个测试用例，输出一行包含\*\*“ Case \#x：y”\*\*的行，其中x是测试用例编号（从1开始），如果代码是前缀代码，则是“ Yes”，否则为“ No”。

## 输入 ##

3
    2
    9
    55
    4
    9
    5
    59
    55
    4
    01
    01
    123
    321

## 输出 ##

Case #1: Yes
    Case #2: No
    Case #3: No

# 算法分析 #

本题用Trie树的思想，类似于哈夫曼编码的那棵树（因为对于哈夫曼编码而言，每个编码都是一个前缀编码），只要一个串的终点不是叶子结点，就说明这个树就不是一个Trie树。

> **换而言之，只要一个串的终点被多次遍历（利用），就说明不是一个Trie树**

如图（对于样例2的数据）：

![1][]

图中，深度为1 的 5 节点 是第二个串 `5` 的终点，同时也是串 `55` 和 `59` 的组成部分，所以这个例子不是Prefix Tree。

# 代码分析 #

用 `T[maxn][12]` 数组记录树，

用 `num[maxn]` 数组记录第 `i` 个节点被遍历（利用）的次数

用 `isend[maxn]` 数组记录第 `i` 个节点是不是该串的终点

用 `tot` 标记当前为第几个节点

# 解题代码 #

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+5;
    
    int T[maxn][12]; //数组构成的树
    
    int num[maxn];  //记录这个节点被经过了几次
    
    int isend[maxn];    //这个节点是不是终点
    
    int tot = 1; //记录节点数
    
    void add(char *s){
        
        int l=strlen(s+1);
        
        int rt=1;   //第几个节点，还作为这个节点的下一个层的层数
        
        for(int i = 1; i <= l; i++){
        
            if(T[rt][s[i]-'0'] == 0){
        	
    						//如果在rt这一层，没有该节点，就在这层启用这个节点
              	//并且该节点的下一层为该节点的节点编号tot
    						T[rt][s[i]-'0'] = ++tot;
                rt = tot;
            }
            else{
        
    	          //如果在rt这层，存在此节点
              	//就在寻找此节点所指向的下一层
                rt = T[rt][s[i]-'0'];
            }
            num[rt]++;	//每向下找一层，该层的这个节点使用次数加1
        }
        isend[rt]=1;	//标记最后一个节点为 终点
    }
    
    void init(){
        
        for(int i = 0; i <= tot; i++){
        
            memset(T[i], 0, sizeof(T[i]));
            num[i] = isend[i] = 0;
        }
        tot=1;
    }
    
    char s[15];
    
    int main(){
        
        int T;
        cin>>T;
        
        for(int kase=1;kase<=T;kase++){
        
            init();
            
            int n;
            scanf("%d",&n);
            
            for(int i=1;i<=n;i++){
        
                scanf("%s",s+1);
                add(s);
            }
            
            int flag=1;
            for(int i=1;i<=tot;i++){
        
    	          //只要一个节点是终点，并且该节点被遍历（利用）的次数 大于 1
              	//就说明这个样例不是一个Trie树
                if(isend[i] && num[i]>1){
        	
                    flag=0;
                    break;
                }
            }
            
            if(flag)
                printf("Case #%d: Yes\n",kase);
            else
                printf("Case #%d: No\n",kase);
        }
    }

--------------------

# 错题分析 #

关于Trie树的概念（类似于哈夫曼编码的形成原因）：  
http://www.sohu.com/a/300621285\_115128

[1]: /images/20221120/82dcf6c4017646c791ced5ba30ae39f6.png