寒假集训1-2 string

给定长度为n的字符串S，每次可以删除一个非回文子串，问最少几次能删完。不能输出-1

题解

分类讨论：

1. 如果s不是回文串，则输出1.
2. 如果s是回文串，如果能把s划分为两个子串A=s[1..i],B=s[i+1..n]，使得A,B都不是回文串，则输出2，否则输出-1

抄一段闫神的题解（稍微修改了一点点，主体意思一样的）：

如果不能划分的话，如果A=B，那么s只会形如aaaaa或aaabaaa；如果A!=B，那么s只会形如abababa。这三种情况都是无解的。

回文串的判断用manacher即可。

/*
Author: CNYALI_LK
LANG: C++
PROG: string.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
    int cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
    putchar(end);
}
int n;
char s[102402];
void getstr(char *s){
    while(!isalpha(*(++s)=getchar())){--s;}
    while(isalpha(*(++s)=getchar()));
    *s=0;
}
#ifndef cnyali_lk
#define cnyali_lk
#endif
int p[204848],r,mid;
int notHW(int l,int r){
    --(l<<=1);
    --(r<<=1);
    int mid=(l+r)>>1;
    return mid-p[mid]>l;
}
char ss[204848];
void manacher(int n){
    for(int i=1;i<=n;++i)ss[(i-1)<<1|1]=s[i];
    ss[0]='!';
    ss[n+n]='?';
    mid=r=0;
    int m=(n<<1)-1;
    for(int i=1;i<=m;++i){
        if(i<=r){
            p[i]=min(p[mid-(i-mid)],(r-i));
        }
        else p[i]=0;
        while(ss[i-p[i]-1]==ss[i+p[i]+1])++p[i];
        if(chkmax(r,i+p[i]))mid=i;
    }
}
int main(){
#ifdef cnyali_lk
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
#endif
    int t;
    t=read();
    while(t){
        --t;
        n=read();
        getstr(s);
        manacher(n);
        int ans=-1;
        if(notHW(1,n))ans=1;
        else{
            for(int i=1;i<n;++i)if(notHW(1,i)&&notHW(i+1,n)){ans=2;break;}
        }
        printf("%d\n",ans);
        for(int i=0;i<=n+n;++i)ss[i]=p[i]=0;
    }
    return 0;
}