某岛

… : "…アッカリ~ン . .. . " .. .
October 19, 2021

Codeforces Round #749

又是 一轮构造 Round。。。
要想上分必须要瞬秒掉 E、F。。。

https://codeforces.com/contest/1586
https://zhuanlan.zhihu.com/p/422490422

Problem E. Moment of Bloom

构造。
任取一颗生成树,然后直接树上暴力拉路径即可,不需要写 lca = =。

Problem F. Defender of Childhood Dreams

构造。
假设有 c 种颜色,那么最大能支持 c^k 个点,答案就是 ceil(log(n,k))。
如何构造?每次将当前点集,按照顺序拆成 k 组,组外部之间全部连颜色 c,内部不再使用颜色 c,递归构造下去即可。

实现起来貌似只要一行,不需要憨憨的去写递归。。。

Problem G. Omkar and Time Travel

题目背景是命运石之门!
感觉有点像 Codeforces Global Round 15 的 F 啊。。。
我们不妨用那个题的语言重新叙述这个题,看看有什么不同。

  • 初始所里的传送门都是 active 的
  • 传送之后会让传送位置在目标点之后的传送门更新为 active
  • 经过的 inactive 不会变成 active
  • 最后求的从总的时间变成传送发生的次数

结果感觉反而更简单了。。。dp 状态也类似。。
f[i] 表示再回到这个传送门需要经过传送多少次即可,只需要考虑被这组区间完全包含的区间即可,可以排序后用 树状数组 简单维护。
考虑最后所有状态都 inactive 的情况,答案就是所有 f[i] 的和。

最后如果询问允许一些状态为 active,只要处理出这些状态是否可以跳过即可。

Problem H. Omkar and Tours

感觉比前面几个题都简单
有点像 前几天 FHC R3 的最后一题
离线并查集即可,第二问类似虚树求直径,同样可以在并查集里简单维护。
需要求树上两点之间边权的最大值,显然倍增祖先最好写。(如果 E 题不小心写了 lca 可以粘过来。。。

Problem I. Omkar and Mosaic

构造?