MYF

UVa 1368 DNA Consensus String

Posted on | In | | Visitors

题目链接

UVa 1368

方法：map

题目分析

题目大意

给出n条长度为len的DNA，问len的每个位置出现概率最大的碱基是哪个？如果两个碱基概率相同，取字典序较小者。输出概率最大的DNA序列，并且求出每条给定的dna序列和最概然dna序列有多少位不一样，对这些数字求和。

解析

暴力，统计即可。

代码

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
51
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
int main(){
    char dna[60][1005];
    int t,n,len,ans;
    char mx;
    map<char, int>mp;
    scanf("%d",&t);
    while (t--) {
        ans=0;
        scanf("%d %d",&n,&len);
        for (int i=1; i<=n; i++) {
            scanf("%s",dna[i]);
        }
        for (int i=0; i<len; i++) {
            mp.clear();
            mx='.';
            mp[mx]=-1;
            for (int j=1; j<=n; j++) {
                if (mp.count(dna[j][i])==0)
                    mp[dna[j][i]]=1;
                else
                    mp[dna[j][i]]++;
                
                if (mp[mx]<mp[dna[j][i]]||(mp[mx]==mp[dna[j][i]]&&mx>dna[j][i]))
                    mx=dna[j][i];
            }
            printf("%c",mx);
            ans+=n-mp[mx];
        }
        printf("\n%d\n",ans);
    }
}