#1339. 进化论

进化论

题目背景

进化论,生物学术语。是由英国生物学家查尔斯·达尔文(1809—1882)曾经乘坐贝格尔号舰作了历时 55 年的环球航行中,对动植物和地质方面进行了大量的观察和采集后,当时是对物种起源的一种猜测而提出的一种假说。随着进化论的发展,产生了现代综合进化论,而现代进化学绝大部分以查尔斯·罗伯特·达尔文的进化论为指导,埃尔温·薛定谔的《生命是什么》为主体方向,进化论已为当代生物学的核心思想之一。

所有生物物种是由少数共同祖先,经过长时间的自然选择过程后演化而成。2018年诺贝尔化学奖:定向进化技术是进化论的具体应用和实现。

古希腊时期曾出现零星的进化思想,包括现在“进化论”者的进化无方向存在即合理,都不具有系统性的科学性。

题目描述

如今的生物种类均变幻莫测。因此,科学家们使用 AZ, azA\sim Z,~a\sim z 为每种生物的基因进行编号。已知现在共有 nn 个物种,每个物种拥有一个长度为 LiL_i 的基因编码。随着科技的发展,人类已经不再拘泥于发现物种,而在于利用基因编辑重新创造物种,或者换句话说,克隆。所以,对于已经具有的基因序列,人类可以通过编辑将其转换为另一个序列。

当然,基因编辑显然需要一定的代价。对于两个物种,基因编辑的代价为两物种基因序列所具有的不同字母的数量(严格区分大小写,但不考虑位置)。如今人们已经具有了第一种生物的基因序列。请问最少付出多少代价能使得人类掌握全部的基因序列。

注意“具有”意味着人类可以多次使用某个基因序列,即基因序列本身不会因为编辑而改变,编辑的作用在于创造新的序列。

输入格式

第一行为一个正整数 TT,表示数据组数。

对于每组数据,第一行为一个正整数 nn,表示物种的数量。接下来 nn 行,每行包含一个正整数 LiL_i 和一个长度为 LiL_i 的字符串 SiS_i,表示物种的基因序列。

输出格式

TT 行,对于每组数据,输出一个整数表示最少付出的代价。

2
3
3 ABC
3 DEF
3 DGH
8
6 ABCFGE
5 AHSDF
6 SDAOFM
7 OPaAion
6 abcfgE
5 ADjdn
6 KLAdpO
7 OPSDFAM
11
61

说明

对于 30%30\% 的数据,n100n≤100

对于 100%100\% 的数据,2n1032≤n≤10^31T31≤T≤31Li501≤L_i≤50{Si}{AZ  az}\{S_i\}∈\{A\sim Z\ \cup\ a\sim z\}

请尽可能避免因 \n 不兼容而造成的读入错误。

  • 第一个物种到第二个物种的代价为 {ABCDEF}=6\{\text{ABCDEF}\}=6
  • 第一个物种到第三个物种的代价为 {ABCDGH}=6\{\text{ABCDGH}\}=6
  • 第三个物种到第二个物种的代价为 {DGHEF}=5\{\text{DGHEF}\}=5

所以顺序为 1231\to 2\to 3,最少代价为 6+5=116+5=11