ZOJ 3635 Cinema in Akiba:塊狀鏈表模擬座位分配,O(√n) 查找刪除
問題大意 n ≤ 50000 個座位(1~n),n 個人依次入場。第 i 人票號 a[i](1 ≤ a[i] ≤ n-i+1),表示從剩餘空座位中選第 a[i]
HDU 1533 Going Home:KM 算法解決最小權完美匹配(曼哈頓距離)
問題建模 網格中有若干 H(人)和 m(房子),數量相等(≤ 100)。 每人必須分配一間不同房子,使總曼哈頓距離最小。 這是經典最小權完美匹配(指派問題),雙
C++ 靜態成員詳解:靜態變量與靜態函數的定義、訪問、初始化陷阱與最佳實踐
靜態成員核心概念 靜態成員變量:屬於類而非對象,全程序僅有一份拷貝,被所有對象共享。 靜態成員函數:屬於類,無 this 指針,只能訪問靜態成員。 聲明與定義
POJ 2570 Fiber Network:Floyd-Warshall 位掩碼求公司連通性
問題建模 n ≤ 200 個節點(站點)。有向邊附帶一組公司(小寫字母 a-z,最多 26 家)。 查詢:給定起點 A、終點 B,輸出能單獨提供 A→B 連通路
POJ 3321 Apple Tree:樹上子樹查詢與單點修改,DFS 序 + 樹狀數組
問題建模 給定一棵 n 節點樹(n ≤ 10⁵),根為 1。每節點初始有 1 個蘋果。 操作: • C u:翻轉節點 u 蘋果狀態(有↔無)。 • Q u:查詢
Codeforces 282E Sausage Maximization:字典樹維護前綴/後綴異或最大值
問題重述 給定長度 N 的陣列 A。選一個前綴(可空)和一個後綴(可空),兩者不重疊,使 (前綴異或) ⊕ (後綴異或) 最大。 等價於:選 i ≤ j,最大化
HDU 1885 Key Task:BFS 狀態壓縮尋找最短路徑(鑰匙開門問題)
問題大意 迷宮 n×m(≤100),字元含義: . 空地、# 牆、* 起點、X 終點、 a-z 鑰匙(拾取後永久擁有)、A-Z 門(需對應小寫鑰匙開啟)。 求從
POJ 3764 The xor-longest Path:樹上路徑異或和最大值,字典樹優化查詢
問題轉化 給定一棵 n 節點樹,邊有權值。任意路徑 u→v 的異或和 = xor[u] ⊕ xor[v],其中 xor[x] 為根到 x 路徑邊權異或和。 證明
HDU 1702 ACboy needs your help again!:FIFO/FILO 模擬隊列與棧操作
題目大意 多組測資。每組給出命令數 N 與模式(FIFO 或 FILO)。 後續 N 行命令:IN M 入隊/棧,OUT 出隊/棧並輸出值。 若結構為空執行 O
POJ 2253 Frogger:Floyd-Warshall 求最小最大邊權路徑(Frog Distance)
問題定義 給定 n ≤ 200 個石頭座標,石頭 1 為起點,石頭 2 為終點。青蛙可跳躍任意兩石頭間,跳躍距離為歐氏距離。 定義路徑的代價為路徑上最長單次跳躍
HDU Always Cook Mushroom:極角排序 + 樹狀數組離線處理三角形區域權值和
問題建模 1000×1000 網格,點 (x,y) 權值 (x+A)(y+B)。 M ≤ 10⁵ 個查詢:每查詢給 (a,b,x),求直角三角形區域和。三角形頂
LightOJ 1269 Consecutive Sum:字典樹求區間異或和最大值與最小值
問題轉化 給定長度 N 的陣列,選取一個連續區間,計算其異或和。求所有區間異或和的最大值與最小值。 前綴異或 pre[i] = a[1] ⊕ ... ⊕ a[i
UVA 818 Cutting Chains:狀態壓縮 DFS 求最少開環數重組單一鏈條
問題建模 給定 n ≤ 15 個環,部分環相連(無向圖)。操作:剪開一個環(開環),可將其取出並重新連接。目標:用最少開環數,將所有環重組為單一簡單鏈條(首尾相
POJ 2408 Anagram Groups:哈希分組 + 排序輸出前 5 大字母重組群組
題目要求 讀入所有單字(至 EOF),將「字母組成相同」(anagram)的單字分為一組。輸出群組大小前 5 大的群組,每組內按字典序輸出不重複單字。群組大小相
POJ 1195 Mobile Phones:二維樹狀數組(Fenwick Tree)區間增點查完整解析
題目大意 維護一個 1024×1024 的二維陣列(初始全 0),支援兩種操作: 1. 1 x y v:單點加 v(座標 0-based)。 2. 2 x1 y
C++ 觀察者模式完整實作:部落格訂閱系統範例與 UML 設計解析
模式定義與別名 觀察者模式 又稱 發布-訂閱、Model-View-Controller (MVC) 核心機制。 定義物件間一對多依賴:當一個物件(主題/Sub
LeetCode Remove Element:三種原地移除目標值算法對比與最佳實踐
題目要求 給定陣列 nums 與值 val,原地移除所有等於 val 的元素,返回新長度。元素順序可改變,超出新長度部分內容不限。 方案一:雙指針對撞(前後掃
POJ 2567/2568 Code & Decode the Tree:Prufer 序列與樹的雙向轉換完整實作
Prufer 序列核心性質 對於 n 個節點的無根樹: 反覆刪除編號最小的葉子節點,記錄其鄰居,得到長度 n-2 的序列 → Prufer 序列。 樹與 Pr