hihoCoder 1052-基因工程 #1052 : 基因工程 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho正在进行一项基因工程实验。他们要修改一段长度为N的DNA序列，使得这段DNA上最前面的K个碱基组成的序列与最后面的K个碱基组成的序列完全一致。 例如对于序列”ATCGATAC”和K=2,可以通过将第二个碱基修改为”C”使得最前面2个碱基与最后面两个碱基都为”AC”。当然还存在其他修改方法，例如将最后一个碱基改为”T”，或者直接将最前面两个和最后面两个碱基都修改为”GG”。 小Hi和小Ho希望知道在所有方法中，修改碱基最少的方法需要修改多少个碱基。 输入 第一行包含一个整数T(1 <= T <= 10)，代表测试数据的数量。 每组测试数据包含2行，第一行是一个由”ATCG”4个大写字母组成的长度为N(1 <= N <= 1000)的字符串。第二行是一个整数K(1 <= K <= N)。 输出 对于每组数据输出最少需要修改的碱基数量。 样例输入 2 ATCGATAC 2 ATACGTCT 6 样例输出 1 3
简单的字符串处理题目，该题要求修改字符保证前k个字符和后k个字符相同，求最小的修改次数。这个题目会让人想到字符串的编辑距离，但不完全相同，因为这题是对单个字符串的修改，不能想当然的把前后k个字符取出来，然后逐一比较是否相等，因为如果前k个字符和后k个字符有重叠的话，你修改了某个字符，会影响下一次比较。 比如字符串CTACATGT，长度n=8，k=6，前k个字符串为s1=CTACAT，后k个字符串为s2=ACATGT，我们不能单独求s1和s2的距离，而是需要把这些字符放到原字符串中，再进一步研究你会发现其实就是在原字符串中保证s[i]=s[i+2]，其中2=d=n-k。也就是下图中红色和绿色的两组字符要分别相同。
现在我们分析红色那组字符，首先s[0]==s[2]不成立，可以把s[0]改成A；也可以把s[2]改成C，如果我们把s[2]改成C的话，虽然s[0]==s[2]成立，但是s[2]==s[4]又不成立了，又要修改s[4]；但是如果我们把s[0]改成A的话，则s[0]==s[2]==s[4]都成立，且修改次数更少。那么要怎样才能使修改的次数最少呢？
我们回到问题的本源：使用红色那组字符都相同，为了使修改次数最少，我们当然是将所有字符统一成当前出现次数最多的那个字符咯，这样只需要修改较少的非同一字符，在这个例子中，就是修改成出现次数最多的A。
如果前k个字符串和后k个字符串没有重叠，那就很简单了，只需依次检查对应字符是否相等。
理解了以上内容，代码很快就能写出来了：
[cpp]
#include<iostream>
#include<string>
using namespace std;
//求4个数的最大值
int max4(int a,int b,int c,int d)
{
int maxab=a>b?a:b;
int maxcd=c>d?c:d;
return maxab>maxcd?maxab:maxcd;
}
int main()
{
int t,k,n,d,ans;//t,k为题意；n为字符串长度；d为n-k相隔为d的字符需要相等；ans表示需要修改的碱基数量。
string s;
cin>>t;
while(t–)
{
ans=0;
cin>>s>>k;
n=s.size();
d=n-k;
if(2*k<=n)//如果最前k个碱基和最后k个碱基没有重叠的话
{
for(int i=0;i<k;i++)
if(s[i]!=s[i+d])//只需要依次检查对应字符是否相等即可
ans++;
}
else//如果有重叠，则另行讨论
{
for(int i=0;i<d;i++)//把所有碱基分成d组，需要确保每组都是同一个字符
{
int A=0,T=0,G=0,C=0,num=0;
for(int j=i;j<n;j+=d)//对于每一组，求出该组中出现次数最多的碱基的个数
{
num++;
if(s[j]==’A’)
A++;
else if(s[j]==’T’)
T++;
else if(s[j]==’G’)
G++;
else
C++;
}
int maxATGC=max4(A,T,G,C);//该组全部修改成出现次数最多的碱基
int change_num=num-maxATGC;//用该组中所有碱基个数减去出现次数最多的碱基个数，就是需要修改的碱基个数
ans+=change_num;
}
}
cout<<ans<<endl;
}
return 0;
}
[/cpp]
本代码提交AC，用时1MS，内存0MB。
]]>