POJ 1963 All in All:雙指針判斷子序列
問題描述 給定兩個字符串 s 和 t(長度 ≤ 100,000),判斷 s 是否為 t 的子序列(即能否從 t 中刪除若干字符得到 s)。多測試用例,以 EOF
POJ 2049 Finding Nemo:網格 BFS + 優先隊列最小化穿門數
問題描述 地圖由牆和門組成,牆厚度忽略不計。魚爸爸從起點出發,在非牆區域自由移動,穿過一扇門計為 1 代價。求到達尼莫位置所需最少穿門數。座標為整數交點,實際移
HDU 1272 小希的迷宮:並查集判斷圖是否為樹
問題描述 給定無向圖的邊列表(以 0 0 結束一組,-1 -1 結束輸入),判斷是否滿足: 連通(任意兩點有路徑) 無環(任意兩點有且僅有一條簡單路徑) 即
POJ 2253 Frogger:最小化最大跳躍距離的 Dijkstra 變體
問題描述 青蛙從石頭 0 跳到石頭 1,可經過其他石頭。每次跳躍距離為歐氏距離。青蛙希望「最長單次跳躍距離」最小。輸出這個最小可能的最大跳躍距離(保留三位小數)
HDU 2814 Interesting Fibonacci:Pisano 週期與歐拉定理巧解巨指數
問題描述 定義 G(n): G(1) = F_{A^B},其中 F 為斐波那契數列(F_0=0, F_1=1) G(n) = G(n-1)^{F_{A^B}}
HDU 1757 A Simple Math Problem:矩陣快速冪解線性遞推
問題描述 遞推函數 f(x): x < 10 時 f(x) = x x ≥ 10 時 f(x) = Σ_{i=0}^{9} a_i f(x-1-i),其中 a
UVA 10458 Cricket Ranking:容斥原理計算有界組合數
問題描述 給定 k 個區間 [l_i, r_i],從每個區間選一個整數,求和為 n 的方案數。結果可能極大,需高精度輸出。 數學轉化 令 x_i ∈ [l_i
POJ 1328 Radar Installation:貪心區間選點經典題
問題重述 海岸線為 x 軸,海域在上半平面。雷達安裝在岸上(x 軸),覆蓋半徑 d。給定 n 個島嶼坐標 (x_i, y_i)( 0),求最少雷達數覆蓋所有島嶼
POJ 1062 昂貴的聘禮:等級限制下的最短路變體
問題背景 探險家要用最少金幣娶到酋長女兒。物品編號 1..N(1 號為酋長承諾),每個物品有原價 P、主人等級 L、若干替代品 (T, V) M 不得直接/間接
HDU 1180 詭異的樓梯:三維 BFS 與時間奇偶性狀態
問題描述 哈利波特在霍格華茲遭遇會每分鐘翻轉方向的樓梯(豎直 | ↔ 水平 -)。地圖大小 M×N ≤ 20,包含障礙 *、走廊 .、起點 S、終點 T。哈利每
HDU 1588 Gauss Fibonacci:等差數列索引下的斐波那契加權求和與 4×4 矩陣快速冪
問題數學建模 等差數列 g(i) = k·i + b。求 Σ_{i=0}^{n-1} f(g(i)) 模 M,其中 f 為標準斐波那契數列 (f(0)=0, f
動態線程池查找百萬數據:C++ 多線程實現筆記
專案結構概覽 本項目演示如何動態創建指定數量的線程,在動態分配的大數組(1,000,000 元素)中並行查找目標值。專案包含頭文件 array.h 及主程式邏輯
HDU 4883 TIANKENG's Restaurant (區間選點/掃描線) 替代解法詳解
區間選點視角的統一解法 本題可視為經典「區間選點」問題的加權版本:每個區間 [ST, ED) 有權重 X_i (人數),求時間軸上權重和的最大值。標準區間選點
UVA 11290 Gangs:卡特蘭數與字典序第 k 小合法括號序列構造
問題本質:括號序列的字典序排名與構造 給定 n, k,構造長度 2n-2 的字串,由 E(入棧) 和 S(出棧) 組成,滿足任意前綴 E 數 ≥ S 數 (合法
HDU 4883 TIANKENG's Restaurant:餐廳椅子最小需求與區間最大重疊數
問題轉化:時間線上的最大並發人數 n 組客人,第 i 組 X_i 人,到達 ST_i,離開 ED_i。若一組到達瞬間另一組離開,椅子可重複使用。求最少椅子數使所
HDU 3306 Another kind of Fibonacci:矩陣快速冪求廣義斐波那契平方和
問題數學建模 廣義斐波那契數列:A(0)=1, A(1)=1, A(n)=X·A(n-1)+Y·A(n-2) (n≥2)。求 S(n) = Σ_{i=0}^n
UVA 11549 Calculator Conundrum:計算機溢位截斷下的最大值循環檢測
問題建模 計算機顯示 n 位數字 (1 ≤ n ≤ 9)。初始值 k (0 ≤ k < 10^n)。重複平方:若結果超過 n 位,僅保留最高 n 位 (截斷低位
設計模式精講:橋接模式實現遙控器與電視解耦
橋接模式核心思想 橋接模式將「抽象部分」與「實作部分」分離,使兩者可獨立變化。本質是「組合優於繼承」——透過持有介面參考 (has-a) 取代繼承關係 (is-