2017中国大学生程序设计竞赛-杭州站 Problem A. Super-palindrome（贪心）

题意分析:

改变最少的字符，使字符串的每一个长度为奇数的子串都为回文串

解题思路：

如果想让任意奇数的子串为回文串，必须要让奇数位和偶数位上的所有字符相等，所以统计一下奇数位和偶数位上最多的字符，剩下的是要改变的。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 120
using namespace std;
char str[N];
int odd[N], even[N];
int main()
{
	int t, maxi, sum, len;
	scanf("%d", &t);
	while(t--)
	{
		memset(even, 0, sizeof(even));
		memset(odd, 0, sizeof(odd));
		scanf("%s", str);
		len=strlen(str);
		for(int i=0; i<len; i++)
		{
			if(i%2==1)
				even[str[i]-'a']++;
			else
				odd[str[i]-'a']++;	
		}
		maxi=0;
		sum=0;
		for(int i=0; i<26; i++)
			maxi=max(maxi, odd[i]);
		sum+=maxi;
		maxi=0;
		for(int i=0; i<26; i++)
			maxi=max(maxi, even[i]);
		sum+=maxi;
		printf("%d
", len-sum);
	}
	return 0;
}