HDU4513:完美队形II(Manacher)

Description

Input

Output

Sample Input

 

Sample Output

 

Solution

才发现我之前不会证$Manacher$复杂度……QAQ

题意是求最长向心非递减回文串。在$Manacher$函数向两边扩展的时候特判一下就好了。

┑(￣Д ￣)┍复杂度是对的啊……因为$Manacher$的时间复杂度证明和向两边扩的次数有关。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (200009)

 using namespace std;

 int T,n,x,tot,s[N],len[N];

 void Manacher()

 {

     int x,ans=,mid=,maxn=;

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

     {

         if (i>maxn) x=;

         else x=min(maxn-i+,len[mid*-i]);

         while (s[i-x]==s[i+x] && s[i-x]<=s[i-x+]) ++x;

         len[i]=x;

         if (i+x->maxn) maxn=i+x-, mid=i;

         ans=max(ans,x-);

     }

     printf("%d\n",ans);

 }

 int main()

 {

     scanf("%d",&T);

     while (T--)

     {

         scanf("%d",&n);

         tot=; s[++tot]=1e9; s[++tot]=-;

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

             scanf("%d",&x), s[++tot]=x, s[++tot]=-;

         s[++tot]=1e9;

         Manacher();

     }

 }