Tag Archives: 字符串DP

CH 白色情人节2(⑤我心永恒-字符串序列个数统计)

Posted on by

背景

You're here, there's nothing I fear,
and I know that my heart will go on.
We'll stay forever this way.
You are safe in my heart.
And my heart will go on and on.

描述

男主想要用三句话表达对女主的爱，男主要对这三句话进行一番锤炼，现在要找出三句话中永恒不变的事物，需要做的，就是计算出三份序列的最长公共子序列长度、公共子序列个数，其中个数对第201314个质数(2769433)取模。字符之间的匹配不区分大小写(即"a"与"A"视为相等)

输入格式

共三行，一行一个字母序列。

输出格式

第一行，三份序列的最长公共子序列长度。
第二行，三份序列的公共子序列个数对第201314个质数(2769433)取模得到的答案。

样例输入

INeedYou
IMissYou
ILoveYou

样例输出

4
15

数据范围与约定

对于100%的数据，序列仅含大小写字母，序列长度均leq 100。

样例解释

最长公共子序列是IYou，长度为4，公共子序列分别是I Y o u IY Io Iu Yo Yu ou IYo IYu Iou You IYou，共4+6+4+1 = 15个

来源

本题有个无节操版本……

这题是统计公共子序列个数+去重

正解用了容斥原理,并且允许空串。

F[I][J][K]=2F[I-1][J-1][K-1]-F[I'-1][J'-1][K'-1] I',J',K'为I,J,K,之前出现a[i],b[j],c[k]的位置（没有就不用减）

 假设之前已经去重，那么F[I][J][K]只需与F[I'-1][J'-1][K'-1]去重。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define F (2769433)
#define MAXN (100+10)
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<=n;i++)
int len1,len2,len3,f[MAXN][MAXN][MAXN],pre1[MAXN],pre2[MAXN],pre3[MAXN],s[500];
char a[MAXN],b[MAXN],c[MAXN];
void make_pre(char *a,int n,int *pre)
{
	memset(s,128,sizeof(s));
	memset(pre,0,sizeof(pre));
	For(i,n)
	{
		a[i]=tolower(a[i]);
		pre[i]=s[a[i]];
		s[a[i]]=i;
	}
}
int main()
{
	memset(f,0,sizeof(f));
	scanf("%s%s%s",a+1,b+1,c+1);a[0]=b[0]=c[0]=' ';
	len1=strlen(a)-1,len2=strlen(b)-1,len3=strlen(c)-1;
	make_pre(a,len1,pre1);
	make_pre(b,len2,pre2);
	make_pre(c,len3,pre3);
	int cnt=0;
	For(i,len1)
		For(j,len2)
			For(k,len3)
				if (a[i]==b[j]&&b[j]==c[k]) f[i][j][k]=f[i-1][j-1][k-1]+1;
				else f[i][j][k]=max(max(f[i-1][j][k],f[i][j-1][k]),f[i][j][k-1]);
	cnt=f[len1][len2][len3];
//	memset(f,0,sizeof(f));
	Rep(i,len1) Rep(j,len2) Rep(k,len3) f[i][j][k]=1;
	For(i,len1)
		For(j,len2)
			For(k,len3)
			{
				f[i][j][k]=0;
				if (a[i]==b[j]&&b[j]==c[k])
				{
					f[i][j][k]=(10*F+f[i-1][j-1][k-1]*2)%F;
					if (pre1[i]>0&&pre2[j]>0&&pre3[k]>0) f[i][j][k]=(F+f[i][j][k]-f[pre1[i]-1][pre2[j]-1][pre3[k]-1])%F;
				//	if (!pre1[i]||!pre2[j]||!pre3[k]) f[i][j][k]--;
				}
				else
				{
					f[i][j][k]=(10*F+f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1]-f[i-1][j-1][k]-f[i][j-1][k-1]-f[i-1][j][k-1]+f[i-1][j-1][k-1])%F;
				}
			}

	printf("%dn%dn",cnt,(F+f[len1][len2][len3]-1)%F);
	return 0;
}


回文子串对(扩展kmp-kmp与回文子串)

Posted on by

Problem 1 回文子串对(manacher.cpp/c/pas)

【题目描述】

给定一长度为n的小写字母串，求有多少对回文子串，它们的交集非空。

一对回文子串的交集非空：[a,b]、[c,d](a≠c或b≠d)为2个回文子串，且[a,b]∩[c,d]≠∅。

【输入格式】

第一行一个整数n表示串长。

第二行长度为n的小写字母串。

【输出格式】

输出一个整数表示答案，答案对1000000007取模。

【样例输入】

4

babb

【样例输出】

6

【数据范围】

对于30%的数据，n<=1000

另有10%的数据，串里仅含一种字母。

对于100%的数据，n<=2*10^6

 

找到最前面的max(r[j]+j),映射过去

设r[i]表示以i点为中心点的最长回文子串

