HDU 5115 Dire Wolf:區間 DP 正向推導狼群消滅順序
問題大意 一排 n 隻狼,每隻有攻擊力 a[i] 和防御力 b[i]。每回合選一隻狼消滅,代價為其攻擊力加上當前相鄰兩隻的防御力(邊界只有一側)。求消滅所有狼的
HDU 1180 詭異樓梯:狀態機 BFS 處理周期性障礙
問題大意 迷宮中含水平樓梯 - 與垂直樓梯 |,樓梯每兩步切換方向(水平↔垂直)。從 S 到 T 最少步數。M,N ≤ 25。 狀態定義 狀態 (x, y,
CSUOJ 1601 War:離線並查集動態連通性
問題大意 n 個村莊,m 條路。按給定順序摧毀 q 條路,每摧毀一條輸出當前連通塊數。n,m,q ≤ 100000。 離線反向思維 直接處理刪邊難,反向考慮:
C++ 函數列表提取:從正則匹配到 Clang LibTooling 的演進
背景需求 代碼覆蓋率工具需靜態解析 C++ 源文件,提取所有函數名稱與位置,以便插桩統計。 方案演進與避坑 手寫詞法/語法規則:匹配大括號、括號、分號等。
最小樹形圖(朱劉/Edmonds 算法):POJ 3164 & UVA 11183
問題本質 有向圖中尋找以根節點為根的最小生成樹形圖(每個非根節點恰有一條入邊,無環,可達所有節點)。n≤1000, m≤40000。 朱劉算法核心流程 對每
HDU 2647 Reward:拓撲排序計算最小獎金總額
問題建模 n 員工,m 條約束 b(a 獎金比 b 多)。每人至少 888。求最小總獎金,若有環輸出 -1。n≤10000, m≤20000。 拓撲排序 +
UVA 10635:LCS 轉 LIS —— 王子公主最長公共子序列
問題大意 王子與公主各自給出一個排列(長度 p+1, q+1,含起點 1),求兩排列的 LCS 長度。n≤250,O(n^2) LCS 會超時。 核心優化:排
POJ 3280:區間 DP 最小代價構造回文
問題轉化 給定字符串,可插入或刪除字符(代價為該字符對應的 min(insertCost, deleteCost)),求使其成為回文的最小總代價。len ≤ 2
HDU 1728 逃離迷宮:帶轉彎限制的 BFS 狀態擴展
問題大意 m×n 迷宮(≤100),從 (x1,y1) 走到 (x2,y2),最多轉 k 彎(k≤10)。初始方向任選不算轉彎。求是否可達。 狀態定義與 BF
POJ 2082 Terrible Sets:單調棧求直方圖最大矩形
問題本質 給定 n 個寬 w_i、高 h_i 的矩形並排,求能覆蓋在其上方的最大矩形面積。等價於「直方圖最大矩形」問題,n ≤ 50000。 單調棧 O(n)
ZOJ 3326:質數日期區間計數——閏年與篩法結合
問題大意 統計區間 [date1, date2] 內「月份為質數且日期為質數」的天數。年份範圍 1000~2999,需正確判斷格里曆閏年。 解題步驟 預處理
Codeforces 544C:完全背包計數好計劃數
問題重述 n 位程序員,第 i 位每行產生 a_i 個 bug。需分配恰好 m 行代碼,使總 bug ≤ b。求方案數模 mod。n,m,b ≤ 500。 D
UVA 1493 Draw a Mess:並查集加速倒序繪圖
問題大意 N×M 點陣,依序繪製矩形、菱形、等腰三角形、圓形,後繪蓋前。求最終每種顏色佔據的像素數。N≤200, M≤50000,暴力 O(NM) 會 TLE。
POJ 2083 盒分形:遞歸繪製弗雷澤分形圖案
問題定義 n 階盒分形(n ≤ 7)遞歸定義: 1 階為單個 X; n 階由 5 個 n-1 階組成,佈局如同 3×3 九宮格的四角與中心,邊長 3^(n-1)
HDU 1599:最小費用環——Floyd 算法的巧妙改造
問題建模 無向圖中尋找一個至少包含 3 個頂點的簡單環(不重複經過頂點),使環上邊權之和最小。N ≤ 100,M ≤ 1000。 核心洞察:Floyd 過程中
HDU 3953:數位和的秘密——字符串處理輕鬆解
題目大意 給定兩串數字字符串,求其所有數字字符的數值之和。樣例中 99 72 → 9+9+7+2=27,規律極其簡單。 解題思路 直接遍歷兩字符串,將每個字符
C/C++ 內存洩漏完全指南:成因、避免與檢測工具
什麼是內存洩漏? 程序動態申請的內存(malloc/new)在不再使用時未釋放(free/delete),導致該內存塊持續被佔用,操作系統無法將其分配給其他進程
ACdream 1061:long long 絕對值函數的正確選擇
問題背景 題目要求計算兩棵樹 B、C 相對於 A 的位置差 |x - y|,其中 |x|, |y| ≤ 4611686018427387904(即 2^62),