UVaOJ 1368 - DNA Consensus String

问题描述

解法一：模拟 + 贪心

由于本题中的 Hanmind Distance 是按照字符串的每一位去计算的，可以使用贪心策略，把每个 testcase 中的长度为 n 的字符串 $S$ 看成是 n 个字符 $S_1 \ldots S_n$ ，最终求得的字符串 res 中的每一位字符 res[i] 和已知字符串组 dna 中对应 i 位置的各个字符相似度最高，即取每个位置出现次数最多的字符。同时注意：根据题目要求，对于出现次数一样多的字符，使用字典序排序。

#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;
}

#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;

}

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}")

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}")

AOAPC II UVaOJ 字符串数组贪心