尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands 题解
P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands 题解思路考虑映射将基因库的字符串SiS_iSi​映射成Si#SiS_i\#S_iSi​#Si​的形式对于询问P,QP,QP,Q映射成Q#PQ\#PQ#P的形式那么就相当于问每个询问串在基因库中出现的次数直接跑 AC 自动机多模匹配即可。代码#includebits/stdc.husingnamespacestd;typedeflonglongll;intn;intch[5000010][5],ed[5000010],fail[5000010],c[255],id;intip[100010];voidins(string s,intx){intp0;for(inti0;is.size();i){intjc[s[i]];if(!ch[p][j])ch[p][j]id;pch[p][j];}ip[x]p;}intq[4100010],l1,r;voidbuild(){for(inti0;i5;i)if(ch[0][i])q[r]ch[0][i];while(lr){intxq[l];for(inti0;i5;i){intych[x][i];if(!y)ych[fail[x]][i];elsefail[y]ch[fail[x]][i],q[r]y;}}}vectorintG[5000010];voidquery(string s){intp0;for(inti0;is.size();i){intjc[s[i]];pch[p][j];ed[p];}}voiddfs(intx){for(inty:G[x]){dfs(y);ed[x]ed[y];}}string s[100010];intmain(){ios::sync_with_stdio(0);cin.tie(0);c[A]0;c[G]1;c[U]2;c[C]3;c[#]4;intq;cinnq;for(inti1;in;i){cins[i];s[i]s[i]#s[i];//字符串映射}dfs(0);for(inti1;iq;i){string s,t;cinst;st#s;//字符串映射ins(s,i);}build();//建AC自动机for(inti1;iid;i)G[fail[i]].push_back(i);for(inti1;in;i)query(s[i]);//多模匹配dfs(0);for(inti1;iq;i){couted[ip[i]]\n;}return0;}
RELATED

相关推荐

Ever Gauzy 平台认证 UI 库 @gauzy/ui-auth 完整指南:组件、路由守卫与构建发布实战

Ever Gauzy 平台认证 UI 库 @gauzy/ui-auth 完整指南:组件、路由守卫与构建发布实战

后端前端企业应用MCP 服务 【免费下载链接】ever-gauzy Ever Gauzy™ - Open Business Management Platform (ERP/CRM/HRM/ATS/PM) - https://gauzy.co 项目地址: https://gitcode.com/GitHub_Trending/ev/ever-gauzy 点击查看 免费下载 gauzy/ui-auth 是 Ever Gau…

📅 2026/10/1 16:08:19
Symfony 服务别名 Markdown 描述格式详解:读懂 `debug:container` 的别名与定义输出

Symfony 服务别名 Markdown 描述格式详解:读懂 `debug:container` 的别名与定义输出

后端Web框架 【免费下载链接】symfony The Symfony PHP framework 项目地址: https://gitcode.com/GitHub_Trending/sy/symfony 点击查看 免费下载 导读 本指南以 Symfony FrameworkBundle 测试夹具中的 Markdown 描述快照(alias_with_definition_1.md…

📅 2026/10/1 16:08:19
调用B站WEB端与TV端API,Java源码需JDK 8+FFmpeg——BiliDownloader在命令行下载器的赛道里走出了“极客原教旨”路线

调用B站WEB端与TV端API,Java源码需JDK 8+FFmpeg——BiliDownloader在命令行下载器的赛道里走出了“极客原教旨”路线

今天这份资源照旧全部无偿分享,不设任何门槛。点击文章底部左下方的“阅读原文”,即可进入下载页面直接获取。跟着网课学东西的人大概都有同一个习惯:某一段讲得特别清楚,要倒回去看三四遍。在线看没问题,一旦把网页关…

📅 2026/10/1 16:08:19
MORE NEWS

更多资讯

📰

Java SSM与Flask混合架构社区管理系统开发与部署全解析

这篇项目标题确实很典型——带着源码、LW(通常是论文或文档)、调试文档、讲解视频这类资源包的关键词,就意味着读者大多是计算机专业的毕业生或者刚入行的开发者,目的很明确:要一个能跑、能写进简历、能应付答辩的完整…

📰

Ubuntu 22.04上VCS与Verdi安装踩坑记录:从依赖修补到波形闭环

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📰

MATLAB实现多微网电能互补与需求响应的双层优化模型

多微网这东西,圈子里聊得火热,但真正能把模型跑通、结果讲清楚的人不多。今天不绕弯子,我直接把近期复现的一个基于MATLAB的“考虑多微网电能互补与需求响应的微网双层优化模型”从头到尾拆开聊。这个模型解决的问题很实在:多个微…

📰

考虑多微网电能互补与需求响应的双层优化模型及MATLAB实现

多微网之间能不能像人一样“互通有无”?答案是能,而且这个方向在最近的微电网运行优化研究里已经成了标配动作。我上一轮接到“考虑多微网电能互补与需求响应的微网双层优化模型”的需求时,第一反应是:这不只是套一套双层优化框架…

📰

结构体字节对齐实战:从HardFault到总线Fault的排查与预防

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📰

I2C总线死锁实战:从模式状态机、时钟延展与九脉冲恢复全解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