HDU 5371 （2015多校联合训练赛第七场1003）Hotaru's problem(manacher+二分/枚举)

题意：

定义一个序列为N序列：这个序列按分作三部分，第一部分与第三部分同样，第一部分与第二部分对称。

如今给你一个长为n（n<10^5）的序列，求出该序列中N序列的最大长度。

思路：

来自官方题解：

/*

* @author FreeWifi_novicer

* language : C++/C

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<string>

#include<map>

#include<set>

#include<vector>

#include<queue>

using namespace std;

#define clr( x , y ) memset(x,y,sizeof(x))

#define cls( x ) memset(x,0,sizeof(x))

#define mp make_pair

#define pb push_back

typedef long long lint;

typedef long long ll;

typedef long long LL;

const int maxn = 100000 + 5;

int p[2*maxn];

int s[maxn];

int s1[2*maxn];

int n;

void init(){

    cls(s1);

    s1[0] = -1;

    s1[1] = -2;

    int k = 2;

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

        s1[k++] = s[i];

        s1[k++] = -2;

    }

}

void manacher(){

    int mx = 0 , id = 0;

    p[0] = 0;

    for(int i = 0 ; i < 2*n+1 ; i++){

        if(mx > i) p[i] = min(p[2*id-i] , mx-i);

        else p[i] = 1;

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

        if(mx < p[i]+i){

            mx = p[i] + i;

            id = i;

        }

    }

}

int solve(){

    int ans = 0;

    for(int i = 1; i < n*2 + 1 ; i += 2)

        if((p[i] - 1) / 2 > ans){

            for(int j = i + p[i] - 1 ; ; j -= 2){

                if(p[j] >= j-i){

                    ans = (j-i) / 2;

                    break;

                }

                if((j-i)/2 <= ans)  break;

            }

        }

    return 3*ans;

}

int main(){

  //freopen("input.txt","r",stdin);

    int t; cin >> t ; int kase = 1;

    while(t--){

        cls(s);cls(p);cls(s1);

        cin >> n;

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

             scanf("%d",s+i);

        }

        init();

        manacher();

        printf("Case #%d: %d\n",kase++,solve());

    }

    return 0;

}