「BZOJ3790」神奇项链

2014年12月11日6,2492

Description

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

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

Input

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

Output

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

Sample Input

abcdcba
abacada
abcdef

Sample Output

0
2
5

HINT

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

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

题解

追随zky巨神的脚步TAT

这题数据范围是10^5

以下来自http://blog.csdn.net/iamzky/article/details/41852799

首先manacher,计算出所有的极长回文子串,问题转化为给定一些线段,用最少线段可重叠的覆盖整个区间,BIT优化dp即可

按右端点排序,f[i]=min{f[j],seg[j].sec>=seg[i].fst-1}+1

或者贪心也可以吧TAT

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define inf 1000000000 
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,cnt;
int p[200005],t[100005];
char ch[100005],a[200005];
struct seg{
	int l,r;
}l[100005];
int query(int x)
{
	if(!x)return 0;
	int tmp=inf;
	for(int i=x;i<=n;i+=i&-i)tmp=min(t[i],tmp);
	return tmp;
}
void modify(int x,int val)
{
	for(int i=x;i;i-=i&-i)t[i]=min(t[i],val);
}
bool operator<(seg a,seg b)
{
	return a.r<b.r;
}
void add(int x,int y)
{
	x=x/2+1;y=y/2-1;
	if(x>y)return;
	l[++cnt]=(seg){x,y};
}
void manacher()
{
	m=2*n+1;
	for(int i=1;i<=n;i++)
	{
		a[i<<1]=ch[i];
		a[i<<1|1]='#';
	}
	a[0]='+';a[1]='#';a[m+1]='-';
	int mx=0,id;
	for(int i=1;i<=m;i++)
	{
		if(mx>i)p[i]=min(mx-i,p[2*id-i]);
		else p[i]=1;
		for(;a[i-p[i]]==a[i+p[i]];p[i]++);
		add(i-p[i],i+p[i]);
		if(p[i]+i>mx)mx=p[i]+i,id=i;
	}
}
int main()
{
	while(scanf("%s",ch+1)!=EOF)
	{
		cnt=0;
		n=strlen(ch+1);for(int i=1;i<=n;i++)t[i]=inf;
		manacher();
		sort(l+1,l+cnt+1);
		int ans=inf;
		for(int i=1;i<=cnt;i++)
		{
			int x=query(l[i].l-1)+1;
			modify(l[i].r,x);
			if(l[i].r==n)ans=min(ans,x);
		}
		printf("%d\n",ans-1);
	}
	return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#define ll long long

#define inf 1000000000

using namespace std;

inline int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,m,cnt;

int p[200005],t[100005];

char ch[100005],a[200005];

struct seg{

int l,r;

}l[100005];

int query(int x)

{

if(!x)return 0;

int tmp=inf;

for(int i=x;i<=n;i+=i&-i)tmp=min(t[i],tmp);

return tmp;

}

void modify(int x,int val)

{

for(int i=x;i;i-=i&-i)t[i]=min(t[i],val);

}

bool operator<(seg a,seg b)

{

return a.r<b.r;

}

void add(int x,int y)

{

x=x/2+1;y=y/2-1;

if(x>y)return;

l[++cnt]=(seg){x,y};

}

void manacher()

{

m=2*n+1;

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

{

a[i<<1]=ch[i];

a[i<<1|1]='#';

}

a[0]='+';a[1]='#';a[m+1]='-';

int mx=0,id;

for(int i=1;i<=m;i++)

{

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

else p[i]=1;

for(;a[i-p[i]]==a[i+p[i]];p[i]++);

add(i-p[i],i+p[i]);

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

}

int main()

{

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

{

cnt=0;

n=strlen(ch+1);for(int i=1;i<=n;i++)t[i]=inf;

manacher();

sort(l+1,l+cnt+1);

int ans=inf;

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

{

int x=query(l[i].l-1)+1;

modify(l[i].r,x);

if(l[i].r==n)ans=min(ans,x);

}

printf("%d\n",ans-1);

}

return 0;

}

« 「BZOJ2819」Nim 「codechefFNCS」Chef and Churu »

Crab_Dave

大佬大佬那个l数组应该开成200005不然会WA qwq

Crab_Dave

哦我好像说错了麻烦删评/kk

hzwer.com _ Home | http://hzwer.com

「BZOJ3790」神奇项链

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论