Exercises in Chapter 3 数组和字符串

aoapc_2nd C++ 编程 所有文稿

3-7: DNA序列

DNA Consensus String, ACM/ICPC Seoul 2006, UVa1368

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <cmath>
using namespace std;
/*
8 5
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
*/
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    string dna[55];
    int hu[55];
    memset(hu,0,sizeof(hu));
    for(int i=1;i<=n;i++) cin>>dna[i];
    for(int i=1;i<=n;i++)
    {
        int tot=0;
        for(int j=0;j<m;j++)
        {
            for(int k=1;k<n;k++)
            {
                if (dna[i][j]!=dna[(i+k)%5][j]) tot++;
            }
        }
        hu[i]=tot;
    }
    //for(int i=1;i<=n;i++) cout<<hu[i];
    cout<<endl;
    int mi=1;
    for(int i=2;i<n;i++)
    {
        if (hu[i]<hu[mi]||(hu[i]==hu[mi]&&dna[i]<dna[mi])) mi=i;
    }
    cout<<mi<<endl<<dna[mi];
    return 0;
}

网上参考做法（github代码库里只有1-6题）

#include<bits/stdc++.h>
#define _for(i,a,b) for(int i=(a);i<(b);++i)//for循环的一种简单写法的宏定义
using namespace std;
int main(){
    int T,m,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&m,&n);
        string input[m];
        _for(i,0,m) cin>>input[i];//读入m个字符串
        map<char,int>um;//存储m个字符串中相同位置出现的字符及其对应的次数,注意map按键有小到大的顺序存储
        int error=0;//存储Hamming距离和
        _for(i,0,n){
            _for(j,0,m) ++um[input[j][i]];
            char MAX='A';
            for(auto&j:um)//查找出现次数最多的字符
                if(j.second>um[MAX])
                    MAX=j.first;
            putchar(MAX);//输出出现次数最多的字符
            error+=m-um[MAX];//加上Hamming距离
            um.clear();//清空map
        }
        printf("\n%d\n",error);//输出Hamming距离和
    }
    return 0;
}

直接取该列出现次数最高的字符，若并不存在一个序列包含了所有频次最高的字符呢？ -2019.2.21