2951.DNA序列-预推免

通过数:16提交数:29学校:深圳大学保研机试真题 题目列表 标签
题目描述 两个等长字符串的 $Hamming$ 距离等于字符不同的位置个数。例如,${ACGT}$ 和 ${GCGA}$ 的 $Hamming$ 距离为 ${2}$(左数第 ${1}$、${4}$ 个字符不同)。 输入 ${m}$ 个等长的 $DNA$ 序列,求其中的某个 $DNA$ 序列,到其它 ${m-1}$ 个序列的总 $Hamming$ 距离最小。注意:如有多解,要求字典序最小的解。 例如,对于下面 ${3}$ 个 DNA 序列: 3 ATTGC ACTGT TCCGC 其中:${TCCGC}$ 到 ${ATTGC}$ 的 $Hamming$ 距离是 ${3}$,到 ${ACTGT}$ 的 $Hamming$ 距离是 ${3}$,因此它到其它序列的总 $Hamming$ 距离和是 ${6}$。同理,${ATTGC}$ 和 ${ACTGT}$ 到其它序列的总 $Hamming$ 距离和都是 ${5}$,按字典序,则最优解为 ${ACTGT}$。 输入格式 第一行输入 DNA 数目 ${m}$。 其余各行,依次输入 ${m}$ 个等长的 DNA 序列。 输出格式 输出到其余 ${m-1}$ 个序列的 $Hamming$ 距离和最小的 DNA 序列,以及该总距离。 数据范围 ${1 \leq m \leq 50}$ 每个 DNA 序列长度不超过 ${500}$,且仅由字符 ${'A'}$、${'C'}$、${'G'}$、${'T'}$ 组成。 输入样例 3 ATTGC ACTGT TCCGC 输出样例 ACTGT 5
C
补全
点击调试按钮即可调试代码。

点击提交按钮即可提交代码。