contents
Problem
給予一堆相同長度的 ATCG 構成的基因,找一段字典順序最小的基因,使得與給定的基因漢明碼距離(有多少位置不同)總和最小。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
3 5 8 TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 4 10 ACGTACGTAC CCGTACGTAG GCGTACGTAT TCGTACGTAA 6 10 ATGTTACCAT AAGTTACGAT AACAAAGCAA AAGTTACCTT AAGTTACCAA TACTTACCAA
|
Sample Output
1 2 3 4 5 6
|
7 ACGTACGTAA 6 AAGTTACCAA 12
|
Solution
對於每一個位置,找到字符使用最多次的使用,這樣將可以將此位置的漢明碼距離縮到最短。
最後討論一下相同時所需要的最小字典順序,即可完成。
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
|
#include <stdio.h> #include <algorithm> using namespace std; int main() { int testcase; int n, m; char DNA[64][1024]; scanf("%d", &testcase); while (testcase--) { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) scanf("%s", DNA[i]); int hh = 0; char ret[1024] = {}, cc[] = "ACGT"; for (int i = 0; i < m; i++) { int cnt[4] = {}, mx = 0; for (int j = 0; j < n; j++) cnt[find(cc, cc+4, DNA[j][i]) - cc]++; for (int j = 0; j < 4; j++) { if (cnt[j] > cnt[mx]) mx = j; } ret[i] = cc[mx], hh += n - cnt[mx]; } printf("%sn%dn", ret, hh); } return 0; }
|
近期评论