→ Firstshadow: 大師 04/02 00:02
推 dustsstar79: 大師 04/02 00:02
→ dustsstar79: 最後一題夠廢==模板題 04/02 00:02
推 pandix: 大師 04/02 00:04
→ Che31128: 大師 04/02 00:13
推 NTHUlagka: 大師 04/02 00:21
推 JIWP: 大師 04/02 01:00
這次還行
https://i.imgur.com/EryuGTN.png
感覺最後一題網路上應該一堆答案
不過我寫的卡卡的浪費很多時間
不然我前三題的狀況還不錯
1. Form Smallest Number From Two Digit Arrays
兩層 for 迴圈，如果數字一樣可以只有一個數
取最小的
2. Find the Substring With Maximum Cost
變形的 maximum subarray
其實就只需要維護字母對應到值的表
再把 s 都轉成對應的值再直接套 max subarray 就可以了
3. Make K-Subarray Sums Equal
看了一下解出來的人數，大家好像認為這題比第四題難
我自己是覺得比一般的第三題難
至少感覺需要兩種第三題等級的技巧同時用在這一題上
所有長度 k 的 subarray 的和都一樣，
所以對任意的 i，我們有
arr[i] + ... + arr[i+k-1] == arr[i+1] + ... + arr[i+k]
消一消之後就能得到 arr[i] == arr[i+k]
因為是環形的，所以會被切成 gcd(arr.size(), k) 個 subsequence
令 g = gcd(arr.size(), k)
對任意 0 <= i < g, 我們有
arr[i] = arr[i + g] = arr[i + 2g] = ...
而讓 arr[i], arr[i+g], arr[i+2g], ... 全部一樣的最小 cost
就是取他們的中位數
4. Shortest Cycle in a Graph
看題目就感覺是經典題
我自己也覺得好像很久以前有做過的樣子
不過實際寫起來就一直卡卡的
最後我的作法是對每個節點 v 做 bfs
如果有某個走過的點想要走到另一個走過的點
就計算他們的 cycle 的長度
因為是 bfs 所以這會是這兩個點經過 v 的最短 cycle 了
不過要處理像是不能朝原路走回去之類的細節
後來是覺得如果改成每次拔掉一個邊 (u, v) 後
再用 bfs 算 u --> v 的最短距離會比較簡潔
因為 |E| 和 |V| 的上限都是 1000 所以時間應該沒差
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.198.173.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1680364821.A.B52.html