「雅礼集训 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}})$ 。

已经实现:提交记录

思维不能硬化啊,搜索也要面子的诶

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code