【LOJ 3049】「十二省联考 2019」字符串问题
这个D1T2绝对有毒。。。
首先我们构造一把反串的后缀自动机。
然后我们就需要找到每一个子串在SAM上的节点。
这个可以通过扫描线+树上倍增处理。
首先我们把所有的子串按照左端点排序，
然后从右往左扫描，在扫到\(i\)的时候：
我们取到\([i,n]\)的子串代表的节点，
那么所有的\([i,j]\)的子串都是这个节点在反串中的后缀！
所以所有的\([i,j]\)的子串对应的节点都是\([i,n]\)在\(parent\)树上的祖先。
那么就可以记\(f[i][j]\)为从\(i\)向上走\(2^j\)次\(suffix\) \(link\)得到的节点。
然后倍增出每一个\([i,j]\)的子串对应的节点就好了。
但这样会导致一些不同的子串对应到了同一个节点\(i\)，
我们假设\(i\)表示的子串们存在\(v_i\)中。
那么我们考虑构图。
首先我们把所有\(v_i\)按照长度从小到大排序，小的就是大的前缀
（根据后缀自动机节点的定义，以及构的是反串的SAM）
那么我们就可以把所有的B类向后面的所有A类连边。
但是这样的边数就是平方级的，所以要改一下：
所有的B类向下一个B类连边，以及向所有的下一个B类之前的A类连边。
还需要为每一个SAM上的节点向所有第一个B类之前的A类连边。
这样就可以做到同一个SAM上的节点内的前缀关系。
那么看不同节点的前缀关系怎么求。
这样就可以很自然地想到\(suffix\) \(link\)。
把所有节点表示的最后一个B类向所有\(link\)指向它的节点连边。
因为这样可以从所有节点的所有B类走到另外所有节点的A类。
那么最后把控制关系连下边就可以直接\(dag\)上\(dp\)了。
如果存在环则答案必须是\(-1\)。因为环必须是包含A类串的。
dxm
把每个SAM上的节点拆成\(in_i\)和\(out_i\)两个，
然后从\(in\)到\(out\)连边，
并且从\(out\)向所有\(link\)指向它的\(in\)连边。
我们现在考虑怎么把节点内部的A和B处理好。
我们肯定要从所有的B连向所有的A，而不能从A跑到另一个能计入答案的A，
所以我们把A分成\(in\)和\(out\)，
只有\(out\)是计入答案的，
那么我们对于同一个SAM上的节点这样连边：
- 从每个A的\(in\)连到\(out\)，并从\(out\)向所有支配的B连边。
- 从每个B，向长度大于等于它的第一个A的\(in\)连边，还要向该节点的\(out\)连边（要不然出不去
- 从这个节点的\(in\)向所有的A的\(out\)连边。
这样想十分的自然。
xyx
首先通过SAM上倍增求出每个子串的节点，
然后看怎么建图：
首先我们把每个SAM中的节点的\(link\)连到自己，
并且按照长度把这个节点对应的所有的子串排序，
每个B连向下一个B，同时连向所有下一个B之前的A。
再把每个A连向所有支配的B即可。
再跑个dp就行了。
wyj
类似xyx，
但是他是把同一个SAM上节点的A串和B串分开考虑了，
导致需要对于每一个B串二分出长度大于等于它的第一个A。
复杂度就多了一个\(log\)。
hhr
类似xyx。（一模一样？
csl
首先构造SA。然后我们把每一个A串拎出来，
构建一棵树，其包含了所有的子串，并且如果\(u\)到\(v\)有一条边，则要满足\(u\)是\(v\)的前缀。
但这棵树的节点数太多了，我们只需要包含A的，就引出了新的概念——虚树。
（吐槽：这玩意折腾死我了。。。
所谓虚树，是在树上找一个不连通的块，使得：
其包含所有的A串和所有A串两两的LCA们。
这就要求我们在线性时间内求出A串两两的LCA。
注意到两串的LCA就是他们的LCP，那么我们这样做：
先把所有的A串按照字典序排（其实就是按照他们在原树上的\(dfn\)
然后把连续两个A串的LCP加进去也作为A串
这个是一个结论一样的东西？？？可能就是最后用到的LCA们最多就是这里的吧。（删掉
emmm其实这\(^{TM}\)就是虚树的基本操作啊。。。
再用单调栈存现在的“有用”的点，
扫一遍排序过后的A串，每次一直弹栈直到栈顶是当前节点的祖先（当前节点的前缀
那么就可以确定连这条边。
Ah...怎么这么难啊
再把所有的B连到自己所属的节点就好辣
yjz
首先构造SA，然后每一个子串可以用\([l,r]\)来一一表示，代表这个子串在排名\([l,r]\)的前缀中出现。
这样就可以按照字典序把A串都排好（所属后缀的\(rank\)，长度）
那么B串是其前缀的A串们肯定是连续的。
感性理解一下：假设连续两个A串有一个\(lcp\)，那一段A串的\(lcp\)就是中间两两的\(lcp\)的\(min\)。
所以假如现在我们的某个B串是\(A_i\)的前缀，那么
那么我们就要从B串的一个点连向A串的一个区间
所以线段树优化建图（orz
再跑个\(dp\)就。。行了？？？
总结一下这题就是各种奇怪操作优化建图？？？
最新文章
- Bay Trail平板安装Ubuntu ThinkPad 8（20BNA00RCD）
- java开发常用工具
- webpack入坑之旅（四）扬帆起航
- 编辑一个.bat文件来启动一个.erl的程序？
- Visual Studio调试
- Linux kernel perf_swevent_init Local root Exploit
- python解无忧公主的数学时间编程题001.py
- OD调试4--绕过nag窗口
- ASP.NET和JSP相似方法总结（持续中。。）
- javascript常见错误
- SonarQube代码质量管理平台安装与使用--转载
- poj 2305（指定进制，大数取模）
- GMap.Net
- SharePoint 2016 文档库的新功能简介
- CentOS_5.6下使用cmake编译MySQL_5.5.11
- Windows数据库编程接口简介
- hihoCoder #1038 : 01背包(板子题)
- Dede 删除文档同时文章中的图片的方法
- mysql导入导出数据
- SDOI2017 R1做题笔记