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

2023-10-19 10:40

本文主要是介绍CH 白色情人节2(⑤我心永恒-字符串序列个数统计),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

背景
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("%d\n%d\n",cnt,(F+f[len1][len2][len3]-1)%F);return 0;
}



这篇关于CH 白色情人节2(⑤我心永恒-字符串序列个数统计)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/239236

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中,我们都清楚统计信息对于优化器来说非常重要。一般情况下,我们会开启"自动更新

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字