Super-palindrome

时间限制: 1 Sec  内存限制: 128 MB

提交: 486  解决: 166

[提交] [状态] [命题人:admin]

题目描述

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.

输入

The fi rst 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.

输出

For each test case, print one line with an integer refers to the minimum steps to take.

样例输入

复制样例数据

3
ncncn
aaaaba
aaaabb
​

样例输出

0
1
2

提示

For second test case aaaaba, just change letter b to a in one step.

题意：需要改几个字符能使一个字符串具有奇数长度的所有子串都是回文串

只有两种情况 1.全部是同一个字符，或者2.两个字符穿插起来

所以刚开始我用的贪心，按出现次序排了个序，取前两个字符来生成两个新字符串和原串比较，

看哪个差异最小的，然后WA掉惹=。=

无奈只好暴力，

刚看了别人的博客，我写的也过于沙雕了。

#include<iostream>
#include<cstdio>     //EOF,NULL
#include<cstring>    //memset
#include<cstdlib>    //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc
#include<cmath>           //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
#include<algorithm>  //fill,reverse,next_permutation,__gcd,
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<utility>
#include<iterator>
#include<iomanip>             //setw(set_min_width),setfill(char),setprecision(n),fixed,
#include<functional>
#include<map>
#include<set>
#include<limits.h>     //INT_MAX
#include<bitset> // bitset<?> n
using namespace std;

#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define fori(x) for(int i=0;i<x;i++)
#define forj(x) for(int j=0;j<x;j++)
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(y))
#define all(x) x.begin(),x.end()
#define readc(x) scanf("%c",&x)
#define read(x) scanf("%d",&x)
#define read2(x,y) scanf("%d%d",&x,&y)
#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define print(x) printf("%d\n",x)
#define lowbit(x) x&-x
#define lson(x) x<<1
#define rson(x) x<<1|1
#define pb push_back
#define mp make_pair
typedef pair<int,int> P;
typedef long long LL;
typedef long long ll;
const double eps=1e-8;
const double PI = acos(1.0);
const int INF = 0x3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int MAXN = 1e6+7;
const int maxm = 1;
const int maxn = 105;
const ll MOD = 998244353;
int T;
int n,m;
string s;
struct node {
  int sum ;
  char id ;
}cnt[maxn];
bool cmp(node a,node b){
  return a.sum > b.sum;
}
int main(){
  read(T);
  while(T--){
     memset(cnt,0);
     cin >> s;
     int len = s.length();
     int tot = 0;
     for(int i = 0; i < len ; i++){
       cnt[tot].sum++;
       cnt[tot++].id  = s[i];
     }
     sort(cnt,cnt+tot,cmp);
     int imin = inf;
     for(int i = 0; i < tot ; i++){
       for(int j = 0; j < tot ; j++) {
         int sub = 0;
         for(int k = 0 ;k < len; k++){
           if(s[k] != cnt[i].id ){
             sub++;
           }
         }
         imin = min(imin,sub);
         if(i == j) continue;
         sub = 0;
         for(int k = 0 ;k < len; k+= 2){
           if(s[k] != cnt[i].id ){
             sub++;
           }
           if(s[k+1] && s[k+1] != cnt[j].id){
             sub++;
           }
         }
         imin = min(imin,sub);
       }
     }
     cout <<  imin <<endl;
    //以下是我WA掉的代码请忽视
     //cout << cnt[0].id <<" " << cnt[1].id<< endl
    //  string str1,str2;
    //  for(int i = 0 ; i < len ; i ++){
    //     str1 +=  cnt[0].id;
    //  }
    //  //cout << str1 <<endl;
    //  for(int i = 0 ; i < len ;i += 2){
    //    str2 += cnt[0].id;
    //    str2 += cnt[1].id;
    //  }
    // // cout <<str2 <<endl;
    // int sub = 0;
    // for(int i = 0 ;i < len ;i++){
    //     if(s[i]!=str1[i]) sub ++;
    // }
    // int imin = sub;
    // sub = 0;
    // for(int i = 0 ;i < len ;i++){
    //     if(s[i]!=str2[i]) sub ++;
    // }
    // if(sub < imin) imin = sub ;
    // cout << imin <<endl;
  }
}