la3602（贪心）

/* translation: 给出若干条由A，G，C，T组成的字符串。现在求一个字符串，使得它到每个给出的字符串的hamming距离最小 haming距离定义为两个字符串不同字符的个数。 solution: 贪心 很明显，对于要求字符串的i位置上的字符来说，该字符必定在其它字符串上出现的字符最多。明白这一点也就没有难度了。 */ #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1000 + 5; const char letter[] = {'A', 'C', 'G', 'T'}; char s[55][maxn]; int m, n, cnt[5]; int setNo(char c) { if(c == 'A') return 0; if(c == 'C') return 1; if(c == 'G') return 2; if(c == 'T') return 3; } int main() { //freopen("in.txt", "r", stdin); int T; scanf("%d", &T); while(T--) { scanf("%d%d", &m, &n); for(int i = 0; i < m; i++) scanf("%s", s[i]); char ans[maxn]; int p = 0; int res = 0; for(int i = 0; i < n; i++) { memset(cnt, 0, sizeof(cnt)); int maxv = -1; for(int j = 0; j < m; j++) { int no = setNo(s[j][i]); cnt[no]++; maxv = max(maxv, cnt[no]); } int id; for(id = 0; id < 4; id++) if(cnt[id] == maxv) break; for(int i = 0; i < 4; i++) if(i != id) res += cnt[i]; ans[p++] = letter[id]; } for(int i = 0; i < n; i++) printf("%c", ans[i]); printf("\n%d\n", res); } return 0; }