【游记】HNOI2021 没翻车记 — Qiuly

Day -2 考了一套神仙题,dandandan 又虐场了,我又垫底了。后面被 ysu 吐槽了一句” 分太低了”(改了前两题,第三题是个巨大恶心多项式,就咕了。 Day -1 去桃花岭散心。 路上青山一直在讨论博弈论,被要求唱歌了(然后芙卡米也被要求唱歌了 后面发现了一条小 阅读更多…

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

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

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

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