算典03_習(xí)題_07_UVA-1368

2019-11-08 03:12:18

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

DNA Consensus String

題意

給出一組DNA序列(即一些字符串),找出與每個(gè)DNA序列的差最小的DNA序列 差的意思是序列中位置相同但字符不同的位置的個(gè)數(shù) 輸出這個(gè)DNA序列以及最小的差

題解

1.準(zhǔn)備

這里有一個(gè)小技巧，DNA只有“ATCG”四種，要統(tǒng)計(jì)這四種出現(xiàn)的次數(shù)，就需要一種對(duì)應(yīng)關(guān)系，如讓ATCG分別對(duì)應(yīng)0123，那么我就可能用a[0]表示A的出現(xiàn)次數(shù)

char N[] = {"ACGT"};int Nid(char c){ return strchr(N, c) - N; } //N[Nid(c)];

我這里還是一如既往地使用常量表來很簡(jiǎn)便地建立這種對(duì)應(yīng)關(guān)系，然后用一個(gè)查找函數(shù)，使其可以通過字符找到下標(biāo)，如上面的代碼，N[Nid(“A”)]就可以表示A的次數(shù)，這樣就方便多了

2.實(shí)現(xiàn)

有了上一步的準(zhǔn)備，代碼就很顯而易見了，這里我對(duì)所有的DNA一起統(tǒng)計(jì)某一位，這一位上出現(xiàn)最多的字符就是結(jié)果在這一位的字符，而差就用總的DNA數(shù)減去其出現(xiàn)的次數(shù)即可(每一位都這樣處理)

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 1e3 +5;#define met(a,b) memset(a, b, sizeof(a));char N[] = {"ACGT"};int Nid(char c){ return strchr(N, c) - N; } //N[Nid(c)];int m, n, res;char s[maxn][maxn];int ans[maxn][4];char solve(int id){ int Max = 0, ID = 0; for(int i = 0; i < 4; ++i){ if(Max < ans[id][i]) { Max = ans[id][i]; ID = i; } } res += n - Max; return N[ID];}int main(){ #ifdef _LOCAL freopen("in.txt","r", stdin); #endif // _LOCAL int t; cin >> t; while(t--) { cin >> n >> m; for(int i = 0; i < n; ++i) { scanf("%s", s[i]); } met(ans, 0); for(int i = 0; i < m; ++i){ for(int j = 0; j < n; ++j){ ++ans[i][Nid(s[j][i])]; } } res = 0; for(int i = 0; i < m; ++i){