hdu4513吉哥系列故事——完美队形II 马拉车

题目传送门

题意：求最长回文串长度，要求回文串左边是非下降。

思路一：

　　先把连续的回文串，满足先上升再下降的序列处理出来，再对这部分序列做马拉车模板就可以了。

　　需要注意的是，由于他要的是非下降的序列，所以要注意等于的情况。

　　还需要注意的是，写马拉车的板子习惯用的是char。。但是char的上限是255,'0'+250会爆char。因为这个wa了好几天也没想出bug是什么。

思路二：

　　对马拉车算法进行修改，只要在判断回文的时候加入递增这个条件即可。

两个思路都实现了一遍。

#include<bits/stdc++.h>

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int maxn=;

int s[maxn<<],ne[maxn<<];

int p[maxn<<],mx,maxx,n,T,a[maxn<<],b[maxn],cnt;

int init(int b[],int len){

    int j=;

    ne[]='$',ne[]='#';

    for(int i=;i<=len;i++)

    {

        ne[j++]=(''+b[i]);

        ne[j++]='#';

    }

    ne[j]='\0';

    return j;

}

void Manacher(int b[],int len)

{

    if(len==)return;

    len=init(b,len);

    int id,ma=;

    for(int i=;i<len;i++)

    {

        if(i<ma){

            p[i]=min(p[*id-i],ma-i);

        }else p[i]=;

        while(ne[i-p[i]]==ne[i+p[i]])p[i]++;

        maxx=max(maxx,p[i]);

        if(i+p[i]>ma){

            ma=i+p[i];

            id=i;

        }

    }

}

int main(){

//    printf("%d %d %d\n",'#','$','\0');

    cin>>T;

    while(T--)

    {

        cin>>n;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

        }

        cnt=,maxx=;

        int flag=;

        for(int i=;i<=n;i++)

        {

            if(a[i]>=a[i-]&&flag==){

                b[++cnt]=a[i];

            }else if(a[i]<=a[i-]){

                flag=;

                b[++cnt]=a[i];

            }else{

                Manacher(b,cnt);

                cnt=flag=;

                int j=i-;

                while(a[j]<=a[j+]){

                    if(j==)break;

                    b[++cnt]=a[j];

                    j--;

                }

                b[++cnt]=a[i];

            }

        }

        Manacher(b,cnt);

        printf("%d\n",maxx-);

    }

}

#include<bits/stdc++.h>

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int maxn=;

int s[maxn<<],ne[maxn<<];

int p[maxn<<],mx,maxx,n,T,a[maxn<<],b[maxn<<],cnt;

int init(){

    int j=;

    ne[]=-;

    ne[]=;

    for(int i=;i<=n;i++)

    {

        ne[j++]=a[i];

        ne[j++]=;

    }

    ne[j]=-;

    //printf("j:%d  n:%d\n",j,n);

    return j;

}

int Manacher(){

    int len=init();

    int id,ma=,mx=;

    //printf("len:%d\n",len);

    for(int i=;i<len;i++)

    {

        if(i<ma){

            p[i]=min(p[*id-i],ma-i);

        }else p[i]=;

        int k=ne[i];

        while(ne[i-p[i]]==ne[i+p[i]]&&(ne[i-p[i]]==||ne[i-p[i]]<=k)){

            if(ne[i-p[i]]!=)k=ne[i-p[i]];

            p[i]++;

        }

        if(i+p[i]>ma){

            ma=i+p[i];

            id=i;

        }

        mx=max(mx,p[i]);

    //    printf("i:%d  mx:%d\n",i,mx);

    }

    return mx-;

}

int main(){

    cin>>T;

    while(T--)

    {

        cin>>n;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

        }

        maxx=Manacher();

        cout<<maxx<<endl;

    }

}