推 NTHUlagka: 大師真的好強 第一題原來那麼簡單喔我還在那邊用bitma 03/05 00:04
→ NTHUlagka: sk 03/05 00:04
今天還不錯
https://i.imgur.com/Ifg4g1v.png
1. Split With Minimum Sum
最大的要放在個位數，有兩個個位數的位置
接著依據大小往前擺
2. Count Total Number of Colored Cells
這題出的不好，因為跟程式沒什麼關係
可以算出公式解 2n^2 - 2n + 1
3. Count Ways to Group Overlapping Ranges
可以分成好幾個集合
其中只要某一集合內的一個 range 被選了
則整個集合都要被選
而最後的答案就是 2^{集合數}
因為對於第一個 group 對每個集合都可以選擇選或不選
而決定好第一個 group 則另一個 group 也自動被決定了
至於怎麼算出集合數，只要先 sort 之後
每當新的 range 的左端點 <= 當下集合裡最大的右端點
就要加進這個集合裡
否則就可以開一個新的集合
因為在這之後的 range 一定都不會和之前的相交了
4. Count Number of Possible Root Nodes
可以發現，如果 root 從某個點 u 轉移到某個他的子節點 v
則只有 u v 之間的關係會受到影響
令 score_u 是以 u 為 root 時符合的 guess 數
則 score_v = score_u + (guess 裡 [v, u] 的數量) - (guess 裡 [u, v] 的數量)
所以先跑一次 dfs 算出以 root = 0 時的 score_0
最後再跑第二次 dfs 算出以各個節點當 root 時的 score 是否 >= k 即可
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677945617.A.E77.html