【BZOJ-3790】神奇项链 Manacher + 树状数组(奇葩) + DP

2022-12-24 10:51:46

3790: 神奇项链

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 304 Solved: 150
[Submit][Status][Discuss]

Description

母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小 H 购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来，可以生成串abaaca或 abaca。现在给出目标项链的样式，询问你需要使用第二个机器多少次才能生成这个特殊的项链。

Input

输入数据有多行，每行一个字符串，表示目标项链的样式。

Output

多行，每行一个答案表示最少需要使用第二个机器的次数。

Sample Input

abcdcba
abacada
abcdef

Sample Output

0
2
5

HINT

每个测试数据，输入不超过 5行

每行的字符串长度小于等于 50000

Source

Solution

用来当Manacher模板题..

Manacher算法,一种线性求解最长回文串的算法,简单好写,也好懂,详细见这里: 折越

这道题就是说,转换为多个回文串结合成一个新串,那么对目标串Manacher,对得到的回文串当做一条线段

那么这题转为"线段覆盖"CodeVS上某题,贪心或者DP搞搞就可以了,这里利用树状数组优化一下

这里的树状数组非常神奇,以前只知道树状数组能维护和,没想到可以维护后缀,做法和平常的正好相反

Code

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

#define maxn 50010<<1

int n,len,mx,id,p[maxn],cnt;

char S[maxn>>],s[maxn];

struct TreeNode

{

    int a[maxn];

    void init() {memset(a,,sizeof(a));}

    int lowbit(int x) {return x&(-x);}

    int Query(int loc)

        {

            if (!loc) return ;

            int x=0x7fffffff;

            for (int i=loc; i<=n; i+=lowbit(i))

                x=min(x,a[i]);

            return x;

        }

    void Change(int loc,int D)

        {

            for (int i=loc; i; i-=lowbit(i))

                a[i]=min(a[i],D);

        }

}Tree;

void PreWork()

{

    cnt=; mx=; id=;

    Tree.init(); memset(p,,sizeof(p));

    n=strlen(S+); len=n<<|;

    s[]='$'; s[]='#'; s[len+]='%';

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

        s[i<<]=S[i],s[i<<|]='#';

}

struct HWCNode

{

    int l,r;

    bool operator < (const HWCNode & A) const

        {return r<A.r;}

}Line[maxn];

void Manacher()

{

    PreWork();

    for (int i=; i<=len; i++)

        {

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

                else p[i]=;

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

            int x=(i-p[i])/+,y=(i+p[i])/-;

            if (x<=y) Line[++cnt].l=x,Line[cnt].r=y;

            if (p[i]+i>mx) mx=p[i]+i,id=i;

        }

}

int DP()

{

    int ans=0x7fffffff;

    sort(Line+,Line+cnt+);

    for (int i=; i<=cnt; i++)

        {

            int D=Tree.Query(Line[i].l-)+;

            Tree.Change(Line[i].r,D);

            if (Line[i].r==n) ans=min(ans,D);

        }

    return ans-;

}

int main()

{

    while (scanf("%s",S+)!=EOF)

        Manacher(),printf("%d\n",DP());

    return ;

}

码农公寓