脚本宝典收集整理的这篇文章主要介绍了[BalticOI 2020 Day2] 病毒，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题面

​ link

​ 题面直接看吧，这里补充一点，就是只有在序列中只含(0,1)才会被考虑，也就是那些长度无限长的病毒根本没有意义。

题解

​ 题目问最小不能被检测的病毒长度，而可以被检测(rightarrow)最小不能被检测的病毒长度为无限长。

​ 发现有多串的匹配问题（不能以(c)作为子串），直接考虑AC自动机表示状态，对于fail树祖先中有结束状态的节点都设为不可访问点。

​ 但是我们的一种基因可以有多种突变方式，而且字符的长度也很长，不能直接在只有(0,1)的最终字符串上转移。但这启发我们：任何一个基因其实完成的是AC自动机上状态的转移。

​ 比如 (0) ，可以让(xleftarrow tr[x][0])，而比如对于基因 (2) 存在一个突变表(2leftarrow 0;1;0)，其实也就是让(x)通过以下变换(xleftarrow tr[x][0],xleftarrow tr[x][1],xleftarrow tr[x][0])。所以我们可以设 (f_{i,s,t}) 表示通过第 (i) 个基因，让AC自动机上状态从(srightarrow t)且不经过不可到达点，所需要的最短长度。

​ 考虑维护这个转移。首先，任何基因肯定是通过突变表来变换的，所以我们可以枚举突变表。考虑(s)是怎么变到(t)的？一定是先经过第一个(b_1)，使用(f_{b_1,s,c_1})的代价到(c_1)，在使用(f_{b_1,c_1,c_2})的代价到(c_2)......最后使用(f_{b_l,c_l,t})的代价到(t)，我们需要维护这个过程的最小代价。所以我们又需要一个dp来维护这个最小值。

​ 枚举起点(s)设(g_{i,j})表示经过(i)个突变后的基因，当前AC自动机上的状态为(j)的最小代价。那么有转移(g_{i,j}=min_{k}{g_{i-1,k}+f_{b_i,k,j}})，最后再去更新(f_{a,s,t}=min g_{l,t})。

​ 这样我们对与一个突变表维护一次的复杂度为(O(n^3l))，(n) 为AC自动机的状态数。好像可以直接暴力扫 (G) 遍，每次再去更新一次所有突变表，复杂度为(O(G sum l n^3))，这里的 (l) 为原题中的 (k) 。

​ 但这个的正确性感觉无法保证，主要是突变表中包含本身的情况，一定会保证自己更新自己的取值不会作为其他点的最终答案吗？

​ 有个正确性可以保证的做法，但是我没有研究。。。

启发

• 这类(aleftarrow {b_1,b_2...,b_l})的转移都可以套用这种dp方法，即考虑一个数带来的状态的转移。
• AC自动机可以维护不能以某些串作为子串的dp状态。

脚本宝典总结

以上是脚本宝典为你收集整理的[BalticOI 2020 Day2] 病毒全部内容，希望文章能够帮你解决[BalticOI 2020 Day2] 病毒所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。