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

相关文章

Pandas统计每行数据中的空值的方法示例

《Pandas统计每行数据中的空值的方法示例》处理缺失数据(NaN值)是一个非常常见的问题,本文主要介绍了Pandas统计每行数据中的空值的方法示例,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是空值?为什么要统计空值?准备工作创建示例数据统计每行空值数量进一步分析www.chinasem.cn处

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》:本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST(抽象语法树)、字符串操作... 目录前言解决方案方法一:使用正则表达式方法二:使用 Pyparsing方法三:使用 AST方法四:使用字

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》:本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析:String、StringBuilder与StringBuffer一、St

Mysql如何将数据按照年月分组的统计

《Mysql如何将数据按照年月分组的统计》:本文主要介绍Mysql如何将数据按照年月分组的统计方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql将数据按照年月分组的统计要的效果方案总结Mysql将数据按照年月分组的统计要的效果方案① 使用 DA

MySQL更新某个字段拼接固定字符串的实现

《MySQL更新某个字段拼接固定字符串的实现》在MySQL中,我们经常需要对数据库中的某个字段进行更新操作,本文就来介绍一下MySQL更新某个字段拼接固定字符串的实现,感兴趣的可以了解一下... 目录1. 查看字段当前值2. 更新字段拼接固定字符串3. 验证更新结果mysql更新某个字段拼接固定字符串 -

Java String字符串的常用使用方法

《JavaString字符串的常用使用方法》String是JDK提供的一个类,是引用类型,并不是基本的数据类型,String用于字符串操作,在之前学习c语言的时候,对于一些字符串,会初始化字符数组表... 目录一、什么是String二、如何定义一个String1. 用双引号定义2. 通过构造函数定义三、St

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

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

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