#P11720. [清华集训 2014] 虫逢
[清华集训 2014] 虫逢
题目描述
小强和阿米巴是好朋友。
阿米巴告诉小强,变形虫(又叫阿米巴虫)和绝大多数生物一样,也是有 DNA 的。并且,变形虫可以通过分裂的方式进行无性繁殖。
我们把一个变形虫的基因组抽象成一个大小为 的基因集合。每个基因都是一个 位长的字符串(字符包括大小写字母、数字、符号 ~!@#%^&()[]`:;"'<>,.?/|=-{}})。现在,有 个变形虫凑到了一起。由于他们是从天南海北过来的,我们可以认为,他们的基因组都是从一个大小为 的“变形虫基因库“中独立的随机的选取 个基因得到的。目前人类并不了解这个基因库里都有什么基因,但是我们知道它的大小是 。
这时,环境突然发生巨变。这 个变形虫在外界的刺激下同时进行了一次分裂。每个变形虫分裂成了两个。分裂的过程中,原来的变形虫的基因组(基因的集合)被原样的复制成了两份,分别进入两个新的变形虫。两个新变形虫中的一只的基因组中有一半发生了突变,被替换为“变形虫基因库”中随机的其他的基因。如果两个变形虫是由原来的一个变形虫产生的,我们叫它们“同源”的。
给出 个变形虫的基因组,请你找出每个变形虫同源的另一只虫是谁。
输入格式
第一行三个整数 、、。
接下来一行 个字符,依次表示每个集合中的元素。集合内的元素之间的顺序是无关紧要的。
输出格式
输出 行,每行一个整数表示第 个变形虫(从 开始标号)同源的另一只变形虫是谁。
2 100 6
H[P,86(^,<n&7X_Sg"LY67m2H$n+5'!VHp5IA.@GM:4-NJsqsiG!H[P,7X_S86(^>aNQ22'B5'!V<FD!F!6xNJsq>!]dHp5I
3
4
1
2
提示
样例解释
输入文件一共有两行。四个基因组分别是:
H[P,
,86(^
,,<n&
,7X_S
,g"LY
,67m2
H$n+
,5'!V
,Hp5I
,A.@G
,M:4-
,NJsq
siG!
,H[P,
,7X_S
,86(^
,>aNQ
,22'B
5'!V
,<FD!
,F!6x
,NJsq
,>!]d
,Hp5I
明显, 是同源的, 是同源的。
数据范围
一共有 个测试点。数据均为按照题目中描述的方法随机生成的。对于非同源的两个变形虫,他们的基因组的交的大小均小于 。对于同源的两个变形虫,他们的基因组的交的大小刚好是 。
测试点编号 | |||
---|---|---|---|
最大的一个测试数据的大小是 左右()。在测评系统上,由于磁盘缓存的存在,使用 scanf 将数据读入需要的时间小于 秒。请不要使用 cin。经测试:
- 一个实现良好的 时间复杂度的算法能拿 30 分,
- 一个实现良好的 时间复杂度的算法能拿 50 分。