f437 - 1368 - DNA Consensus String
題目描述
題目給定 M 個長度為 N 的 DNA 序列 (由 A, T, G, C 組成)，要求找出與這些序列漢明距離總和最小的字串 (共識字串)，並輸出該字串以及最小的漢明距離總和 (共識錯誤)。如果有多個共識字串，則輸出字典序最小的那個。
解題思路
本題的核心思想是貪心策略。對於 DNA 序列的每一位，統計 A, T, G, C 四個鹼基出現的次數，選擇出現次數最多的鹼基作為共識字串對應位上的鹼基。然後計算共識字串與所有輸入序列的漢明距離總和。
具體步驟如下：
- 讀取輸入，包括 DNA 序列的數量 M 和長度 N，以及 M 個 DNA 序列。
- 建立一個二維陣列
dp[N][4]，用於統計每一位上 A, T, G, C 四個鹼基的出現次數。 - 遍歷所有 DNA 序列，對於每個序列的每一位，將對應鹼基的計數加 1。
- 建立一個字串
aa，用於儲存共識字串。 - 遍歷每一位，找到出現次數最多的鹼基，將其添加到
aa中。 - 計算共識字串
aa與所有輸入序列的漢明距離總和anss。 - 輸出共識字串
aa和共識錯誤anss。
複雜度分析
- 時間複雜度: O(M * N)，其中 M 是 DNA 序列的數量，N 是 DNA 序列的長度。需要遍歷所有 DNA 序列的每一位來統計鹼基出現次數，以及遍歷每一位來構建共識字串和計算漢明距離。
- 空間複雜度: O(N)，主要用於儲存
dp[N][4]陣列和共識字串aa。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
string a[1001];
int dp[1001][4],t,x,y;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> x >> y;
for(int i=0;i<1001;++i)
for(int j=0;j<4;++j)
dp[i][j]=0;
int ans[y]={0},anss=0;
string aa;
for(int i=0;i<x;++i){
cin >> a[i];
for(int j=0;j<y;++j){
if(a[i][j]=='A')
++dp[j][0];
else if(a[i][j]=='C')
++dp[j][1];
else if(a[i][j]=='G')
++dp[j][2];
else
++dp[j][3];
}
}
for(int i=0;i<y;++i){
ans[i]=max(max(dp[i][0],dp[i][1]),max(dp[i][2],dp[i][3]));
for(int j=0;j<4;++j){
if(ans[i]==dp[i][j]){
if(j==0){
aa+='A';
anss+=x-dp[i][j];
break;
}
else if(j==1){
aa+='C';
anss+=x-dp[i][j];
break;
}
else if(j==2){
aa+='G';
anss+=x-dp[i][j];
break;
}
else{
aa+='T';
anss+=x-dp[i][j];
break;
}
}
}
}
cout << aa << "\n" << anss << "\n";
}
}