「雅礼集训 2017 Day7」事情的相似度
注意到 最长公共后缀 其实是 SAM 上的 LCA ，因此原题变成了询问深度最深的 LCA 。
定义一个前缀在 parent 树上对应的点为其” 结束点”。考虑一个树上的点什么时候可能成为答案，注意到如果这个点的子树内有两个以上的” 结束点” 那么就可以，这个时候就直接用其更新答案即可，注意到如果其不合法也一定在子树内有合法答案点存在，且子树内的更优。
这样的话就是询问：所有子树内有至少两个” 结束点” 的深度最大点的深度。
考虑离线，将询问挂在右端点，维护左端点的答案。现在在右边加入一个字符，暴力做法就是不断往上跳祖先，对于祖先 $f$ ，令 $f$ 的子树中有一个最晚的” 结束点”，对应的前缀是 $S{1,k}$ ，那么对于询问的左端点在 $[1,k]$ 中的点都将被更新。由于是前缀 $\max$ 操作，可以直接用 树状数组 维护。
暴力跳祖先是不能被接受的，考虑加速这个过程。注意到插入完毕后，整个一条链上的” 子树中最晚” 结束点”” 都会变为当前插入的右端点。这个东西可以直接用” 区间本质不同子串个数” 那题的方法做，就是直接上 LCT 维护即可。
至于为什么 LCT 的时间复杂度是对的，容易发现这个过程其实和 access 的过程是相似的，直接套用 access 的证明过程就行（当然也可以从 区间染色的颜色段数均摊 理解）。
已经实现：提交记录
$\mathtt{suffix\ automaton}$ 复健计划 $\mathtt{(2/?)}$ 。
「雅礼集训 2017 Day7」跳蚤王国的宰相
考虑当前在点 $u$，如果一个儿子 $v$ 更适合作为答案当且仅当 $siz_v>n-siz_v$ 。要满足点 $u$ 可以被钦定，就一定要满足 $u$ 的内子树和外子树的大小都不超过 $\frac{n}{2}$ 。
画出一棵树，找到它的重心 $g$ ，将 $g$ 提为根节点。现在求 $g$ 某个儿子 $u$ 的答案，不难发现：
- $u$ 子树内是不需要管的，$u$ 的外子树一定需要被调整。
- 调整外子树的最优方案一定是切掉一些 $g$ 的其他儿子，切掉的儿子不需要再次被调整。
这样子的话就挑最大的切，什么时候合法了就停下，得到的一定是最优解。
考虑怎么做 $u$ 子树内某个点 $u’$ ，不难发现：
- $u’$ 子树内是不需要管的，$u’$ 的外子树一定需要被调整。
- 调整外子树的最优方案有两种：
- 切掉一些 $g$ 的其他儿子，被切掉的儿子不需要再次被调整。
- 切掉一些 $g$ 的其他儿子，并且切掉 $g$ 。
不难发现 调整外子树 的第二种方法需要的操作次数就是 $u$ 的操作次数加 $1$ ，那么要管的只有第一种。又不难发现第一种只跟 $u’$ 在 $u$ 子树中的外子树的大小有关，又是满足单调性的，对这个直接求解即可。
时间复杂度 $O(n\log n)$ ，瓶颈在给 $g$ 的子树排序。
已经实现：提交记录
「雅礼集训 2017 Day7」蛐蛐国的修墙方案
连边的操作就是形如” 如果 $i$ 为左括号，那么 $j$ 一定是右括号” 的限制。
然后我想了各种做法，包括但不限于网络流，感觉做不动。哀叹水平不够，偷看 tag 发现是” 搜索” …… 爱了。
先考虑怎么判断合法括号序，显然只需要满足前缀和不小于 $0$ 即可。
容易发现原图一定成为若干环，并且环上的点一定是左右括号相间，那么不会出现奇环，对于每个偶环也只有 $2$ 种方案。硬搜方案的话，最多可能有 $50$ 个偶环，难以通过。不过对于长度为 $2$ 的偶环可以贪心考虑，即一定是左括号在前面，右括号在后面。
这样的话只有长度不小于 $4$ 的环需要被暴力枚举，时间复杂度 $O(n2^{\frac{n}{4}})$ 。
已经实现：提交记录
思维不能硬化啊，搜索也要面子的诶
0 条评论