這種線性最值問題一般不是貪心就是動歸
應該是道貪心題，因為每一列的值與其他列沒有什麼關系（這是判斷貪心問題的根本大法），對于每一列找出使其Hamming距離最小的值即可，由于此題隻要值相同就是0，值不同就是1，沒有遠近之分，是以每一個值都是原來出現次數最多的值。
一定注意出現多解的時候如何選擇！！！！此題就被坑了，一定注意此題是輸出字典序最小的！！！
1 #include "bits/stdc++.h"
2 using namespace std;
3 const int MAX=1005;
4 int t,n,m,ans;
5 char s[55][MAX],as[MAX];
6 struct Cha{
7 char c;
8 int num;
9 bool operator < (Cha &tt) const {
10 return num<tt.num;
11 }
12 }a[5],an;
13 int main(){
14 freopen ("string.in","r",stdin);
15 freopen ("string.out","w",stdout);
16 int i,j;
17 scanf("%d",&t);
18 a[1].c='A',a[2].c='T',a[3].c='C',a[4].c='G';
19 while (t--){
20 ans=0;
21 scanf("%d%d",&n,&m);
22 for (i=1;i<=n;i++) scanf("%s",s[i]+1);
23 for (i=1;i<=m;i++){
24 a[1].num=a[2].num=a[3].num=a[4].num=0;
25 for (j=1;j<=n;j++){
26 if (s[j][i]=='A') a[1].num++;
27 if (s[j][i]=='T') a[2].num++;
28 if (s[j][i]=='C') a[3].num++;
29 if (s[j][i]=='G') a[4].num++;
30 }
31 an=a[1];
32 if (an<a[3]) an=a[3];
33 if (an<a[4]) an=a[4];
34 if (an<a[2]) an=a[2];
35 as[i]=an.c;
36 ans+=n-an.num;
37 }
38 for (i=1;i<=m;i++)
39 printf("%c",as[i]);
40 printf("\n%d\n",ans);
41 }
42 return 0;
43