本文主要是介绍DTOJ4350. 「十二省联考 2019」字符串问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:
给一个长度为n的串S,给na个A类S的子串,nb个B类S的子串,由m中支配关系,表示一个A类串支配一个B类串,求最长的由A类串拼接而成的串,满足除最后一个外,每个A类串都存在一个被它支配的B类串,满足该B类串是该A类串下一个A类串的子串。若可以无限长则输出-1。
范围:所有数均<=2e5
题解:
考场:
没有图论思维,因为全世界都会的T1不会做而心态爆炸的我:对每个A类串向它能连向的A类串连边,判断是否有环,有则-1,没有则是一个DAG,DP跑最长路即可。但要怎么判断两个A类串之间是否有连边?还要枚举A所支配的B类串,再哈希判断,这样只有10分。
正解:
先考虑更优秀的暴力,若只在A类串中判断,则判断是否连边时的效率不高。发现一个A类串向另一个A类串连边的条件其实是借助了一个这个A类串支配的串,所以也将B类串作为一个点,A向其支配的B连边,B向是A的前缀的A连边,这样每次枚举B是否为每个A的前缀,O(N*N)就有40分了!
考虑上述算法的复杂度在于B向A连边,而这个条件是B是A的前缀,有什么和前缀有关的数据结构呢?将字符串翻转一下,就变成后缀了,所以考虑后缀自动机。将所有A,B对应到后缀自动机上的点(倍增求即可),B会是哪些串的前缀?显然是后缀树上它的子树的节点上的A!考虑如何用后缀树的结构优化建图,将后缀树的每个点连向它的儿子,这样每个点都有通往它子树的路径。但如何将A,B串和后缀树上的点建立关系?考虑对于在后缀树同一节点上的串,B也会对比它长的A有贡献,故对其长度从大到小排序,每个B都连向他前面的A,一直连到直到下一个B,下一个B也这样做,就可以保证一个节点内的连边关系。不同节点之间,对于前缀的关系,就把每个节点的第一个B连到所有直系儿子的最后一个B,这样保证所有长度小的B都对子树内长度大的A造成贡献,若一个节点内没有B,则新建一个B,反正不会影响权值(选B而不选A作为连接点是为了避免A的权值的影响)。对于支配关系,直接将对应的串相连即可。这样就完美地在O(N)的效率内完成建边了!
这篇关于DTOJ4350. 「十二省联考 2019」字符串问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!