HDU - 6264 Super-palindrome 【思维】

题目

You are given a string that is consisted of lowercase English alphabet. You are supposed to change it into a super-palindrome string in minimum steps. You can change one character in string to another letter per step. A string is called a super-palindrome string if all its substrings with an odd length are palindrome strings. That is, for a string s, if its substring si···j satisfies j | i + 1 is odd then si+k = sj| k for k = 0, 1, · · · , j | i + 1. Input The first line contains an integer T (1 ≤ T ≤ 100) representing the number of test cases. For each test case, the only line contains a string, which consists of only lowercase letters. It is guaranteed that the length of string satisfies 1 ≤ |s| ≤ 100. Output For each test case, print one line with an integer refers to the minimum steps to take

输入 3 ncncn aaaaba aaaabb 输出 0 1 2

题意：t组输入，每次输入一个字符串，问在这个字符串中想让j-i+1=奇数的所有位置字母相等最少进行几次操作，每次操作可以把把串中的一个字母改变

思路：符合上述位置要求的下标只能有两种序列，1,3，5,7，9…；2,4，6,8，10… 下标从零开始的话就是0，2,4，6,8，10…；1,3，5,7，9…让操作次数相等那我们肯定要不操作在符合位置上某种最多的字母，剩下的都要操作，总长度减去两种序列上两种最多的两种字母的出现次数即为所求

AC code

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<sstream> #include<queue> #include<stack> using namespace std; char a[120]; int b[250],c[250]; void solve() { int k=strlen(a); int max1=0,max2=0; memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); for(int i=0;i<k;i++)//求两种序列上出现次数最多的两种字母 if(i%2==0) { b[a[i]]++; max1=max(max1,b[a[i]]); } else { c[a[i]]++; max2=max(max2,c[a[i]]); } int s=k-max1-max2;//最小操作数 printf("%d\n",s); } int main() { ios::sync_with_stdio(0); int t; cin>>t; while(t--) { cin>>a; solve(); } }