题目名称	20. [HAOI 2005]破译密文
输入输出	`encrypt.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	7
题目来源	cqw 于2008-04-07加入
开放分组	全部用户
提交状态
分类标签	并查集 HAOI
查看题解	分享题解

通过：147，提交：464，通过率：31.68%
.Xmz	100	0.000 s	0.00 MiB	C++
CAX_CPG	100	0.000 s	0.00 MiB	Pascal
YGOI_真神名曰驴蛋蛋	100	0.000 s	0.00 MiB	C++
沉迷学习的假的Keller	100	0.000 s	0.00 MiB	C++
面对疾风吧疾风疾风吧	100	0.000 s	0.00 MiB	C++
神威难藏于泪	100	0.000 s	0.00 MiB	C++
ceerRep	100	0.000 s	0.00 MiB	C++
Youngsc	100	0.000 s	0.00 MiB	C++
hyy	100	0.000 s	0.00 MiB	C++
铑小子	100	0.000 s	0.00 MiB	C++

本题关联比赛
4043级NOIP2022欢乐赛4th

关于破译密文的近10条评论(全部评论)
Bennettz 2018-06-01 11:17 21楼
回复 @安呐一条小咸��。 : 把并查集father全初始化为自己就行了 iortheir 2017-02-22 11:35 20楼
如果矛盾，输出0 面对疾风吧疾风疾风吧 2016-10-16 17:43 19楼
类似于229.单词等式 liu_runda 2016-03-30 12:20 18楼
`void _=freopen("encrypt.in","r",stdin); void __=freopen("encrypt.out","w",stdout); int a=arcv.doing(); int main(){;}` 有人知道这东西的威力吗 YGOI_真神名曰驴蛋蛋 2016-03-13 00:16 17楼
回复 @ ‘ : 233 洛克索耶夫 2016-03-12 11:02 16楼
提交30多次，这道题彻底明白，代码讲解各一半- - 求好评安呐一条小咸鱼。 2016-03-12 10:40 15楼
莫怪我打表 Sky_miner 2016-03-10 11:17 14楼
并查集。。。集合的元素是“原文中某个位置的字符”，合并操作对应于“原文中这两个位置的字符是相同的”。最后考虑有多少个不能确定是0还是1的不相交字符集合即可。 liu_runda 2016-03-09 10:46 13楼
并查集，关键是字符与数的转化 forever 2015-10-25 14:31 12楼

20. [HAOI 2005]破译密文

★★☆ 输入文件：encrypt.in 输出文件：encrypt.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

信息的明文是由 $0$ 和 $1$ 组成的非空序列。但在网络通信中，为了信息的安全性，常对明文进行加密，用密文进行传输。密文是由 $0$、$1$ 和若干个密码字母组成，每个密码字母代表不同的 $01$ 串。例如，密文= $011a0bf00a01$。密码破译的关键是确定每个密码的含义。

经过长期统计分析，现在知道了每个密码的固定长度，如今，我方又截获了敌方的两段密文 $S_1$ 和 $S_2$，并且知道 $S_1$ 和 $S_2$ 代表相同的明文。你的任务是帮助情报人员对给定的两段密文进行分析，看一看有多少种可能的明文。

【输入文件】

第 $1$ 行： $S_1$ (第 $1$ 段密文)

第 $2$ 行： $S_2$ (第 $2$ 段密文)

第 $3$ 行： $N$ (密码总数)

第 $4 \sim N+3$ 行：字母$c$ 长度$l$ (密码 $i$ 用小写英文字母 $c$ 表示，长度为 $l$。)

【输出文件】

M（表示有 $M$ 种可能的明文，如果两个密文出现矛盾情况，则输出 $0$。）

【输入样例1】

100ad1
cc1
4
a 2
d 3
c 4
b 50

【输出样例1】

【输入样例2】

a1b0c1
bdad
4
a 5
b 4
d 2
c 1

【输出样例2】

【输入样例3】

abc
abc
3
a 1
b 2
c 3

【输出样例3】

【数据范围】

对于 $40\%$ 的数据，密文长度$ \leq 20, 1 \leq N \leq 10, 1 \leq l \leq 100$;

对于 $100\%$ 的数据，密文长度$ \leq 10000, 1 \leq N \leq 26, 1 \leq l \leq 100$;