问题描述
p1368原题链接：UVaOJ 1368 - DNA Consensus String
相关说明：本题为《算法竞赛入门经典（第2版）》习题 3-7
解法一：模拟 + 贪心
由于本题中的 Hanmind Distance 是按照字符串的每一位去计算的，可以使用贪心策略，把每个 testcase 中的长度为 n 的字符串 $S$ 看成是 n 个字符 $S_1 \ldots S_n$ ，最终求得的字符串 res 中的每一位字符 res[i] 和已知字符串组 dna 中对应 i 位置的各个字符相似度最高，即取每个位置出现次数最多的字符。同时注意：根据题目要求，对于出现次数一样多的字符，使用字典序排序。
|
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 |
#include <bits/stdc++.h> using namespace std; int main() { int t, m, n; cin >> t; while (t--) { cin >> m >> n; string line; vector<string> dna(m); for (int i = 0; i < m; ++i) cin >> dna[i]; string res = ""; int error = 0; map<char, int> nucl_cnt; for (int j = 0; j < n; ++j) { nucl_cnt['A'] = 0, nucl_cnt['C'] = 0, nucl_cnt['G'] = 0, nucl_cnt['T'] = 0; for (int i = 0; i < m; ++i) nucl_cnt[dna[i][j]] += 1; int max_number = 0; char max_char = 'A'; for (auto it : nucl_cnt) if (it.second > max_number) { max_number = it.second; max_char = it.first; } res += max_char; error += (m - max_number); } cout << res << endl << error << endl; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
t = int(input()) for _ in range(t): m, n = map(int, input().split()) dna = [] for i in range(m): dna.append(input()) nucl_cnt = {'A': None, 'C': None, 'G': None, 'T': None} res = "" error = 0 for j in range(n): for char in nucl_cnt: nucl_cnt[char] = 0 for i in range(m): nucl_cnt[dna[i][j]] += 1 max_number = 0 max_char = 'A' for char, count in nucl_cnt.items(): if count > max_number: max_number = count max_char = char res += max_char error += (m - max_number) print("{res}\n{error}") |
