基因工程 HihoCoder - 1052(有意思)

本文主要是介绍基因工程 HihoCoder - 1052(有意思)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小Hi和小Ho正在进行一项基因工程实验。他们要修改一段长度为N的DNA序列，使得这段DNA上最前面的K个碱基组成的序列与最后面的K个碱基组成的序列完全一致。  

例如对于序列"ATCGATAC"和K=2,可以通过将第二个碱基修改为"C"使得最前面2个碱基与最后面两个碱基都为"AC"。当然还存在其他修改方法，例如将最后一个碱基改为"T"，或者直接将最前面两个和最后面两个碱基都修改为"GG"。

小Hi和小Ho希望知道在所有方法中，修改碱基最少的方法需要修改多少个碱基。

Input

第一行包含一个整数T(1 <= T <= 10)，代表测试数据的数量。

每组测试数据包含2行，第一行是一个由"ATCG"4个大写字母组成的长度为N(1 <= N <= 1000)的字符串。第二行是一个整数K(1 <= K <= N)。

Output

对于每组数据输出最少需要修改的碱基数量。

Sample Input

2  
ATCGATAC  
2  
ATACGTCT
6 

Sample Output

1  
3   

这道题目一开始完全没有思路。后来看了大神的代码，还是大佬牛逼，什么都可以想出来。

题意是一段字符串，然后截取前K个，在从后往前截取K个，就这两段字符串进行对比，然后你可以改变一些字符。使这两个字符串完全匹配，输出这个最小的改变字符的数量。题意就是这么的简单，但是我不会做这道题，题意再简单也没有用。看了大神的代码，我就用手在纸上画了画模拟的过程。确实很奇妙。

例如 ABCDAB 这个字符串，我们都知道最后的换取结果是 ABABAB,换掉C和D ，就可以了。但是这个过程计算机怎么实现呢？首先列出截取4个后的两个字符串，为 ABCD CDAB ,因为是有交叉字符出现的情况，可能我们还掉一个就可以使很多字符都可以相同的。两个字符串一 一对应后，(下标我先定为从1开始)1，3，5，是对应的，而2，4，6，这个循环节是(n-k)(n是长度，k世是截取数量)，是对应的位置，我们就可以将这个问题换成1，3，5   和2，4，6 这两块问题了，看怎么换掉才是最小的数量。分块数量是for(int i=0;i<(循环节);i++) ，这样就将问题分为好几个块，这样就将问题简单化。

然后，就是找到最小的数量，就是 比如   ABCDAB 这样的 截取4个 的时候， C ,D字符是重复的，所以现在就可以比较A,C,A的数量，因为 A,C 是对应的 ，这个 C与下一个A ，也是对应的，这个C出现2次，另外两个 A出现1次，我们人脑想想也是将C换成A，换成数量多的那一个(A有2个，C有一个) ，所以就将C换为A，这个就是最少的换的字符了。每一次分块都是这样算。

 

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
const int maxn=100005;
using namespace std;
#include<map>
#include<string>
#include<string.h>
typedef long long ll;int main()
{int t;scanf("%d",&t);char s[maxn];int k;while(t--){scanf("%s",s);scanf("%d",&k); int len=strlen(s);if(2*k<=len){int ans=0;for(int i=0;i<k;i++){if(s[i]!=s[len-k+i])ans++;}printf("%d\n",ans);}else	{int ans=0;int jie=len-k;for(int i=0;i<jie;i++){int a[4]={0};for(int j=i;j<len;j+=jie){if(s[j]=='A')a[0]++;else if(s[j]=='T')a[1]++;else if(s[j]=='G')a[2]++;	else if(s[j]=='C')a[3]++;}int maxshu=-1;int sum=0;for(int j=0;j<4;j++){maxshu=max(maxshu,a[j]);sum+=a[j];}ans+=sum-maxshu;}printf("%d\n",ans);}}return 0;
}

思路就是这样。 很巧妙。                                      

 

这篇关于基因工程 HihoCoder - 1052(有意思)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---