POJ 3345 Bribing FIPA:樹形 DP 最小賄賂成本獲取足夠選票
問題描述 n 個國家(≤ 200),形成樹狀支配關係(根為超級大國)。賄賂一國需 cost 鑽石,可獲得該國及其所有從屬國的選票。求獲得至少 m 張選票的最小鑽
動態規劃求最長遞增子序列 (LIS):O(n²) 經典解法 Java 實作
問題描述 給定字串(或數列),求最長嚴格遞增子序列長度。例:dabdbf → abdf,長度 4。 DP 狀態定義 dp[i] = 以第 i 個字元開頭的最長
POJ 1469 二分圖最大匹配:Hopcroft-Karp 算法模板
問題描述 N 位學生、P 門課程。輸入每門課程可選的學生編號。判斷是否存在完美匹配(匹配數 = 學生數)。 Hopcroft-Karp 算法 分層 BFS +
HDU 2642 Stars:二維樹狀數組 動態維護矩形區域星星計數
問題描述 動態操作: B x y:在位置 (x,y) 增加一顆星(若無) D x y:刪除位置 (x,y) 的星(若有) Q x1 y
POJ 3255 Roadblocks:次短路 SPFA + A* 算法
問題描述 給定 N 個節點、R 條雙向邊,求從 1 到 N 的次短路長度。次短路定義:長度嚴格大於最短路,且在所有這類路徑中最短。路徑可重複經過節點/邊。 算
HDU 4099 Revenge of Fibonacci:字典樹 (Trie) 查詢斐波那契數列前綴
問題描述 給定字串前綴,查詢斐波那契數列中第一個以此為前綴的數的索引(最多前 40 位)。斐波那契數列項數較大,需高精度加法。 解法:Trie + 高精度斐波
BZOJ 1087 [SCOI2005] 互不侵犯 King:狀態壓縮 DP 解棋盤放國王
問題描述 N×N 棋盤(N ≤ 9)放 K 個國王,互不攻擊(八方向相鄰不可)。求方案數。 狀態壓縮 DP 設計 狀態:f[i][j][state]
Codeforces 416D Population Size:貪心分割等差數列
問題描述 給定長度 n 0)。 貪心策略 遍歷序列,嘗試將當前數併入前一個等差數列。核心邏輯: 記錄前兩個非 -1 的數,確定公差 d 檢查
UVa 10905 Children's Game:自定義排序規則拼接最大數字
問題描述 給定一組數字,將它們拼接成一個盡可能大的整數。數字很大,需用字串處理。關鍵在於排序比較函數:不是字典序,而是比較 a+b vs b+a。 核心比較邏
HDU 1181 變形課:有向圖 DFS 判斷路徑連通性
問題描述 輸入多組字串,每組以 0 結束。字串首尾字母代表有向邊(如 abc 表示 a→c)。判斷是否存在從 b 到 m 的路徑。注意:必須建有向圖,建無向圖會
Codeforces 416C Booking System:餐廳訂桌貪心策略
問題描述 餐廳有 n 批客人,每批給出人數 ci 與消費 pi。有 m 張桌子,每張桌容量 rj。一桌只能坐一批客人,且桌容量 ≥ 客人數。目標:最大化總收入,
ZOJ 1409 Communication System:枚舉帶寬 + 貪心選擇最小價格
問題描述 有 n 種設備,第 i 種有 mi 個選項,每個選項有帶寬 b 與價格 p。每種選一件,使系統 B/P 最大,其中 B 為所選設備的最小帶寬,P 為總
LeetCode 平衡二叉樹判斷:遞歸後序遍歷 O(n) 解法
問題描述 判斷一棵二叉樹是否為高度平衡:任意節點的左右子樹高度差不超過 1。 遞歸解法核心思想 後序遍歷(左→右→根),遞歸函數返回: ≥ 0:該子
HDU 1573 X問題:擴展中國剩餘定理求解同餘方程組
問題描述 給定 m 個同餘方程:x ≡ bi (mod ai),求 1 到 n 之間滿足所有方程的整數個數。注意測試資料中 ai 可能為 0(題目說正整數但實際
Codeforces 416B Art Union:流水線作業調度貪心解法
問題描述 有 n 位畫家、m 幅畫。畫家以流水線方式作業:第 j 位畫家處理第 i 幅畫需 tij 時間。規則: 每幅畫必須按畫家順序 1→2→...