解題區/解題區 - UVa

UVa 1368 - DNA Consensus String

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給予一堆相同長度的 ATCG 構成的基因，找一段字典順序最小的基因，使得與給定的基因漢明碼距離(有多少位置不同)總和最小。

Sample Input

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
TAAGATAC 
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("%s\n%d\n", ret, hh);
    }
    return 0;
}