欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVa1368 - DNA Consensus String

程序员文章站 2024-03-19 11:51:10
...
//UVa1368 - DNA Consensus String
//题目:给m个长度为n的DNA序列,求一个DNA序列到所有序列的总Hamming距离最小,Hamming距离为不同字符的位置的个数。
//分析:每列找出最多重复次数。

#defien A1 //1,only DNA
#defien A2 //2,已AC

#ifdef A1
#include<stdio.h>
#include<string.h>
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
	//输入
		int m, n;
		scanf("%d %d",&m,&n);//m个n长度的
	//存储
		int s[n][4];
		memset(s,0,sizeof(s));
		char f[4]={'A','C','G','T'};
	//找个数
		for(int i = 0; i <= m; i++){//rows
			int g,count = 0;
			char ch;
			//while((ch=getchar()) != '\n'){
			while(scanf("%c",&ch) == 1){//every row
				//getchar();
				if(ch=='\n')break;
				if(ch=='A')g=0;
				if(ch=='C')g=1;	
				if(ch=='G')g=2;
				if(ch=='T')g=3;
				s[count][g] += 1;	
				count++;
			}
		}
		//printf("%d %d %d %d %d\n",s[1][0],s[1][1],s[1][2],s[1][3],s[0][0]);	
	//输出
		for(int j = 0; j < n; j++){
			int max = 0, T = 4;
			//int *pt;
			while(T){
				//pt = &s[j][T];
				if(((s[j][T-1]) > (s[j][max])))max = T-1;
				T--;
			}
			//printf("%d\n",s[j][T-1]);
			printf("%c",f[max]);
		}
		putchar('\n');
	}
	return 0;
}
#endif

#ifdef A2
#include<stdio.h>
#include<string.h>
int main(void){
    int t;
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d %d",&n,&m);
		char DNA[n][m+1];
		for(int i=0;i<n;i++) scanf("%s",DNA[i]);
		int list[4];
		int num=0,num1;
		for(int i=0;i<m;i++){
			memset(list,0,sizeof(list));
			for(int j=0;j<n;j++){
				if(DNA[j][i]=='A') list[0]++;
				else if(DNA[j][i]=='C') list[1]++;
				else if(DNA[j][i]=='G') list[2]++;
				else list[3]++;
			}
			int temp=0,ans;
			for(int k=0;k<4;k++){
				if(list[k]>temp) {
				ans=k;
				temp=list[k];
				num1=n-list[k];
			    }
			}
			if(ans==0) printf("A");
			else if(ans==1) printf("C");
			else if(ans==2) printf("G");
			else printf("T");
			num+=num1;
		}
		printf("\n%d\n",num);
	}    
    return 0;
}
#endif