圆方树
圆方树能有效地把图论问题转换为树上问题,从而利用数据结构高效地维护信息。
考虑对一个无向图建出它的圆方树,这棵圆方树上的点分为两种:圆点与方点。
我们首先对于无向图的每一个点双连通分量新增一个方点,将该方点与连通分量中的每一个点相连,断开原图所有边。
比如该图:
建出其圆方树:
其中节点 \(8,9,10\) 为方点。
首先建出圆方树,那么答案就是两个节点之间的圆点个数。
建出圆方树之后,考虑固定 \(c\),考虑点对贡献。对于一个点,拆分为子树内的点相互产生的贡献和子树内与外的点产生的贡献,\(dfs\) 即可解决。
建出圆方树,首先考虑对于每一个方点维护与他相连的圆点的权值最小值,发现修改操作无法进行。
那么考虑对于每一个方点维护一个 \(\text{multiset}\),存储与其相连圆点的权值,每次修改圆点,暴力修改与其相连方点的 \(\text{multiset}\)。
发现可以被菊花图卡,然后我就不会做了。
原来可以对于每一个方点,只维护其儿子圆点的 \(\text{multiset}\),然后线段树求最小值,如果要旅行的两个点的 \(\text{LCA}\) 是方点,要额外考虑其父亲圆点的贡献。
UVA1464 Traffic Real Time Query System
建出圆方树,与 P4320 道路相遇 处理相同,唯一变化的是询问转换为边,则我们每次询问对于两条边 \(u[x],v[x],u[y],v[y]\) 中不属于同一条边的两个节点两两询问取 \(\max\) 即可。
模拟退火
模拟退火是爬山算法的升级版,爬山算法适用于处理单峰函数问题,而出现非单峰函数的题目时,爬山算法会陷入局部最优解。这时候使用模拟退火,能有概率避免陷入局部最优解的情况。
线段树优化建图
有一些图论问题的时间复杂度瓶颈在于连边,例如需要将区间 \([l_1,r_1]\) 与区间 \([l_2,r_2]\) 中的点相连,这时复杂度到达了 \(O(n^2)\),所以我们考虑优化建图这一过程来优化复杂度。
在针对区间问题,我们考虑用线段树这一解决区间问题的有力工具来优化建图,考虑建立两棵线段树表示出树与入树。
对于出树,考虑对于出树上的区间节点,对于它的左,右区间,向当前区间节点连边。
对于入树,对于当前的区间节点,向它的左,右区间连边。
然后我们分成 \(4\) 类讨论:
对于点向点连边,直接在出树与入树上找到对应的叶子节点连边。
对于区间向点连边,在出树上找到对应区间向对应叶子节点连边。
对于点向区间连边,找到对应叶子节点向入树上对应区间连边。
对于区间向区间连边,我们新增节点 \(node\),出树对应区间向 \(node\) 连边, \(node\) 向入树对应区间连边。
最后我们就达到了优化建图的目的。
AC 自动机
\(tr[i].end\) 为 \(1\) 时表示为该节点为串尾。
\(tr[i].sum\) 表示以该点为串尾的字符串数。
普通自动机
考虑对模式串建出自动机,在串尾打 tag ,在文本串上跑自动机,开一个栈维护当前位跑到自动机上的节点编号,一个栈维护剩余的字符,当跑到串尾时,弹出该串所有的字符,挂在自动机上的指针回退到该串入栈之前。
考虑将 \(t\) 拆成两半,枚举断点,设 \(t=t_1+t_2\),则只需要考虑模式串分别匹配 \(t_1\) 的后缀与 \(t_2\) 的前缀即可。
由于自动机的 fail 指针有着优秀的后缀性质,所以我们可以将模式串与文本串以正序和逆序分别建出两台自动机,这样前后缀的问题就解决了。
由于 fail 指针代表着当前字符串的后缀子串,所以我们在累加贡献的时候串的贡献要加上其后缀子串的贡献,这一步可以在求 fail 指针时求出来。
对 fail 树的操作 + DS 维护
考虑建出该字典图的 fail 树,考虑 fail 树的性质。由于串长不超过 \(20\), 在每一个节点维护一个状压集合 \(S\) 表示从根到该节点的所有串能匹配的长度,考虑边 \(u->v\),下传时显然有 \(S_v~|=S_u\),特殊的,若该节点本身是串尾,则 \(S_u~|=(1<<dep_u)\) 。
考虑依旧使用状压来匹配,在字典树上跑当前的文本串,记录跑到的节点到根节点中的串尾的长度,也能用状压维护,最后把两个值与起来不为 \(0\) 就能计入答案了。
首先将病毒代码段插入自动机,建出 fail 指针,显然如果能在不走串尾的情况下在字典图上经过一个环则有解,这一过程可以通过 dfs 实现。
考虑一个自动机常见优化,当一个节点的 fail 指针如果指向串尾,则其一定不能走。
考虑自动机的匹配问题,可以枚举匹配到的文本串末端,求出其在自动机上的节点编号后在 fail 树上用 DS 维护,由于 fail 树上根到节点路径上所有字符串都为枚举字符串的后缀,所以不重不漏。
考虑本题,建出自动机后,建出 fail 树,由于 fail 树上 \(u->v\) 路径表示 \(u\) 的字符串为 \(v\) 的字符串的后缀,说明新增一个模式串,在 fail 树上以其为根的子树一定能新增贡献,删除同理。查询只需要像上文一样,枚举末端,然后单点查询就可以了。
于是只需要用 \(dfs\) 序转序列问题后维护一个支持单点查询,区间修改的数据结构即可。
套路的建出 fail 树,由于修改权值,我们不能将 fail 树上以其为根的子树全部修改,因为其他串可以被权值更大的子串所覆盖,所以我们考虑转成单点修改权值。
查询的话同理,我们枚举末端,求出节点编号为 \(u\),考虑到根到 \(u\) 上的路径全为子串,我们只需要求路径最值即可,可以用树剖来维护。
自动机 + DP
在自动机上的 DP 十分套路,一般设 \(dp[i][j]\) 表示跑到自动机上的节点 \(i\),并且当前匹配到文本串第 \(j\) 位的答案。
正难则反,考虑完全不可读的文章数,则答案为 \(26^m-ans~\)。
有一个显然的结论是匹配到的点能计入答案当且仅当其不是串尾,于是可以直接用来做转移的条件。
记 \(dp[u][j]\) 表示跑到自动机第 \(u\) 个点,匹配到第 \(j\) 位的方案数。
初始值 \(dp[0][0]=1\)
当转移后的节点不为串尾时有转移方程 \(dp[tr[u].ch[i]][j+1]+=dp[u][j]\) 。
套路的,我们设 \(dp[u][j]\) 表示跑到自动机第 \(u\) 个点,匹配到第 \(j\) 位的方案数。
特殊的,我们在求 fail 指针时,以 \(u\) 为结尾的贡献要加上 \(tr[u].fail\) 的贡献,因为根到 \(fail\) 的路径组成的字符串为根到 \(u\) 路径组成字符串的一个后缀,当加入节点 \(u\) 时,后缀同样能累计贡献。
初始值 \(dp[u][j]=-INF\)
转移方程会比较简单:
\(dp[tr[u].ch[i]][j+1]=\max(dp[tr[u].ch[i]][j+1],dp[u][j]+tr[tr[u].ch[i]].sum)\)
将字符串建出自动机,标记串尾。
当把数位 DP 放在自动机上跑,根据套路,设 \(dp[u][j][0/1]\) 表示跑到自动机上第 \(u\) 个点,匹配第 \(j\) 位,前 \(j\) 位是否选取了上界(0/1)。
若当前处于第 \(j\) 位,位于节点 \(u\), 且下一位不为串尾,则有转移:
\(dp[tr[u].ch[0\cdots9]][j+1][0]+=dp[u][j][0]\)
\(dp[tr[u].ch[n[j+1]]][j+1][1]+=dp[u][j][1]\)
\(dp[tr[u].ch[0\cdots n[j+1]-1]][j+1][0]+=dp[u][j][1]\)
初始值设置的比较特殊,我们考虑没有前导 \(0\) 的情况来设置初始值。
但是,这样不足 \(n\) 位的数会被我们所舍弃,所以我们在递推的初态要加上前 \(j-1\) 位全为 \(0\) 的情况。
标签:连边,tr,笔记,学习,fail,自动机,节点,dp From: https://www.cnblogs.com/tidongCrazy/p/16892132.html