MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1368 - DNA Consensus String
AOAPC II

UVaOJ 1368 - DNA Consensus String

Chai
2021-11-24 0:00:00在线评测阅读 266

问题描述

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 位置的各个字符相似度最高,即取每个位置出现次数最多的字符。同时注意:根据题目要求,对于出现次数一样多的字符,使用字典序排序。

C++
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;
}
Python
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}")
AOAPC II UVaOJ 字符串 数组 贪心
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz