求一个字符串的连续非空子串与询问串本质不同的非公共子串个数
一开始没看到本质不同，第二个下发数据完全不一致才发现
如果我们要求一个字符串的本质不同子串个数，那么我们只需要对于 \(Parent\) 树上的每一个节点 \(x\) 累计求和 \(maxlen(x)-maxlen(parent(x))\)
现在，又多了一个字符串，导致每个节点产生和原来不一致的贡献，考虑每个节点表示的子串是相应 \(endpos\) 前缀的后缀，也就是说对于每个位置，我们处理下以该位置结尾的前缀与另一个字符串某一子串 \(LCS\) 的最大值 \(L\)，处理一下 \((0,\ L]\) 和 \((maxlen(parent(x)), maxlen(x)]\) 的区间交算下贡献即可，\(L\) 可以通过后缀自动机上的匹配解决
给定前缀结束位置区间，求其两两间 \(LCS\) 的最大值
一个人学 \(SAM\)，也需要考虑历史的进程
这道题在一开始有一个口胡的后缀数组和莫队的 \(O(n\sqrt{nlogn})\) 做法，但觉得常数有点大，就放弃了
之后又错误估计了预处理的点对数量，以为是 \(O(n^2)\)，然后就看了题解，发现是 \(O(nlogn)\)
任意两前缀的 \(LCS\) 一定是相应 \(np\) 节点在 \(Parent\) 树上的 \(LCA\) 的 \(maxlen\)，我们预处理一些点对即可，具体来说，两个子节点合并到父节点时，我们找最接近的合并一定不会差，这样和启发式合并复杂度一致
求 \(A\) 串对 \(B\) 串朴素匹配的比较次数
一道综合性和思维性很好的题
解决的关键在于把匹配的复杂度转移到 \(A\) 上
起初没什么思路，只知道这道题一定是在 \(B\) 的 \(Parent\) 树上乱搞
对着样例和 \(Parent\) 树找了快半个小时的规律才知道怎么做
首先分两种情况讨论
给定后缀集合 \(S\) , 求 \(\sum_{s_i,s_j\in S}LCP(s_i,\ s_j)\)
很套路的一道题，在反串构造后缀自动机建后缀树
在后缀树上 \(DP\) 统计以当前节点为 \(LCA\) 的路径数即可
多组询问就用虚树搞一下就好了
给定关键点，求树的最小割
虚树模板题，虚树是用来解决多次询问，但关键点总数有限的优化方法，就是将关键点及其 \(LCA\) 提取出来在进行 \(DP\)
具体来说，我们先将关键点按 \(dfn\) 排序，依次加入一个栈中，这个栈维护了从根到栈顶的一条链
设加入节点为 \(p\) 则分如下情况讨论
若 \(LCA(p,\ S_{top})\ =\ S_{top}\) 说明 \(p\) 仍在链上，直接入栈
反之，则说明已经到另外一颗子树上了
给定字符串集合，求只属于该字符串的本质不同的非空子串的个数
难度一般，建一个广义 \(SAM\) 在 \(Parent\) 树上对 \(endpos\) 全部属于同一个字符串的统计即可
关键是下面的错误和解决方法
大部分直接按照 \(maxlen\) 拓扑序会 \(WA\)，是因为如果字符串具有相同前缀则在广义 \(SAM\) 中会出现 \(maxlen(parent(A))= maxlen(A)\)
主要是因为大部分广义 \(SAM\) 的写法每次都必须新建一个 \(np\) 节点，但实际上这个 \(np\) 节点所表示的原串的前缀有可能在 \(SAM\) 上出现了，但由于 \(Parent\) 树的性质两者间有边相连，导致了 \(maxlen\) 非严格单调递增的父子关系，可以通过 \(\lbrace ab, abc\ \rbrace\) 体会一下
求最长子串序列使得后一个在前一个出现至少 \(2\) 次
子串序列显然属于 \(Parent\) 树从根节点到叶子节点的链上，考虑 \(Parent\) 树上 \(DP\)
但是，答案是最长的一条链吗？
自己多试几组发现并不是如此，比如 \(abababb\) 中 \(parent(ab) = a\) 但并没有出现两次
本题的关键在于此
首先，不难证明一个结论 \(A\) 的最长串 \(S\) 被\(Parent\) 树上的祖先 \(B\) 的任意 \(S'\) 匹配状态相同，所以选最长串作为序列即可
对 \(n\times m\) 的矩阵进行不重复的 \([1,\ n\times m]\) 整数填数，定义局部最小值为比其八连通块都小的位置，给定局部最小值，求合法方案数
如果罗兹瓦尔说的像这样清晰该有多好
还是我语文太差了
先不讨论非局部最小值的合法性，显然这是一个拓扑排序计数问题，对于一般图的拓扑排序计数问题，通常使用状压\(DP\)，把已排序好的集合作为状态，在转移时判断加入集合的点的前驱是否都已排序，而顺序性体现已排序集合的扩大的过程中，这也是排序问题的核心思想
已知 \(F(t)\ =\ \sum_{i=1}^nt_i^2+\sum_{i=2}^n|h_i+t_i-t_{i-1}-h_{i-1}|\) ，求 \(F_{min}\)
设 \(f_{i,j}\) 表示 \(t_i\ =\ j\) 时 \(F_i(t)\) 的最小值则有如下转移
\[ f_{i,j}\ = \begin{cases} f_{i-1,k}+j^2+|k+h_{i-1}-h_i-j| ,\ j>1\\\\ j^2,\ i\ =\ 1 \end{cases} \]
一个颜色序列删去颜色的方案使得最后剩下来的序列非空且连续
首先一个序列非空且连续就是原颜色序列的一段连续区间，这段颜色区间的每个颜色仅在该区间里出现，对于每个颜色都有一个左端点和右端点，我们枚举合法区间的左端点就可以通过某些数据结构来后面的位置找有多少个合法右端点即可