Codeforces Round #749
source link: http://www.shuizilong.com/house/archives/codeforces-round-749/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
又是 一轮构造 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
Posted by
xiaodao
Category: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK