BZOJ3790: 神奇项链【贪心+manacher】

3790: 神奇项链

【题目描述】

传送门

【题解】

处理出所有的回文串,然后就是一道区间覆盖问题,贪心就可以了。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=50005;
int n,Ans,p[MAXN<<1],q[MAXN<<1],lst,MAX;char s[MAXN<<1],ch[MAXN];
void maker(){
    for(int i=1,mx=0,id=0;i<=n;++i){
        if(mx>i) p[i]=min(p[2*id-i],mx-i);else p[i]=1;
        while(1<=i-p[i]&&i+p[i]<=n&&s[i-p[i]]==s[i+p[i]]) ++p[i];
        if(i+p[i]>mx) mx=i+p[i],id=i;
    }
}
int main(){
    freopen("necklace.in","r",stdin);
    freopen("necklace.out","w",stdout);
    while(~scanf("%s",ch)){
        int Len=strlen(ch);Ans=lst=MAX=0;
        memset(q,0,sizeof(q));
        for(int i=0;i<Len;i++) s[((i+1)<<1)]=ch[i],s[((i+1)<<1)-1]='#';
        s[(Len<<1)+1]='#',s[(Len<<1)+2]=0,n=strlen(s+1),maker();
        for(int i=1;i<=n;i++) q[i-p[i]+1]=max(q[i-p[i]+1],i+p[i]-1);
        for(int i=1;i<=n;i++){
            if(q[i]>MAX) MAX=q[i];
            if(i>lst) Ans++,lst=MAX,MAX=0;
        }
        printf("%d\n",Ans-1);
    }
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部