d480. 基因的核
標籤 :
通過比率 : 8人/21人 ( 38% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-02-17 23:25

內容

这题的测资可能有问题!
假如您正在或想做此题,得到AC就恭喜,得到WA也不要丧气,假如有什么问题欢迎提出。
欢迎提供解法,欢迎提供测资。

OI地外生化研究中心遇到了一个巨大的机遇&&挑战------xxxxx年x月x日,一架来自地外文明的载人飞船企图在戈壁登陆地球,对于研究地外文明和外星生物,这是一个千古难得的机遇,然而中国国防部也检测到了这不明飞行物,(在不明情况的前提下)国防部用最新研制的反物质防空炮唐突的向它开火(什么飞船能抵抗这样的攻击?!),这架万年不遇的地外飞船就这样被击毁在无边戈壁...

 

OI地外生化研究所的科学家立即在第一时间赶到现场,在戈壁的黄沙之上,到处可见飞船的残骸和外星人已粉碎的遗体,破碎的飞船是没有什么研究价值了,科学家收集了外星人的遗体并回到了研究中心。通过最高端的科技,科学家分离了这种生物细胞中的遗传信息载体“XNA”(类似而不同于地球生物的“DNA”),你可以将“XNA”看成一串密码子组成的长链,基因研究所首席研究员Talent对“XNA”进行了分析,将不同的密码子编号,使每个密码子对应一个小写英文字母,在这生物的不同细胞中,“XNA”是不一样的,但这些细胞的“XNA”中,有一些公共部分,选出这些“XNA”最长的公共部分,就构成了“XNA”的核心框架,我们称之为该生物的“基因的核”,所谓“最长的公共部分”,就是这些“XNA”最长的公共密码子序列,“公共密码子序列”在“XNA”中不一定是连续的,但一定不能改变原顺序,科学家们想了解这种生物的“基因的核”。于是Talent将这个任务交给了聪明的你,面对众多的“XNA”序列,每个“XNA”的长度(length)又很长,你无法目测答案,就准备编一个通用的程序,对于若干组“XNA”,求出它们的“基因的核”,(为降低难度)你只需要输出“基因的核”长度就可以。

輸入說明
第一行是一个整数N,代表要处理的“XNA”的数量,以下N行是N个待处理的“XNA”的代码(每个“XNA”由一串小写字母组成,每个字母对应一个密码子)。
輸出說明
只有一行,一个整数:“基因的核”的长度。
範例輸入 #1
输入1:
2
qwertyuiopasdfghjklzxcvbnmasdfghjklqwererttyyuu
mnbvcxzasdfgqwertyhjklpoyuiotrewqwertyuuioppas

输入2:
4
abcdefg
bcdefgh
cdefghi
defghij
範例輸出 #1
输出1:
18
输出2
4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 30.0s , <1K
提示 :

对于20%的数据,N<=5,length<=20
对于50%的数据,N<=10,length<=50
对于100%的数据,N<=100,length<=500,对于任何一组测试数据,设:“XNA”的平均长度为L,则L^N<=30000000

声明:

此题来源于vijos,原管理员为vijos_car。
题目中的限制条件,由于测资难生,将L^N<=30000000改为所有L^N<=40000000,请见谅!
这题中的输入请用EOF,测资为liouzhou_101提供,与vijos原题的测资有不同之处请见谅,若发现测资错误,请及时提醒现任管理员。
vijos上此题的时间限制、空间限制不详,这里输入测资有5笔,时间限制为30s,空间限制为256MB,应该相当宽松。

欢迎提供测资!

標籤:
出處:
vijosvijos_car [管理者: liouzhou_101 (王启圣) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」