status
date
slug
tags
category
type
password
icon
目錄
Ch00. 前言Ch01. Recursiond001. P-1-1. 合成函數(1)d002. Q-1-2. 合成函數(2)d003. P-1-3. 棍子中點切割d004. Q-1-4. 支點切割d005. Q-1-5. 二維黑白影像編碼d006. P-1-7. 子集合乘積d007. Q-1-8. 子集合的和d008. Q-1-10. 最多得分的皇后d009. Q-1-11. 刪除矩形邊界Ch02. Sort & Binary Searchd010. P-2-1. 不同的數d011. P-2-2. 離散化d012. P-2-3. 快速冪d013. Q-2-4. 快速冪 2d014. Q-2-5. 快速計算費式數列第 n 項d015. P-2-6. Two-Number problemd016. Q-2-7. 互補團隊d017. Q-2-8. 模逆元d018. P-2-9. 子集合乘積d019. Q-2-10. 子集合的和d020. P-2-11. 最接近的區間和d021. Q-2-12. 最接近的子矩陣和d022. Q-2-13. 無理數的快速冪d023. Q-2-14. 水槽d024. P-2-15. 圓環出口Ch03. Queue & Stackd025. P-3-1. 樹的高度與根d026. P-3-2. 括弧配對d027. Q-3-3. 加減乘除d028. P-3-4. 最接近的高人d029. Q-3-5. 帶著板凳排雞排的高人d030. P-3-6. 砍樹d031. P-3-7. 正整數序列之最接近的區間和d032. P-3-8. 固定長度區間的最大區段差d033. P-3-9. 最多色彩帶d034. P-3-10. 全彩彩帶d035. Q-3-11. 最長的相異色彩帶d036. Q-3-12. 完美彩帶d037. Q-3-13. X差值範圍內的最大Y差值d038. Q-3-14. 線性函數Ch04. Greedy & Line Sweepingd042. P-4-1. 少林寺的代幣d043. P-4-2. 笑傲江湖之三戰d044. P-4-3. 十年磨一劍d045. P-4-4. 幾場華山論劍d046. P-4-5. 嵩山磨劍坊的問題d047. Q-4-6. 少林寺的自動寄物櫃d048. P-4-7. 岳不群的併派問題d053. Q-4-8. 先到先服務d049. P-4-9. 基地台d054. Q-4-10. 恢復能量的白雲熊膽丸d050. P-4-11. 線段聯集d051. P-4-12. 一次買賣d052. P-4-13. 最大連續子陣列d055. P-4-14. 控制點d056. P-4-15. 最靠近的一對d057. Q-4-16. 賺錢與罰款d058. Q-4-17. 死線高手d059. Q-4-18. 少林寺的櫃姐d060. Q-4-19. 五嶽盟主的會議場所d061. Q-4-20. 監看華山練功場Ch05. Divide & Conquerd064. P-5-4. 反序數量d065. P-5-7. 大樓外牆廣告Ch06. Dynamic Programmingd066. P-6-1. 小朋友上樓梯最小成本d067. P-6-2. 不連續的表演酬勞d068. P-6-3. 最小監控鄰居的成本d072. Q-6-4. 闖關二選一d073. Q-6-5. 二維最大子矩陣d069. P-6-6. 方格棋盤路線d070. P-6-7. LCSd074. Q-6-8. Local alignmentd071. P-6-9. 大賣場免費大搬家d075. Q-6-10. 置物櫃出租d076. P-6-11. Catalan numberd084. Q-6-12. 楊鐵心做 1 休 Kd077. P-6-13. 周伯通的基地台d085. Q-6-14. K 次買賣d078. P-6-15. 一覽衆山小d118. P-6-16. 山寨華山論劍d079. P-6-17. 切棍子d086. Q-6-18. 矩陣乘法鏈d080. P-6-19. 階梯數字d081. P-6-20. Hyper-cube pathd082. P-6-21. 刪除邊界d083. P-6-22. 文無第一武無第二d087. Q-6-23. 直升機抓寶d088. Q-6-24. 隔離採礦d089. Q-6-25. 貨郎問題Ch07. Graphd090. P-7-1. 探索距離d091. P-7-2. 開車蒐集寶物d092. P-7-3. 機器人走棋盤d093. P-7-4. 方格棋盤的最少轉彎數路線d094. Q-7-5. 闖關路線d095. P-7-6. DAG 的最長與最短路徑d099. Q-7-7. AOV 最早完工時間d100. Q-7-8. 小寶的著色問題d096. P-7-9. 最短路徑d097. P-7-10. 挖坑跳d101. Q-7-11. 紅白彩帶d098. P-7-12. 最小生成樹
Ch00. 前言
Ch01. Recursion
d001. P-1-1. 合成函數(1)
- Version 1
- Version 2
d002. Q-1-2. 合成函數(2)
- Version 1
- Version 2
d004. Q-1-4. 支點切割
關於兩次前後綴和的詳解
為什麼求兩次前後綴和就能找到最佳切點？
這個問題的核心在於如何高效地計算數列的「加權和不平衡度」，並找到使這個值最小的切割點。讓我們來一步步拆解這個過程。
1. 問題目標
給定一個數列 ，我們想找到一個最佳切割點 ，使得 的值 最小。
這代表的是：
- 數字 的影響力由 來衡量：
- 距離 越遠，對總不平衡度影響越大。
- 最佳 需要讓左右部分的總影響力盡可能相等。
2. 直接計算的問題
如果直接暴力計算：
- 對於每個 （候選切點），我們需要計算
- 這樣的計算是 的。
- 如果要對所有可能的 都計算一遍，時間複雜度會是 ，這對於 來說太耗時。
3. 透過前後綴和來快速計算
為了加速這個計算，我們預處理兩組前綴和：
- ：區間 的總和
- ：區間 的總和
接著，我們定義”前綴加權和”和”後綴加權和”：
這兩個陣列的核心作用是 快速計算每個 的不平衡度：
其中：
- 左側不平衡度：
- 右側不平衡度：
這樣，我們只要遍歷 一次（ ），就能快速計算所有 的不平衡度，從而找到最佳切割點。
4. 具體計算流程
假設我們有數列：
- 計算 和
- 計算 和
- 尋找最佳切割點
- 對每個 ，計算
- 找到 最小的 組合，即為最佳切割點。
5. 為什麼這樣做可以找出最佳切點？
透過 和 ：
- 代表 左側區間的影響力。
- 代表 右側區間的影響力。
- 當這兩個值相近時，左右影響力相等，切割點最平衡！
我們只需要一次遍歷（ ）就能高效計算所有 的影響力，從而找出最佳切割點，避免暴力計算的 時間複雜度。
6. 時間複雜度
- 計算前綴和 ：
- 計算前綴加權和 ：
- 尋找最佳切割點：
- 總共 時間內完成切割點的搜尋，比原本 快。
d007. Q-1-8. 子集合的和
- backtracking 窮舉
d008. Q-1-10. 最多得分的皇后
- 就是 N Queen(?
- 使用一個 vector 來記錄之前每個 row 放置的皇后 col，讓斜向判斷比較好寫
Ch02. Sort & Binary Search
d013. Q-2-4. 快速冪 2
- 超大數 ⇒ string
- 將大數切開，一位一位處理，再用10的冪次乘上去，不斷取模才不會 overflow
d014. Q-2-5. 快速計算費式數列第 n 項
- 對上述矩陣做快速冪，最後左上角的元素即為
- 扁平化成一維 vector 比較好寫
d016. Q-2-7. 互補團隊
- 用 bitmask 去重
- 如果用 XOR 還是需要 ，會吃 TLE
- 直接排序後往後做二分搜，複雜度是
d017. Q-2-8. 模逆元
- 費馬小定理: 當模數 為質數時，任意非 倍數的整數 的模逆元為
d018. P-2-9. 子集合乘積
- 直接窮舉 鐵吃 TLE
- 折半枚舉，往另外一個集合搜模逆元，將複雜度降到
d020. P-2-11. 最接近的區間和
- 維護前綴和集合，在其中搜尋最接近 的結果
d021. Q-2-12. 最接近的子矩陣和
- 對矩陣的行列求前綴和，扁平化成一維陣列，轉換成 d20 求解。
d022. Q-2-13. 無理數的快速冪
- 有理數部分:
- 無理數部分:
- 剩下的就是快速冪
d023. Q-2-14. 水槽
官方教材提示
- 如果區間只剩一個水槽，該水槽高度=水量，結束
- 否則，在區間中找出最高的隔板，假設此隔板高度為 。區間被此隔板分成左右兩邊，考慮下面三種情形：
- ，水量足以讓兩邊都至少 ，區間內所有水槽高度皆是相同的平均值，結束。
- 水量不足以越過輸入這一邊，那麼，另外一邊一定不會有水，縮小區間遞迴呼叫。
- 水量會越過輸入這一邊，那麼，輸入這一邊的水槽高度一定都是 H，把水量扣掉後遞迴呼叫另外一邊。
- 跟著提示遞迴下去就對了
d024. P-2-15. 圓環出口
- 將整個陣列複製一份拼在後面 ⇒ 維護前綴和 ⇒ 往後二分搜
Ch03. Queue & Stack
d027. Q-3-3. 加減乘除
- Version 1
- Version 2
- 順便附上 Python 版(?
d028. P-3-4. 最接近的高人
- Monotonic Stack
d029. Q-3-5. 帶著板凳排雞排的高人
- 用 vector 維護 monotonic sequence，因為單調性可以直接二分搜
d031. P-3-7. 正整數序列之最接近的區間和
- Sliding Window
d032. P-3-8. 固定長度區間的最大區段差
- Monotonic Queue
d033. P-3-9. 最多色彩帶
- 針對整個區間做計數太浪費時間，只在 element 進入與離開 window 時做計數更新與判斷
d037. Q-3-13. X差值範圍內的最大Y差值
- 排序後將距離已經超出的點從比較的範圍中移除
Ch04. Greedy & Line Sweeping
d042. P-4-1. 少林寺的代幣
- 大硬幣可以換成小硬幣 ⇒ 不存在小硬幣可以支付而大硬幣不能支付的情況
- 選大硬幣與小硬幣都可以的情況下，選大硬幣的數量更少
d043. P-4-2. 笑傲江湖之三戰
- 只挑最方戰力最低的挑戰
d044. P-4-3. 十年磨一劍
- idx 越小，權重越大(會被乘到更多次) ⇒ 從小到大排序
- 要用 Long Long 才不會 overflow
d045. P-4-4. 幾場華山論劍
- Earliest Deadline First
d046. P-4-5. 嵩山磨劍坊的問題
- 按照 從小到大排序
d047. Q-4-6. 少林寺的自動寄物櫃
- 這題用 double 算比值會 overflow，改用交叉相乘比大小的方式排序
d048. P-4-7. 岳不群的併派問題
- 越早合併的數字會被算到越多次 ⇒ 小的先合併
d053. Q-4-8. 先到先服務
- 用 pq 的大小模擬櫃台的數量
d049. P-4-9. 基地台
- 二分搜
d050. P-4-11. 線段聯集
- 將有重疊的線段合併，確定沒有重疊的線段再計算長度
d051. P-4-12. 一次買賣
- 記錄過去最低的價格，更新最大可以獲得的利益
d052. P-4-13. 最大連續子陣列
- 保證區間內的總和為正數，否則只會讓後續的總和變小 ⇒ 不如不取
d055. P-4-14. 控制點
- 依照 x 座標排序，再對 y 座標維護 monotonic stack
d056. P-4-15. 最靠近的一對
- 這題用教材給的作法最後兩個測資會吃 TLE，不知道為啥==
- 逐漸縮小搜尋的範圍
d057. Q-4-16. 賺錢與罰款
- Shortest Job First
d058. Q-4-17. 死線高手
- Earliest Deadline First
- 小師妹最後還是跟林平之跑了QQ
d059. Q-4-18. 少林寺的櫃姐
- d053 加上二分搜
- 這題要注意的是不要真的創建 個櫃台(pq 的大小)，會很久==
- 只需要創建 個櫃檯就夠了
d060. Q-4-19. 五嶽盟主的會議場所
- Line Sweeping 問題，筆記可參考這邊
d061. Q-4-20. 監看華山練功場
- 不斷更新最遠可以覆蓋到的時間點，每次延長就將計數器加一
Ch05. Divide & Conquer
d064. P-5-4. 反序數量
- 其實就是 Merge Sort
d065. P-5-7. 大樓外牆廣告
- Merge Version
- 跑兩次 monotonic stack
Ch06. Dynamic Programming
d066. P-6-1. 小朋友上樓梯最小成本
- 定義 為從第 0 階踩到第 階時，需要耗費的最小成本
- 第 階只可能來自第 階或第 階
- 可得出轉移式
d067. P-6-2. 不連續的表演酬勞
- 定義 為從第 0 天到第 天最大的酬勞
- 第 天的最大酬勞是第 天表演或是第 天和第 天都表演
- 可得出轉移式
d068. P-6-3. 最小監控鄰居的成本
- 要額外處理
d073. Q-6-5. 二維最大子矩陣
- 跟 d052 類似的作法
d069. P-6-6. 方格棋盤路線
- 每一格的狀態只能來自上方的格子或是左邊的格子
d070. P-6-7. LCS
- 經典 LCS
- 將 LCS 轉成 LIS 問題，用 的複雜度求解
d074. Q-6-8. Local alignment
- 定義狀態 為 與 的最大分數
- 如果 ，跟 LCS 一樣從前一個狀態轉移過來並加上分數
- 否則:
- 放棄之前的狀態，從 開始重新計算(如果是 Global Alignment 就沒有這個情況) ⇒ 0
- 選擇讓 與 不同 ⇒
- 選擇 空白 ⇒
- 選擇 空白 ⇒
- 可得出下列轉移式:
d071. P-6-9. 大賣場免費大搬家
- 01 背包問題，筆記可參考這邊
d075. Q-6-10. 置物櫃出租
- 就是 01 背包
d076. P-6-11. Catalan number
- memorization dp
d084. Q-6-12. 楊鐵心做 1 休 K
- 就是 d067
d077. P-6-13. 周伯通的基地台
- d068 加上 Monotonic Queue 維護區間最小值
d078. P-6-15. 一覽衆山小
- 就是 LIS
這題跑 會TLE
- 將 的定義改成目前最長的 LIS ，再加上二分搜，變成
d079. P-6-17. 切棍子
- 區間 dp
d086. Q-6-18. 矩陣乘法鏈
- 跟 d079 一樣的區間 dp
d080. P-6-19. 階梯數字
- 數位 dp
d089. Q-6-25. 貨郎問題
- TSP 問題
Ch07. Graph
d090. P-7-1. 探索距離
- BFS
d093. P-7-4. 方格棋盤的最少轉彎數路線
- 把轉彎當作走一步，每次都直接走到底
d094. Q-7-5. 闖關路線
- Level Order BFS
d095. P-7-6. DAG 的最長與最短路徑
- Topological Sort
d099. Q-7-7. AOV 最早完工時間
- Topological Sort → 找出最早開始與結束時間 → 找出最晚開始與結束時間 → 如果最早開始時間等於最晚開始即 critical jobs
d100. Q-7-8. 小寶的著色問題
- 檢查是否為二分圖
d096. P-7-9. 最短路徑
- Dijkstra
d098. P-7-12. 最小生成樹
- Kruskal
- Author:Zixu
- URL:https://zixu.us.kg/article/AP325_隨筆
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
