HDU 2829 Lawrence:四邊形不等式優化 DP(分組背包/決策單調性)
題目大意 有 N 個數 a[1..N],需放置 M 個分隔點(炸路),將序列分成 M+1 段。第 i 段(L..R)的代價為 w(L,R) = Σ_{k=L+1
UVA 216 Getting in Line:全排列暴力求解電纜最短連接
問題描述 N (≤ 8) 個點座標,找訪問所有點恰好一次的路徑(不需回起點),最小化總歐氏距離 + 16*(N-1)(每段額外 16 英尺)。輸出路徑與總長。
計算幾何基礎:判斷兩線段是否相交(向量叉積法)完整模板
核心幾何原理 線段 P1P2 與 P3P4 相交的充要條件: 跨立實驗:P1、P2 分別在 P3P4 兩側,且 P3、P4 分別在 P1P2 兩側。向
HDU 1839 Delay Constrained Maximum Capacity Path:二分答案 + Dijkstra 求最大容量路徑
題目大意 無向圖 N (≤ 10,000) 點、M (≤ 50,000) 邊。每邊有容量 C 與時間 D。從 1 到 N 尋找一條路徑,使其 最小邊容量最大,且
HDU 1754 I Hate It:Splay Tree(伸展樹)區間最大值查詢與單點修改
題目大意 維護一個長度 N (≤ 200,000) 的序列,支援兩種操作(M 次): U a b:將第 a 個數改為 b。 Q a b:查詢區
UVA 10806 Dijkstra, Dijkstra:無向圖最短往返路徑(費用流建模)
題目大意 給定 n 點無向帶權圖,求從 1 到 n 再返回 1 的最短往返路徑,要求不重複使用任何邊(即去程與回程邊不相交)。若無解輸出 Back to jai
UVA 二分圖匹配經典例題總結:KM 算法、最小點覆蓋、最大獨立集、最小路徑覆蓋完整實現
二分圖基礎知識回顧 頂點集分為 X, Y,邊僅連接跨集合頂點。 匹配:邊集中任意兩條不共用端點。 最大匹配:邊數最多的匹配。
POJ 2151 Check the difficulty of problems:概率 DP 計算冠軍解題數與全隊至少解一題的聯合機率
題目大意 有 T (≤ 1000) 支隊伍、M (≤ 30) 道題。隊伍 i 解出題目 j 的機率為 P[i][j]。求:所有隊伍至少解出 1 題,且冠軍(解題
UVA 10827 Maximum Sum on a Torus:環狀矩陣最大子矩陣和(四倍擴展法)
題目大意 給定 N × N (N ≤ 75) 的方陣,上下左右皆為環狀連接(即 torus)。尋找一個子矩陣(可跨越邊界),使其元素和最大。測資 ≤ 18 組。
HDU 3724 Encoded Barcodes:字典樹 + 條形碼解碼 + 二分查找綜合應用
題目大意 有 N (≤ 10,000) 個產品名稱(小寫字母,長度 ≤ 30),M (≤ 2,000) 個查詢。每個查詢給出 K (≤ 30) 條條形碼,每條碼
POJ 1365 Prime Land:大整數質因子分解與輸出格式詳解
題目大意 輸入由多組測資組成,每組以一連串 p t 配對給出,表示質數 p 的 t 次方。遇到 p = 0 結束該組,再計算 N = (∏ p^t) - 1,並
TOJ Right Triangles II:座標平面直角三角形計數(邊平行座標軸)
問題描述 給定 N (3 ≤ N ≤ 100,000) 個互不相同的平面整數點 (X, Y),座標範圍 1..100,000。請計算有多少種方式選擇三個點,使它
TOJ 4224 Cryptologist:一次性密碼本(OTP)空格與句點位置推導解題詳解
題目背景與核心任務 本題源自 TOJ 4224,情境為密碼學家 Slavko 使用一次性密碼本(One-Time Pad, OTP)加密訊息。明文僅包含小寫字母
C++ 指標基礎操作:動態記憶體分配與釋放實例解析
指標與動態記憶體管理基礎 在 C++ 程式設計中,指標是直接操作記憶體位址的強大工具。正確理解指標的分配、使用與釋放流程,對於撰寫高效且安全的程式碼至關重要。本
HDU 1045 Fire Net:回溯搜尋最大非攻擊砲台放置
問題描述 n×n (n≤10) 棋盤,部分格為牆(X)。放置砲台,同行/同列無牆阻隔不能相互攻擊。求最大放置數。 回溯剪枝 按行優先(索引 0..n*n-1)
CF 337C Quiz:最小期望分數與快速冪取模
問題描述 答對得 1 分,連續答對計數器 +1,歸零於答錯。計數器達 k 時歸零並分數翻倍(先加 1 再翻倍)。共 n 題,答對 m 題,求最小可能分數模 1e
UVA 10115 Automatic Editing:多規則字串替換模擬
問題描述 給定 n (≤ 10) 條規則,每條:find 字串、replace 字串(可為空)。對輸入文本行,依序應用規則:每條規則反覆替換最左匹配,直到無匹配