JDFZOJ1108 第二饭堂

2014.12.19 14:52 Fri| 10 visits oi_2015| 2015_刷题日常| Text

可能是翻译的题吧,,题意各种读不懂……

Problem

Description

由于一饭班长表示各种鸭梨,美丽的纪中决定历史性地启用第二饭堂。

而部分领导觉得,二饭依山傍水,环境优美,未免有不和谐的事情(你懂的)发生,决定到二饭巡视同学们用餐时的就座情况。

为了应付这一情况,同学们决定联合起来“布阵”。

方便起见,同学们已经把座位情况抽象成一个长度为n的仅含数字及字母的字符串,他们想请你帮忙算算这个字符串的和谐程度。

已知一个字符串被称为k-回文串的充要条件是它自身是回文串,并且它长为⌊n/2⌋(下取整)的前缀和后缀是(k-1)-回文串。根据定义,任意字符串(包括空串)都是0-回文串。

一个字符串的回文度数就是这个字符串的k的最大值。

而对于一个给定的字符串,它的和谐程度就是其所有前缀的回文度数之和。

你的任务就是算出这个和谐程度具体是多少。

Input

一行一个仅包含数字和字母的字符串。

Output

一行一个整数表示这个字符串的和谐高度。

Sample Input

abacaba

Sample Output

6

HINT

对于30%的数据字符串长度不超过1000

对于70%的数据字符串长度不超过100000

对于100%的数据字符串长度不超过5000000

Solution

首先求出原串的每一个前缀字符串是否是回文串,之后一遍 $\mathcal O(n)$ 的DP即可求出答案。若使用Manacher算法求回文字串,需要注意各种边界各种讨厌的约束条件各种XX……

看到pengzhou的代码,为什么这么想哭……T^T

Code

Manacher算法

#include <bits/stdc++.h>
using namespace std;
#define N 5000010

char s[N*2],str[N];
int p[N*2],head[N],f[N];

int manacher(char str[],int len)
{
    s[0]='$'; s[1]='#';
    for(int i=0;i<len;i++)
        s[i*2+2]=str[i], s[i*2+3]='#';
    len=len*2+2;
    int id=0,maxp=0,re=0;
    for(int i=1;i<=len;i++)
    {
        if(maxp>i) p[i]=min(p[id*2-i],maxp-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]]) p[i]++;
        if(i+p[i]>maxp) maxp=i+p[i], id=i;
        re=max(re,p[i]);
    }
    return re-1;
}

int main()
{
    scanf("%s",str);
    int n=strlen(str);
    manacher(str,n);
    memset(head,0x3f,sizeof head);
    for(int i=2;i<=n*2+2;i++)
        head[(i+p[i]-4)/2]=min(head[(i+p[i]-4)/2],(i-p[i])/2);
    unsigned long long ans=0;
    for(int i=0;i<n;i++)
        if(!head[i])
            f[i+1]=f[(i+1)>>1]+1, ans+=f[i+1];
    cout<<ans<<endl;
    return 0;
}

Hash

#include <bits/stdc++.h>
using namespace std;
#define MAXN 5000001
#define seed 131
typedef unsigned long long ull;

int f[MAXN];
char s[MAXN];

int main()
{
    scanf("%s", s);
    int ilen = strlen(s);
    ull l = 0, r = 0, e = 1, ret = 0 ;
    for(int i = 0; i < ilen; i++)
    {
        l = l * seed + s[i];
        r = s[i] * e + r;
        e *= seed;
        if(l == r)
        {
            f[i+1] = f[(i+1)>>1] + 1;
            ret += f[i+1];
        }
        cout<<f[i+1]<<endl;
    }
    printf("%llu\n", ret);
    return 0;
}