hdu 5371 Hotaru's problem (manacher)

Hotaru's problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3952    Accepted Submission(s): 1298

Problem Description

Hotaru Ichijou recently is addicated to math problems. Now she is playing with N-sequence.
Let's define N-sequence, which is composed with three parts and satisfied with the following condition:
1. the first part is the same as the thrid part,
2. the first part and the second part are symmetrical.
for example, the sequence 2,3,4,4,3,2,2,3,4 is a N-sequence, which the first part 2,3,4 is the same as the thrid part 2,3,4, the first part 2,3,4 and the second part 4,3,2 are symmetrical.

Give you n positive intergers, your task is to find the largest continuous sub-sequence, which is N-sequence.

 

Input

There are multiple test cases. The first line of input contains an integer T（T<=20）, indicating the number of test cases.

For each test case:

the first line of input contains a positive integer N（1<=N<=100000）, the length of a given sequence

the second line includes N non-negative integers ,each interger is no larger than 109 , descripting a sequence.

 

Output

Each case contains only one line. Each line should start with “Case #i: ”,with i implying the case number, followed by a integer, the largest length of N-sequence.

We guarantee that the sum of all answers is less than 800000.

 

Sample Input

1 10 2 3 4 4 3 2 2 3 4 4

 

Sample Output

Case #1: 9

 

Author

UESTC

 

Source

2015 Multi-University Training Contest 7 

题意：

定义了一个序列它分为三个部分，最左端和最右端是相同的，左端和中间的是回文，中间和右端又是回文。求这样的序列最长是多少。

思路：

a[i]>=2*x&&a[i+x]>=2*x，所以枚举ans从0到maxr[i]-1(i从3到N)。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=200005;
int N,a[maxn],b[maxn],maxr[maxn];
void init(int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        b[i*2+1]=-1;
        b[i*2+2]=a[i];
    }
    N=2*i+1;
    b[0]=-2,b[N]=b[N+1]=-1;
}
void manacher()
{
    int id,maxn=0;
    for(int i=1;i<=N;i++)
    {
        maxr[i]=i<maxn?min(maxn-i,maxr[2*id-i]):1;
        while(b[i+maxr[i]]==b[i-maxr[i]]) maxr[i]++;
        if(i+maxr[i]>maxn) maxn=maxr[i]+i,id=i;
    }
}
int main()
{
    int t,n,cas=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        init(n);
        manacher();
        int ans=0;
        for(int i=3;i<=N;i+=2)
        {
           for(int j=ans;j<=maxr[i]-1;j+=2)
           {
               if(maxr[i+j]-1>=j)
               {
                   ans=j;
               }
           }
        }
        printf("Case #%d: %d\n",cas++,ans/2*3);

    }
    return 0;
}