[心得] CF771C sum over ceil(path length / k) on a tree
看板Prob_Solve (計算數學 Problem Solving)作者rareone (拍玄)時間5年前 (2019/03/31 15:19)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
AS TITLE
題幹非常簡單
Given a bidirectional tree and k
這題要算的就是 sum over ceil(length between any pair of vertice / k)
作法：
DP，每條 path 的貢獻在他的 LCA 算好
我們可以把一條 path 拆成可以被 k 整除的部分跟餘數
像這樣，假設 k = 5
-----, -----, -----, -----, -----, -----, --
接著維護餘數為 t 的 path 有幾條，例子中 t = 2
以及 sum : 已經成為完整的長度為 k 的部分有幾個，例子中是 sum = 6
接著就像算 sum over length of all pair of path
實作細節：
k 不會很大，所以我寫 k^2 n 複雜度也沒慢多少，而且比較好寫
這題我用 struct 把操作包起來，寫起來非常舒服
寫了一個 shift method 實際上是 +1 的意思
Solution:
https://codeforces.com/contest/771/submission/52069290
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.216.110
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1554016795.A.61A.html
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
