题解 CF7D 【Palindrome Degree】

2018-08-09 21:12:09


竟然1A了。。。发篇Manacher的题解。

先跑一遍Manacher,然后在构造出的那个字符串上跑DP。

拿样例解释一下:

构造出是# # a # b # a # c # a # b # a #。(从0开始编号)

然后Manacher出的f数组是0 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1。(从0开始编号)

设 $dp[i]$ 表示以 $i$ 为中心,第一个字母为开头的字符串的阶数。

先发现一个事实:

如果 $f[i]=i$ ,那么以 $i$ 为中心,第一个字母为开头的字符串是回文串。

比如说字符 $c$ ,它的 $i$ 是 $8$ , $f[i]=8$ 。所以 $abacabc$ 是回文串。

那么 $dp[8]=dp[4]+1$ 。

也就是说:

  • 如果 $f[i]=i$ ,那么 $dp[i]=dp[\frac{i}{2}]+1$
  • 否则, $dp[i]=0$

但是仍有问题: $aa$ 这种字符串会WA。

$aa$ 构造出是# # a # a #

那么我们要把 $dp[3]$ 搞成1,也就是要让 $dp[3]=dp[2]+1$ 。

所以处理后的状态转移方程应该是这样:

  • 如果 $f[i]=i$ ,那么 $dp[i]=dp[\lfloor\frac{i+1}{2}\rfloor]+1$
  • 否则, $dp[i]=0$

然后因为是中心,处理一半即可。

大力DP,答案为 $\sum_{i=3}^{\lfloor\frac{length}{2}\rfloor}dp[i]$

附上代码:

#include <bits/stdc++.h>
#define re register
using namespace std;

char a[5000010],s[10000010];
int f[10000010];
int n;

inline void change() {
    s[0]=s[1]='#';
    for (re int i=0;i<n;i++) s[(i<<1)+2]=a[i],s[(i<<1)+3]='#';
    n=n*2+2; s[n]='\0';
}

inline void manacher() {
    int MaxRight=0,mid;
    for (re int i=1;i<n;i++) {
        if (i<MaxRight) f[i]=min(f[(mid<<1)-i],f[mid]+mid-i);
        else f[i]=1;
        for (;s[i+f[i]]==s[i-f[i]];f[i]++) {
            if (f[i]+i>MaxRight) {
                MaxRight=f[i]+i;
                mid=i;
            }
        }
    }
}

int dp[5000010];

int main() {
    scanf("%s",a); n=strlen(a); int l=n;
    change(); manacher();

    int ans=1; dp[2]=1;
    for (re int i=3;i<=(n>>1);i++) {
        if (f[i]==i) dp[i]=dp[(i+1)>>1]+1;
        else dp[i]=0;
        ans+=dp[i];
    }

    printf("%d\n",ans);
    return 0;
}