Contents
Problem
題目網址
求出與所有字串相差最少的(漢明距離)。
Solution
直接用每一字串相同位置,出現次數最多的字母去拼成一個字串即為答案。
Code
UVa 1368
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
#include<cstring> #define N 50 using namespace std;
int () { int ret[20] = {}; ret[0] = 0; ret[2] = 1; ret[6] = 2; ret[19] = 3;
char DNA[4] = { 'A', 'C', 'G', 'T' }; char str[N][1001], ans[1001]; int Case;
scanf("%d", &Case); while (Case--) { int n, m, i, j, diff = 0; scanf("%d%dr", &n, &m); for (i = 0; i < n; i++) gets(str[i]);
for (i = 0; i < m; i++) { int count[4] = {}; for (j = 0; j < n; j++) count[ret[str[j][i] - 'A']]++;
int max = 0; for (int k = 1; k < 4; k++) if (count[max] < count[k]) { max = k; }
ans[i] = DNA[max]; diff += (n - count[max]); }
ans[i] = NULL; puts(ans); printf("%dn", diff); }
return 0; }
|
近期评论