【题解】雅礼集训 2017 Day7 题解 — Qiuly

「雅礼集训 2017 Day7」事情的相似度 注意到 最长公共后缀 其实是 SAM 上的 LCA ,因此原题变成了询问深度最深的 LCA 。 定义一个前缀在 parent 树上对应的点为其” 结束点”。考虑一个树上的点什么时候可能成为答案,注意到如果这个点的子树内有两个以上的 阅读更多…

【题解】「WC2018」通道 边分治 + 虚树 — Qiuly

简要题意:给你三棵树,二元组 $(x,y)$ 的贡献是 $x,y$ 在三棵树上最短路径经过的边边权之和,求贡献最高的二元组 $(x,y)$ 所产生的贡献。 考虑对第一棵树边分治,注意到边分治的好处就是直接将第一棵树上 $(x,y)$ 的贡献由原来连在一起的变成相对 $x ,y$ 独立的了。 按照&# 阅读更多…

【题解】CF1485 简要题解 — Qiuly

奇怪的难度。 A 当 $b=2$ 的时候再操作,操作次数是一定的。 因此 $b$ 的变化量很小,暴力枚举。 B 考虑哪个数不同,然后不同后可以选择的区间是什么。 会发现中间夹着的区间选两遍,旁边的选一遍。做前缀和好了。 C 简单转化发现一定要满足 $a=k(b+1),k<b$ 。 枚举 $b$ 阅读更多…

【题解】「Ynoi2018」天降之物 及其加强版「MtOI2019」手牵手走向明天 根号分治 / 序列分块 — Qiuly

最开始的想法是对序列分块,然后每个块维护一个 $\sqrt{n}\times \sqrt{n}$ 的矩阵表示这个块中颜色与颜色的距离,再维护每个颜色到左右端点的最短距离。 容易发现查询的时候很好查询,问题在于修改操作:要对每一个块进行处理,光是枚举块就要用掉 $O(\sqrt{n})$ 的时间,那就 阅读更多…