BZOJ3790神奇项链——manacher+贪心

不念不忘少年蓝@ 2022-01-05 15:09 270阅读 0赞

## 题目描述 ##

母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字

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

## 输入 ##

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

## 输出 ##

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

## 样例输入 ##

abcdcba  
abacada  
abcdef

## 样例输出 ##

0  
2  
5

## 提示 ##

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

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

将每个回文串看作一个线段，那么问题就变成至少多少个线段能将区间全部覆盖。用manacher求一下以每个位置为中心的最长回文串，将其视为一个线段然后按左端点排序贪心选线段即可。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<bitset>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    char s[100010];
    int len[100010];
    int n;
    int mx,num;
    struct miku
    {
    	int l,r;
    }a[100010];
    bool cmp(miku a,miku b)
    {
    	return a.l<b.l;
    }
    int main()
    {
    	while(scanf("%s",s+1)!=EOF)
    	{
    		n=strlen(s+1);
    		for(int i=n;i>=1;i--)
    		{
    			s[i<<1]=s[i];
    			s[i<<1|1]='&';
    		}
    		n=n<<1|1;
    		s[0]='%';
    		s[1]='&';
    		s[n+1]='^';
    		mx=0,num=0;
    		for(int i=1;i<=n;i++)
    		{
    			len[i]=mx>i?min(len[num*2-i],mx-i):1;
    			while(s[i+len[i]]==s[i-len[i]])
    			{
    				len[i]++;
    			}
    			if(mx<i+len[i])
    			{
    				mx=i+len[i];
    				num=i;
    			}
    		}
    		for(int i=1;i<=n;i++)
    		{
    			a[i].l=i-len[i]+1;
    			a[i].r=i+len[i]-1;
    		}
    		sort(a+1,a+1+n,cmp);
    		int r=0,ans=0,i=1;
    		while(i<=n)
    		{
    			int sum=0;
    			while(a[i].l-1<=r&&i<=n)
    			{
    				sum=max(sum,a[i].r);
    				i++;
    			}
    			ans++;
    			r=sum;
    			if(r==n)
    			{
    				break;
    			}
    		}
    		printf("%d\n",ans-1);
    	}
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10355961.html