→ a9486l: 大師..... 03/05 12:01
→ dustsstar79: 大師 03/06 11:40
這場不太好
https://i.imgur.com/3QkQbHP.png
今天恍神晚了 30 秒入場，不過應該影響不大
倒是第三題有點出乎我意料
1. Pass the Pillow
因為 time <= 1000 所以可以直接一步一步模擬
設定初始方向 dir = 1，當要超界時掉頭 dir = -dir 即可
2. Kth Largest Sum in a Binary Tree
DFS/BFS 隨便選，反正紀錄每一層的和就好
之後取第 k 大的
我直接 sort 完取 index k - 1
反正 O(nlogn) 就綽綽有餘不需要 O(n)
3. Split the Array to Make Coprime Products
這題有點出乎意料
我還真想不到不需要因式分解的做法
難不成 python 硬乘會過嗎
我想了兩個方法
第一個是同時紀錄左邊和右邊因式分解，看有沒有重複
每次移動邊界只需要看當下被改動的地方有沒有影響即可
因為每個數最多有 O(log n) 個質因數（可以壓更緊）
但因為我的因式分解是用 map 存
所以總複雜度 O(nlog^2(n) + KlogK)
K 是 max(nums[i]) 用來預先計算每個數的質因數的
第二種方法是對於每一個質因數 p
都找出最早出現及最晚出現的 index: [left, right]
則 left 和 right 一定要在同一邊
所以一要選就要選整個 range
總共最多有 O(min(nlogn, K/logK)) 個質因數
最後 sort 之後 greedy 的取相交的 range 即可
（和昨天的題目一樣）
複雜度是對每個數做質因數分解的 O(nlogn)
以及預先計算的 O(KlogK)
4. Number of Ways to Earn Points
可以取好幾個的背包問題
給的範圍不需要任何優化直接硬暴就可以了
DP[i][v] = DP[i-1][v] + sum_{0<j<=count_i}(DP[i-1][v-j*mark[i]])
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677988825.A.C46.html