推 NTHUlagka: 好猛 大神 12/25 12:33
※ 引述《fxfxxxfxx (愛麗絲)》之銘言：
: 這場打爛了
: https://i.imgur.com/zQkxwTz.png
: 卡在第三題，卡到還先跑去寫第四題
: 明明昨天才寫過一題二分搜 :(
: 1. Shortest Distance to Target String in a Circular Array
: 遇到是 target 的就看他和 startIndex 的距離能不能更新最佳解
我條件寫成
res = min(res, abs(i - startIndex), abs(n + startIndex - i), abs(n + i -
startIndex))
奇怪 真的好醜 現在才想到直接用 n-abs(i-startIndex) 算繞頭尾的狀況就好了 笑死
: 2. Take K of Each Character From Left and Right
: 這題我也小卡，最後把頭尾至少各取 k 個這個條件
: 改成取一個 sliding window 且各字母取的數目至少要留 k 個給其他人
: 兩個條件是等價的
: 不知道有沒有比較好的寫法
我也是 把頭尾共留 k 個想成刪掉中間連續 n-k 個
: 3. Maximum Tastiness of Candy Basket
: 我卡了，卡爆，但完全不應該卡的
: 總之就是對 tastiness 做二分搜
: 4. Number of Great Partitions
: 兩個 partition 都要 >= k
: 因為 k <= 1000，所以可以用 DP 算出 >= k 的子集數目
: 再扣掉 < k 的子集數目就可以了（因為兩個互補）
: 忘了 sum - k >= k 這個條件吃到 penalty
: 這場不太順
沒想到能用 <k 的子集數目去濾掉另一邊沒超過的情況
我這題直接用 dp[n][a][b] 把兩個 group 數量分開記成 a,b
複雜度應該是爆的 O(nkk) 不過還是賽過了== 撿到
https://i.imgur.com/hA5C1G1.png
https://i.imgur.com/6Xcotvp.png
兩天都吃 penalty 到超過時間==
--
可憐
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.79 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671942204.A.61D.html