暑假集训Day3 J(lcm系列问题)
2022/7/10 23:55:26
本文主要是介绍暑假集训Day3 J(lcm系列问题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
本质上还是lcm问题,我们设f[i][j]为到s串的第i位(第i位必选),t串的第j位,符合条件的个数,
***注意这里第i位是必选的***,
这样状态统计的时候就不会混,最后ans就f[i][m]求个和就行,注意到由于t串是多个字符的,所以在求f[i][1]和f[i][j]的时候还是有点差别的。
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int MAX=1e5+5; 5 LL n,m,now1,now2,ans; 6 char s[MAX],t[105]; 7 LL f[MAX][105],g[MAX][105]; 8 int main(){ 9 // freopen ("j.in","r",stdin); 10 // freopen ("j.out","w",stdout); 11 int i,j; 12 scanf("%s%s",s+1,t+1); 13 n=strlen(s+1); 14 m=strlen(t+1); 15 memset(f,0,sizeof(f)); 16 memset(g,0,sizeof(g)); 17 f[0][0]=0; 18 for (i=1;i<=n;i++) f[i][0]=f[i-1][0]+1; 19 for (i=1;i<=n;i++){ 20 for (j=1;j<=m;j++){ 21 if (s[i]==t[j]){ 22 if (j==1) 23 f[i][j]+=f[i-1][j-1]+1; 24 else f[i][j]+=f[i-1][j-1]; 25 } 26 else f[i][j]+=f[i-1][j]; 27 } 28 ans+=f[i][m]; 29 } 30 printf("%lld",ans); 31 return 0; 32 }
这篇关于暑假集训Day3 J(lcm系列问题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升