萌新真的刚学OI

回复帖子

@月挣零_yzl 2019-03-22 20:51 回复

为什么WA0啊。

请自行忽略调试语句

#include<bits/stdc++.h>
using namespace std;
char s[2000001];
char ss[2000001];
int n;
void change(){
    s[0]=s[1]='#';
    for(int i=0;i<n;++i){
        s[i*2+2]=ss[i];
        s[i*2+3]='#';
    } 
    n=n*2+2;
    s[n]='\0';  
}
int hw[2000001];
void manacher(){
    int mid=0,mr=0;
    for(int i=1;i<n;++i){
        if(i<mr)hw[i]=min(hw[mid*2-i],mr-i);
        else hw[i]=1;
        while(s[i-hw[i]]==s[i+hw[i]])hw[i]++;
        if(mr<i+hw[i])mid=i,mr=i+hw[i];
    }
}
int ll[2000001];
int rr[2000001];
int main(){
    scanf("%s",ss);
    n=strlen(ss);
    change();
    manacher();
    for(int i=0;i<n;++i)putchar(s[i]);
    putchar('\n');
    for(int i=0;i<n;++i)cout<<hw[i]<<endl;
    for(int i=1;i<n;++i){
        ll[i+hw[i]-1]=max(ll[i+hw[i]-1],hw[i]-1);
        rr[i-hw[i]+1]=max(rr[i-hw[i]+1],hw[i]-1);
    }
    //for(int i=1;i<=n;++i)cout<<ll[i]<<endl;
    //for(int i=1;i<=n;++i)cout<<rr[i]<<endl;
    for(int i=1;i<n;i+=2){
        rr[i]=max(rr[i],rr[i+2]-2);
    }
    for(int i=n-1;i>0;i-=2){
        ll[i]=max(ll[i],ll[i-2]+2);
    }
    int ans=0;
    int loc;
    for(int i=3;i<n-2;i+=2){
        cout<<i<<endl;
        if(ll[i]+rr[i]>ans&&ll[i]&&rr[i]){
            //printf("%d\n",ans);
            ans=ll[i]+rr[i];
            loc=i;
        }
    }
    printf("%d %d %d %d\n",loc,ll[loc],rr[loc],ans);
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。