A6681. 「雅礼集训 2017 Day4」编码
编程题
省选/NOI-
知识点
题目描述
**原题：NEERC 2016 B. Binary Code**
Bob 最新学习了一下二进制前缀编码的那一套理论。二进制编码是指一个由 $ n $ 个互不相同的二进制串 $ s_1, s_2, \ldots, s_n $ 构成的集合。而如果一套编码理论满足，对于任意的 $ i \neq j $，$ s_i $ 不是 $ s_j $ 的前缀，那么我们称它为前缀编码。
Bob 发现了一张上面写有 $ n $ 行二进制编码的纸，但这张纸年代久远，有些字迹已经模糊不清。幸运的是，每一行至多只会有一个模糊的字符。
Bob 想知道这 $ n $ 行二进制编码是否有可能是一个前缀编码？
Bob 最新学习了一下二进制前缀编码的那一套理论。二进制编码是指一个由 $ n $ 个互不相同的二进制串 $ s_1, s_2, \ldots, s_n $ 构成的集合。而如果一套编码理论满足，对于任意的 $ i \neq j $，$ s_i $ 不是 $ s_j $ 的前缀，那么我们称它为前缀编码。
Bob 发现了一张上面写有 $ n $ 行二进制编码的纸，但这张纸年代久远，有些字迹已经模糊不清。幸运的是，每一行至多只会有一个模糊的字符。
Bob 想知道这 $ n $ 行二进制编码是否有可能是一个前缀编码？
输入格式
第一行一个整数 $ n $，表示编码的大小。
接下来 $ n $ 行，每行一个由
接下来 $ n $ 行，每行一个由
0、1 及 ? 组成的字符串。保证每一行至多有一个 ?。输出格式
如果这 $ n $ 个二进制编码可能是前缀编码，输出
YES，否则输出 NO。输入输出样例
输入 #1
4 00? 0?00 ?1 1?0
输出 #1
YES
输入 #2
3 0100 01?0 01?0
输出 #2
NO
说明/提示
**本题采用捆绑测试。**
你需要通过一个子任务内的所有测试点才能得到该子任务的分数。
| 子任务 | 分值 | $ n $ | 字符串总长 |
|:--------:|:-----:|:-------:|:-------------:|
| 1 | 20 | $ \leq 10 $ | $ \leq 1000 $ |
| 2 | 30 | $ \leq 1000 $ | $ \leq 500000 $ |
| 3 | 50 | $ \leq 500000 $ | $ \leq 500000 $ |
你需要通过一个子任务内的所有测试点才能得到该子任务的分数。
| 子任务 | 分值 | $ n $ | 字符串总长 |
|:--------:|:-----:|:-------:|:-------------:|
| 1 | 20 | $ \leq 10 $ | $ \leq 1000 $ |
| 2 | 30 | $ \leq 1000 $ | $ \leq 500000 $ |
| 3 | 50 | $ \leq 500000 $ | $ \leq 500000 $ |