则如图：



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define F (1000000007)
#define MAXN (2000000+10)
using namespace std;
long long r[MAXN],n,L[MAXN][2],R[MAXN][3];
char s[MAXN];
int main()
{
	freopen("manacher.in","r",stdin);
	freopen("manacher.out","w",stdout);
	scanf("%d%s",&n,s+1);
	memset(r,0,sizeof(r));
	memset(L,0,sizeof(L));
	memset(R,0,sizeof(R));
	int j=0;
	for (int i=1;i<=n;i++)
	{
		if (r[j]+j>i) r[i]=min(r[j-(i-j)],j+r[j]-i);
		while (i-r[i]>1&&i+r[i]<n&&s[i-r[i]-1]==s[i+r[i]+1]) r[i]++;
		if (r[i]+i>r[j]+j) j=i;
		L[i-r[i]][0]+=1;
		L[i+1][0]-=1;
		R[i][0]++;
		R[i+r[i]+1][0]--;
	}
//	for (int i=1;i<=n;i++) cout<<r[i]<<' ';cout<<endl;
	j=0;memset(r,0,sizeof(r));
	for (int i=1;i<n;i++)
	{
		if (r[j]+j>i) r[i]=min(r[j-(i-j)],j+r[j]-i);
		while (i-r[i]>0&&i+r[i]<=n&&s[i+1-r[i]-1]==s[i+r[i]+1]) r[i]++;
		if (r[i]+i>r[j]+j) j=i;
		L[i+1-r[i]][0]+=1;
		L[i+1][0]-=1;
		R[i+1][0]++;
		R[i+r[i]+1][0]--;
	}
/*
	for (int i=1;i<=n;i++) cout<<L[i][0]<<' ';cout<<endl;
	for (int i=1;i<=n;i++) cout<<R[i][0]<<' ';cout<<endl;
*/
	for (int i=1;i<=n;i++) L[i][1]=L[i][0]+L[i-1][1];
	for (int j=1;j<=2;j++)
		for (int i=1;i<=n;i++)
			R[i][j]=R[i-1][j]+R[i][j-1];
	long long ans=0;
	for (int i=1;i<=n;i++)
		ans=(ans+L[i][1]*R[i-1][2])%F;
	long long tot=0;
	if (R[n][2]%2) tot=(((R[n][2]-1)/2)%F)*((R[n][2])%F)%F;
	else tot=(((R[n][2])/2)%F)*((R[n][2]-1)%F)%F;
//	cout<<tot<<' '<<ans<<endl;

	cout<<((tot-ans+F)%F)<<endl;
	return 0;
}




两个子序列(？标识符)

Posted on by

Problem 1 两个子序列(twosub.pas/c/cpp)

【题目描述】

将给定的n个长度为M的01串序列{a1,a2…an} 分为两个子序列{b1,b2…bk}和{c1,c2…cm}，m+k=n,使|f(b1,b2…bk)|+|f(c1,c2…cm)|最小化。

f函数定义如下：

f(空序列)=空串
       f(s)=s
       f(s1,s2)=最小长度的有一个前缀等于s1并且有一个后缀等于s2的字符串。        f(a1,a2,…,an)=f(f(a1,a2,…,an-1),an)。

 

【输入格式】

第一行两个整数n。

接下来n行每行一个长度为M的01串，表示a1，a2...an。

 

【输出格式】

输出一个整数，表示答案。

 

【样例输入】

4
000
111
110
001

【样例输出】

8

【数据范围】

对于30%的数据，n<=20

对于60%的数据，n<=2000

对于100%的数据，1<=n<=200000，1<=M<=20

 

 这题要用后缀DP

f[i][j]表示非当前枚举点结尾的那个字符串结尾为i



#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cmath>
#include<iostream>
using namespace std;
#define MAXN (200000+10)
#define MAXM (20+10)
#define MAXSum (1<<20)
int n,m,f[MAXSum][MAXM],a[MAXN],bin[MAXM];
char s[MAXM];
int main()
{
	freopen("twosub.in","r",stdin);
	freopen("twosub.out","w",stdout);
	scanf("%d",&n);
	memset(f,128,sizeof(f));
	memset(a,0,sizeof(a));
	for (int i=1;i<=n;i++)
	{
		scanf("%s",s);
		m=strlen(s);
		for (int j=0;j<m;j++) a[i]=(a[i]<<1)+s[j]-48;
	}
	int tot=0;
	bin[0]=0;
	for (int i=1;i<=20;i++) bin[i]=(1<<i)-1;
	int ans=n*m;
	for (int i=2;i<=n;i++)
	{
		int k=m;
		while (k&&((bin[k]&a[i-1])!=a[i]>>(m-k)))
		{
		//	cout<<(bin[k]&a[i-1])<<' '<<a[i]<<m-k<<(a[i]>>(m-k))<<endl;
			k--;
		}
	//	cout<<k<<endl;
		ans-=k;
		int temp=0;
		for (int j=0;j<=m;j++) temp=max(temp,f[a[i]>>j][m-j]+m-j);
		for (int j=0;j<=m;j++) f[a[i-1]&bin[j]][j]=max(f[a[i-1]&bin[j]][j],temp-k);
	}
	int temp=0;
	for (int j=0;j<=m;j++)
		for (int i=0;i<=bin[j];i++) temp=max(temp,f[i][j]);
	cout<<ans-temp;
	return 0;
}