某島

… : "…アッカリ~ン . .. . " .. .
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

構造?