UVA 1368

在这里插入图片描述在这里插入图片描述在这里插入图片描述

题目大意:

输入一个n表示有n组数据,对于每组数据,输入两个数,一个代表有几个DNA序列,另一个代表每个序列的长度,你的任务是构造这样一个序列,使得这个序列和其他几个序列不同的字符最少,并输出这个序列和不同的字符数。

解题思路:

对于要构造的序列,可以贪心的去构造,我们逐字符的统计,设置一个标记数组num ,num a b 表示在第a个位置,b字符出现过几次。构造序列时,选择每个位置出现次数最多的单词,遍历num数组即可。对于不同的个数,我们用已经构造好的序列和每一个序列逐个比较即可。AC代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
using namespace std;
string s[55];
int num[1050][150];
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		memset(num,0,sizeof num);
		int m,n;
		cin>>m>>n;
		for(int i=0;i<m;i++)
		  cin>>s[i];
		for(int i=0;i<m;i++)
		  for(int j=0;j<n;j++)
		    num[j][s[i][j]]++;//统计第j个位置当前字符出现过几次
		string ans="";
		for(int i=0;i<n;i++)//构造序列的过程
		{
			int t=-1;char ch;
			for(int j='A';j<='Z';j++)
			{
				if(t<num[i][j])
				{
					t=num[i][j];
					ch=j;
				}
			}
			ans+=ch;
		}
		int ans1=0;//统计不同字符数
		for(int i=0;i<m;i++)
		  for(int j=0;j<n;j++)
		    if(ans[j]!=s[i][j])
			  ans1++;
		cout<<ans<<endl<<ans1<<endl;
	}
	return 0;
}
原文地址:https://www.cnblogs.com/Hayasaka/p/14294231.html