Uva1368 DNA序列
程序员文章站
2022-03-14 20:01:15
...
题意:输入m个长度均为n的DNA序列,求一个DNA序列,到所有序列的总Hamming距离尽量小。两个等长字符串Haming距离等于字符不同位置个数,例如,ACGT和GCGA的Hamming距离为2(左边第1,4字符不同)。
题解:用一个二维数组存输入的DNA序列,求出数组每一列出现最先次数最多的字符,这些字符的组成序列就是所求的DNA序列,Hamming距离,每一列与出现最多的字符不同的个数之和。
#include<iostream>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 1010;
const int maxm = 55;
const string temp = "ACGT";
int m, n, t;
int num[4][maxn];
string s;
int main(){
freopen("data.in", "r", stdin);
scanf("%d", &t);
while(t--){
scanf("%d%d", &m, &n);
fill(num[0], num[0] + 4*maxn, 0);
for(int i = 0; i < m; ++i){
cin >> s;
for(int j = 0; j < n; ++j){
switch(s[j]){
case 'A' : num[0][j]++; break;
case 'C' : num[1][j]++; break;
case 'G' : num[2][j]++; break;
case 'T' : num[3][j]++; break;
}
}
}
int cnt = 0;
string t = "";
for(int j = 0; j < n; ++j){
int index = 0;
for(int i = 0; i < 4; ++i){
if(num[index][j] < num[i][j]){
index = i;
}
}
cnt += (m - num[index][j]);
t = t + temp[index];
}
cout << t << endl << cnt << endl;
}
return 0;
}
上一篇: php错误抑制符是什么
下一篇: php如何删除字符串中的html标签