HihoCoder#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)。

输出

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

样例输入

ATCGATAC

ATACGTCT

样例输出

貌似自己很少做这种没有任何提示的题，之前做的也都感觉很简单。

话说人家的技术博客全是技术总结，我这怎么全是个人感受呢？

字符串操作题目，我自己是把情况分成了两种，如果输入的数字*2还小于等于字符串的长度，这种比较简单，从前往后比较即可，有多少个不同，result就加多少。

复杂的在后一种，比方说

ABCDAB

这种比较是

ABCD

与CDAB比较

实际上就是字符串中的

0位与2位

1位与3位

2位与4位

3位与5位

比较。

之后的想法是把0 2 4 这样的分成一组，1 3 5这样的分成一组，因为这些的值都要相等，比如0 2 4位分别是A C A，只需把2中的C变为A就行，实际上就是在这个组中要想相等就要少数服从多数，所以对于每组来说，求出每组出线最多的元素的次数，总的元素数-最多的次数，意思就是让其他组员屈服，都等于我的值。

代码：

#include <iostream>

#include <string>

#include <cstring>

#include <vector>

#include <algorithm>

#include <iterator>

using namespace std;

string test;

int fenge;

int R(vector<char> a)

{

	int start=a.size();

	int count;

	int b[27];

	memset(b,0,sizeof(b));

	int max=0;

	for(count=0;count<start;count++)

	{

		 b[a[count]-'A']++;

		 if( b[a[count]-'A']>max)

			 max=b[a[count]-'A'];

	}

	return start-max;

}

void jiandan()

{

	int start = test.length()-fenge;

	int count;

	int result=0;

	for(count=0;count<fenge;count++,start++)//找最多元素的出现的次数

	{

		if(test[count]!=test[start])

		{

			result++;

		}

	}

	cout<<result<<endl;

}

void fuza()

{

	int start=test.length()-fenge;

	int len=test.length();

	int fenshu=len-fenge;

	int count;

	vector<char> a;

	int result=0;

	for(count=0;count<fenshu;count++)

	{

		int temp = count;

		while(temp<len)//分组，一组中的元素要统一相等

		{

			a.push_back(test[temp]);

			temp=temp+fenshu;

		}

		result+=R(a);

		a.clear();

	}

	cout<<result<<endl;

}

int main()

{

	int count;

	cin>>count;

	while(count--)

	{

		cin>>test;

		cin>>fenge;

		if(test.length()>=2*fenge)

		{

			jiandan();

		}

		else

		{

			fuza();

		}

	}

	return 0;

}