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