POJ 3368 RMQ:區間最大頻率查詢 O(1) 解法
問題描述 給定非遞減序列 a[1..n],m 次查詢 [l,r],求區間內出現次數最多的數的頻率。n≤100000, m≤10000。 關鍵觀察 序列有序 ⇒
POJ 1986 Distance Queries:LCA + RMQ 求樹上兩點距離
問題描述 給定 N≤50000 節點的樹(N-1 邊),M 次查詢,每次詢問節點 u,v 間距離。多測試用例。 核心公式 dist(u,v) = depth[
C++ Templates 進階:Policy-based Design 與多重繼承技巧
背景 現代 C++ 庫設計常用 Policy-based Design(策略模式) 實現靜態多態。本文演示如何通過模板多重繼承組合多個策略類,並解決「同一基類多
HDU 4372 Count the Buildings:組合數學與 Stirling 數計算排列數
問題重述 有 N 棟高度互不相同的大樓(高度為 1~N 的排列),從前向後看能看到 F 棟,從後向前看能看到 B 棟。求滿足條件的排列總數,模 1,000,00
POJ 3162 / HDU 4123:樹上最遠距離 + RMQ/線段樹區間查詢
問題拆解與核心洞察 這是一道綜合性極強的題目,分兩階段: 預處理階段:給定一棵帶權樹(n ≤ 50000),求每個節點到其他所有節點的最遠距離 num[i]
HDU 1242 Rescue:優先隊列 BFS 解迷宮最短路徑
題目場景與建模 天使被囚禁在迷宮中,需從起點 a 走到終點 r。迷宮包含: . 可通行空地 # 牆壁不可通行 x 守衛,經過需額外花費 1 單位時間(可理解為
POJ 3126 Prime Path:四位數質數路徑 BFS 尋找最小代價
問題背景與建模 這是一道經典的 BFS 應用題。內閣部長們需要將辦公室門牌號從一個四位數質數變更為另一個四位數質數,規則是:每次只能修改一位數字,且修改後的新號
POJ 1731 Orders:STL next_permutation 生成字典序全排列
題目大意 給定一個字串,要求輸出其所有全排列,並按字典序升序排列。這是一道標準的排列生成問題,利用 C++ STL 中的 next_permutation 可輕
HDOJ 2717 Catch That Cow:BFS 求最短路徑完整解析
題目背景與核心問題 在 HDOJ 2717 Catch That Cow 這道經典題目中,我們需要幫助農夫約翰從位置 N 移動到位置 K。農夫每一步可以有三種移
POJ 1396 All in All:子序列判定雙指針 O(n) 解法
問題描述 給定兩字串 s、t (長度 ≤ 100,000)。判斷 s 是否為 t 的子序列 (即 s 能否通過刪除 t 中某些字符得到)。是輸出 Yes,否輸出
POI 2000 Stripes:SG 函數與取石子遊戲變體
問題描述 棋盤為 1×p 格子。三種條紋:紅 c×1、綠 z×1、藍 n×1 (c,z,n ≤ 1000)。雙方輪流放條紋,不可重疊、不可超出邊界。無法放置者負
C++ static 關鍵字全方位解析:靜態成員、靜態函數、區域靜態變量
static 的三大用法 用法作用域生命週期關鍵特性 靜態成員變量類作用域程式全期屬於類不屬於對象,需類外定義初始化 靜態成員函數類作用域程式全期無 thi
UVA 10003 Cutting Sticks:區間 DP 經典入門
問題描述 長度 L 的木棍,有 m 個切割點。每次切割的代價 = 當前木棍段長度。求將所有切割點切完的最小總代價。 區間 DP 模型 在左右端點各加一個虛擬切
UVA 103 Stacking Boxes:高維矩形嵌套與路徑輸出
問題描述 n 個 m 維「箱子」(m ≤ 10),每維有長度。箱子 A 可嵌套進 B,當且僅當 A 在所有維度上嚴格小於 B (可排序維度順序)。求最長嵌套鏈長
NYOJ 16 矩形嵌套:最長遞增子序列 (LIS) 變體
問題描述 n 個矩形,各有長寬 (a,b)。矩形 X 可嵌套進 Y 當且僅當: (X.a < Y.a && X.b < Y.b) || (X.b < Y.a &
UVa 993 Product of Digits:最小自然數構造與迭代加深搜尋
問題描述 給定非負整數 N (0 ≤ N ≤ 10⁹),找最小自然數 Q,使其各位數字乘積等於 N。不存在輸出 -1。 觀察與剪枝 Q 的每位數字只能是 1
HDU 4368 Water World I:傾斜柱狀圖積水量計算幾何
問題描述 n 根寬度為 1 的柱子並排,高度 a[0..n-1]。整體向左傾斜 angle0) 或向右傾斜 (angle<0)。求最大積水體積。 幾何轉換:柱