NBOJ 1181 Big Mouth of Abyss:刪除 k 位數字得最小值(貪心區間選擇)
問題重述 給定長度 L 的數字字串,刪除 k 個字元,剩下 L-k 個字元保持相對順序,組成最小可能的數值(允許前導零,輸出時去除)。 貪心策略:逐位決定 剩
wxWidgets 實現可控的連續繪圖循環:OnIdle 與 wxTimer 兩種方案對比
應用場景 CCD 相機實時取像顯示:需要一個「可隨時啟動/停止」的繪圖循環。while(true) 會阻塞主事件循環,導致 GUI 凍結、無法響應停止按鈕。必須
POJ 1787 Charlie's Change:帶數量限制的硬幣找零(完全背包變體)
問題建模 有 1, 5, 10, 25 美分硬幣各 ci 枚,需湊出 m 美分,使總硬幣數最大(即找零硬幣最多),並輸出各面額使用數。若無解輸出 Charlie
POJ 1928 採花生:貪心模擬與路徑規劃
題目情境 一個 row×col 的田地,每格有若干花生。機器人從 (0,0) 出發,每次移動到剩餘花生最多的格子(曼哈頓距離),採摘需 1 單位時間,移動費時等
UVA 439 Knight Moves:棋盤騎士最短路徑 BFS 詳解
問題重述 標準 8×8 國際象棋棋盤,給定起點與終點(如 e2 e4),騎士每步走「日」字(8 種位移)。求最少步數。 為什麼用 BFS? 所有邊權為 1 的
UVA 572 Oil Deposits:八方向連通區域計數(DFS/BFS)
題目大意 給定一個 m×n 的網格,@ 代表油田,* 代表空地。八個方向(上下左右 + 四個對角線)相連的 @ 屬於同一油田。請計算圖中共有多少個獨立油田。
UVA 297 Quadtrees:四叉樹黑像素計算完整解析
題目背景與核心問題 UVA 297 Quadtrees 是一道經典的四叉樹應用題。題目給出兩個以字串形式編碼的四叉樹,分別代表兩幅 32×32 黑白圖像(根節點
編程之美 2.15:最大子矩陣和——二維轉一維 + 部分和優化 O(N³)
問題描述 給定 n × m 矩陣,求子矩陣元素和的最大值。 核心思想:固定上下邊界,轉化為一維最大子段和 預計算二維前綴和 PS[i][j]:以 (1,1)
編程之美 2.14:最大子數組和——動態規劃與環形數組變體完整解析
問題 1:一維數組最大子數組和(經典 Kadane 算法) 動態規劃建模 階段:k = 1..n,考慮以第 k 個元素結尾的子數組。 狀態:以 k 結尾的最
編程之美 2.13:子數組最大乘積——前綴後綴疊乘與啟發式分析雙解法
問題描述 給定長度 N 的整數數組,只能用乘法,求去掉恰好一個元素後,剩餘 N-1 個數乘積的最大值。 解法一:空間換時間——前綴後綴疊乘 O(N) 預計算:
編程之美 2.12:快速尋找滿足條件的兩數/三數之和——排序+雙指針技巧
問題 1:兩數之和等於目標值 算法:排序 + 雙指針(對撞指針),O(N log N)。 快速排序數組 A。 初始化 i=0, j=n-1。 當 i < j:
編程之美 2.11:尋找最近點對——分治法與 POJ 3714 變體詳解
問題描述 給定平面上 N 個點,找出距離最近的兩個點(最近點對問題)。 分治算法 O(N log N) 預排序:按 x 坐標排序(快排/歸併排 O(N lo
編程之美 2.9:斐波那契數列——矩陣快速冪與大整數突破極限
問題描述 斐波那契數列:1)。求第 n 項。 矩陣快速冪解法 遞推關係可寫為矩陣形式: [F(n), F(n-1)]ᵀ = A · [F(n-1), F(n-
編程之美 2.8:找符合條件的整數——同餘+BFS 構造最小 0/1 乘積
問題描述 給定正整數 N,求最小正整數 1),使得 N × M 的十進制表示僅包含數字 0 和 1。 核心洞察 直接搜索 M 空間極大(M 位數可超過 4
編程之美 2.6:精確表達浮點數——分數形式實現無損計算
問題描述 用分數形式精確表示小數(含有限小數與無限循環小數),避免浮點數誤差,實現精確四則運算。 數學原理 將小數分為三部分:整數部分 c、非循環小數部分 a
程式設計之美 2.5:尋找最大的 K 個數——三種數據規模下的最優策略
問題描述 從 N 個數中選出最大的 K 個。根據 N 的數量級(百、百萬、百億),分析最適合的算法與複雜度。 場景一:N ~ 百(全量內存,可隨機訪問) 順序
程式設計之美 2.1:計算 32 位無符號整數二進制中 1 的個數——四種算法深度解析
問題描述 給定一個 32 位無符號整數,求其二進制表示中 1 的個數(Hamming Weight / Population Count),要求執行效率極高。
程式設計之美 1.17:俄羅斯方塊 AI——啟發式評分與貪婪決策
問題描述 讓電腦自動玩俄羅斯方塊:給定當前棋盤狀態與下一個方塊,決定該方塊的旋轉狀態與落下列,以獲得最高生存分數。 核心框架:模擬所有合法動作 → 評分 →