hdu 4513 吉哥系列故事——完美队形II Manacher变形

传送门：吉哥系列故事——完美队形II

马拉车的简单变形，如果不懂Manacher算法请移步：Manacher算法讲解

AC CODE

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int MX = 1e5 + 5; int A[MX]; int ma[MX<<1]; int p[MX<<1]; void Manacher(int n) { int l = 0; ma[l++] = -2; ma[l++] = 0; for(int i=0;i<n;i++) { ma[l++] = A[i]; ma[l++] = 0; } ma[l] = -3;p[0] = 0; int mx = 0,id = 0; for(int i=0;i<=l;i++) { p[i] = mx>i ? min(p[2*id-i],mx-i) : 1; while(ma[i+p[i]] == ma[i-p[i]] && ma[i-p[i]]<=ma[i-p[i]+2]) p[i]++; if(i+p[i]>mx) { mx = i+p[i]; id = i; } } } int main() { int _,n;//freopen("in.txt","r",stdin); scanf("%d",&_); while(_--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&A[i]); Manacher(n); int ans = 0; for(int i=1;i<=2*n+1;i++) ans = max(ans,p[i]-1); printf("%d\n",ans); } return 0; }