POJ 3207:Tarjan 算法解決 2-SAT 問題——圓上弦不相交判定
問題描述 給定一個圓上 n 個點,m 條弦(每條弦連接兩點)。每條弦可以畫在圓內或圓外。判斷是否存在一種分配方案,使得所有弦在各自區域內兩兩不相交。輸出「pan
HDU 3652 B-number:數位 DP 統計含「13」且能被 13 整除的數字
問題描述 定義 B-number(wqb-number)為:十進制表示中包含子串「13」且能被 13 整除的非負整數。給定 n (1 ≤ n ≤ 1,000,0
HDU 1548 A Strange Lift:電梯最短路問題與 Dijkstra 算法應用
問題描述 有一棟 n 層樓的建築,電梯在第 i 層只能向上或向下移動恰好 ki 層。給定起始樓層 A 和目標樓層 B,求從 A 到 B 的最少按鈕按下次數(即最
POJ 3608:旋轉卡殼法求兩凸包最近點對距離
問題描述 給定兩個凸多邊形 P 和 Q(頂點按順時針序給出),求兩多邊形之間的最小距離。這是計算幾何中的經典問題,旋轉卡殼算法可在 O(m+n) 時間內解決,其
UVA 10041 Vito's Family:尋找最小總距離的中位數解法
問題背景 知名黑幫維托·德德斯通(Vito Deadstone)要搬到紐約,他的龐大家族都住在拉馬菲亞大道上。維托希望找一棟房子,使他到所有親戚家的總距離最小化
NYIST 510:昂貴的聘禮 (最短路 + 限制條件)
題目大意 有 n 個物品,每個有價格 c[i]、等級 b[i]、以及若干替代品(有向邊)。購買物品 0 可直接或通過替代鏈獲得。但所購物品的等級差不能超過 m。
NYIST 737:相鄰石子合併 (區間 DP)
題目大意 有 n 堆石子排成一排,每次只能合併相鄰兩堆,代價為兩堆石子數之和。求將所有石子合併為一堆的最小總代價。 DP 定義 dp[i][j] 表示將第 i
HDU 4614:線段樹 + 二分查找 (Vjudge 練習)
題目背景 維護一個長度為 n 的區間,支援兩種操作: 查詢區間 [b, c] 的 1 的個數,並將該區間置 0。 從位置 b 開始,向左、向右各尋找連續 k
POJ 1159:Palindrome (動態規劃求最少插入)
題目大意 給定長度 N (3 ≤ N ≤ 5000) 的字串,求最少插入幾個字元可使其成為回文串。字元區分大小寫。 DP 定義 dp[i][j] 表示子串 s
HDU 3177:搬運物品進山洞 (貪心 + 排序)
題目大意 山洞體積 V,有 n 個物品,每個物品有停放體積 a 和移動體積 b。搬運時需保證當前物品的移動體積 ≤ 山洞剩餘體積。求是否能全部放入。 貪心策略
POJ 1903 / ZOJ 2469 / UVA 1326:Jurassic Remains (Meet-in-the-Middle)
題目大意 給定 n ≤ 24 個僅含大寫字母的字串,選擇盡可能多的字串,使得所有選中字串中每個字母出現次數均為偶數。 關鍵觀察 只關心每字母出現次數的奇偶性。
UVA 644:Immediate Decodability 字符串前綴判斷
問題描述 輸入多組編碼集,每組以單行 9 結束。判斷該組編碼是否「立即可解碼」:即不存在一個編碼是另一個編碼的前綴。輸出 Set X is (not) imme
HDU 1166:敵兵布陣 線段樹單點增減區間求和
問題描述 T 組測試,每組 n (≤50000) 個營地初始兵力。操作: Add i v:第 i 營地加 v Sub i v:第 i 營地減 v Query
HDU 1753 / 1754:I Hate It 線段樹單點修改區間最大值
問題描述 維護長度 n (≤200000) 數組,支持 m 次操作: Q a b:查詢區間 [a,b] 最大值 U a b:將第 a 個元素改為 b 標準線
JOJ 2453:Candy 網絡流建模分配糖果
問題描述 N 顆糖果,M 個孩子 (M≤10)。糖果 i 對孩子 j 的喜好 Aij ∈ {1,2}(2 表示喜歡)。孩子 j 需快樂值 ≥ Bj。分配每顆糖果