HDU 5073 Galaxy 貪心 + 前綴和 最小轉動慣量
問題物理模型 n 個質點(質量 1)在數軸位置 x[i],繞質心旋轉。可移動 ≤k 個質點到任意位置(疊加允許)。最小化轉動慣量 I = Σ (x_i - x_
LeetCode 78 Subsets 子集生成 位運算與回溯
問題 給定無重複整數數組,返回所有可能子集(冪集)。元素升序,無重複子集。 方法一:位運算枚舉 n 個元素對應 n 位二進制數,0/1 表示不選/選。0 到
HDU 1011 Starship Troopers 樹形 DP + 背包
問題模型 樹形洞穴,根節點 1 為入口。每節點有 bugs(需派兵消滅)和 brain_prob(捕獲大腦概率)。每兵消滅 20 隻蟲。共 M 名士兵。士兵進入
LeetCode Summary Ranges 有序數組區間合併
問題 給定無重複遞增整數數組,將連續區間合併為 end 格式,單獨數字輸出 num。例:5,7]。 優雅解法:雙指針掃描 維護區間起點 start,掃描至連續
ZOJ 3772 Calculate the Function 矩陣線段樹 區間遞推查詢
問題 數列 A[1..N],查詢 F(L,R) 定義為: F(L) = A[L], F(L+1) = A[L+1] F(x) = F(x-1) + F(x-2
POJ 2421 Constructing Roads 預連接邊的 MST
題目變體 標準 MST 問題,但輸入中給出 m 條已建成的道路(必須保留)。求補全連通圖的最小額外代價。 技巧:預連接邊權值設 0 將已建道路對應的邊權值設
HDU 1533 Going Home KM 算法 最優二分匹配
問題 網格地圖包含 m(人)和 H(房子),每人分配一間不同房子,最小化總曼哈頓距離。人數 = 房數 ≤ 100。 模型:二分圖最小權完美匹配 左部:人,右
HDU 2686 Matrix 最大費用最大流 雙路徑不重疊
問題建模 N×N 網格(N<30),每格有權值。從左上角 (1,1) 走到右下角 (N,N) 再返回,去程只能右/下,回程只能左/上,除起終點外不可重複經過同一
LeetCode Implement strStr() 字符串匹配 KMP 與 Rabin-Karp
問題 實現 strStr(haystack, needle):返回 needle 在 haystack 中首次出現的索引,不存在返回 -1。空 needle 返
HDU 3501 Calculation 2 歐拉函數求不互質數和
問題轉化 求 1} i (mod 1e9+7)。 等價於:總和 - 互質數和 = N(N-1)/2 - φ(N)·N/2。 數學推導 1 到 N-1 總和:
HDU 4628 Pieces 狀態壓縮 DP 最小回文覆蓋
問題描述 給定長度 ≤16 的字符串,每步可刪除一個子序列(不要求連續),只要該子序列是回文。求刪空整個字符串的最少步數。 關鍵觀察 長度 ≤16 ⇒ 狀態
HDU 3016 Man Down 線段樹 + DP 遊戲優化
問題模型 垂直分佈的木板,每板有高度 h、左右端點 xl, xr、能量值 val(正/負)。角色從最高板(初始能量 100)開始,每次從當前板左/右端點垂直下落
POJ 2593 / 2479 Max Sequence 最大雙子段和 DP
問題重述 給定長度 N (≤100,000) 的整數序列,選取兩個不重疊的非空連續子段,使其元素和之和最大。輸出該最大值。 核心洞察:分治 + 前綴/後綴最優