推 sustainer123: 大師 01/15 12:03
※ 編輯: fxfxxxfxx (140.112.16.175 臺灣), 01/15/2023 12:04:12
推 pandix: 大師 01/15 12:06
推 zizc06719: 大師 01/15 12:10
最近真的不太順
https://i.imgur.com/R1cOf6U.png
主要是最近都沒辦法一次寫完就沒 bug
加上 LeetCode 時間很緊
一花時間 debug 就直接噴飛了
得想點辦法才行
1. Difference Between Element Sum and Digit Sum of an Array
照他說的加一加再相減即可
2. Increment Submatrices by One
稍微算了一下發現其實不能用 brute force 因為 500*500*10000 應該要過不了
（如果 brute force 能過的話我會生氣）
所以要用類似 prefix sum 的東西
mat[i][j] 會是 (0, 0) 到 (i, j) 裡
query 左上角的數量 - 右上角的數量 - 左下角的數量 + 右下角的數量
寫起來有點卡手
3. Count the Number of Good Subarrays
用 sliding window 計算以 j 為終點的最短合法 subarray
如果 [i, j] 是合法的，則 [0, j], [1, j], ..., [i, j] 都是合法的
算合不合法就去維護現在 window 內的 pair 數量就可以
4. Difference Between Maximum and Minimum Price Sum
以某個節點 v 為 root 時的 cost 是以他開始的最大 price sum 減去他自己
我用 two-pass 跑了兩次 dfs，root 統一是 0
第一次算出從各節點出發的最大的兩個 price sum
第二次時計算出各節點的 cost，也就是考慮往上走 parent 之後不考慮自己的最大 price sum
選最大的 cost 即可
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673755281.A.CE0.html