POJ 3107 Godfather:樹形 DP 尋找最小最大連通分量
問題大意 給定 n 個節點的樹(n ≤ 50,000),刪除一個節點後樹分裂為多個連通塊。Godfather 定義為刪除後最大連通塊節點數最小的節點。求所有符合
BZOJ 4071 [APIO2015] 巴鄰旁之橋:中位數與動態維護區間最優橋址
問題背景 河流將城市分為 A、B 兩岸,各有 10⁹+1 棟建築。N 個居民家和辦公室分布在兩岸。政府最多建 K 座垂直橋樑(K=1 或 2),橋不可相交。居民
BZOJ 1588 [HNOI2002] 營業額統計:平衡樹(Splay)維護最小波動值
問題描述 1)波動值為當天營業額與前 i-1 天中最接近值的差的絕對值。求所有天波動值之和。 平衡樹解法 維护已出現營業額的有序集合,支持查找前驅(最大的 ≤
LeetCode 35 搜索插入位置:二分查找經典應用
題目大意 給定升序無重複數組和目標值,返回目標值索引;若不存在,返回按順序插入的位置索引。 二分查找核心 尋找第一個 ≥ target 的位置。若找到等於 t
LeetCode 34 在排序數組中查找元素的第一和最後位置
題目翻譯 給定升序整數數組,找到目標值的起始和結束下標。要求 O(log n) 時間。若不存在返回 [-1, -1]。 二分查找變體 需實現兩次二分: 查找
POJ 3140 Contestants Division:樹形 DP 求最小分割差值
問題大意 給定一棵 n 節點的樹(n ≤ 100,000),每個節點有學生數。刪除一條邊將樹分成兩部分,使兩部分學生總數差值最小。輸出最小差值。 樹形 DP
LeetCode 完美平方數:動態規劃與數學定理雙重解法
問題描述 給定正整數 n,求最少多少個完全平方數(1, 4, 9, 16...)之和等於 n。例如 n=12 答案 3 (4+4+4);n=13 答案 2 (4
LeetCode 筆記:從前序與中序遍歷構造二叉樹
題目要求 給定二叉樹的前序遍歷和中序遍歷,重建二叉樹。假設樹中無重複值。 遞歸構造原理 前序第一個元素為根節點。 在中序中找到根節點,左側為左子樹,右側為右
LeetCode 55 Jump Game:貪心算法 O(n) 判斷能否到達終點
題目描述 給定非負整數數組,初始位於索引 0。每個元素代表該位置最大跳躍長度。判斷能否到達最後一個下標。 示例:[2,3,1,1,4] → true;[3,2,
HDU 5587 Array:數列構造與前綴和遞歸求解
問題描述 初始數列 {1}。每次操作:複製當前數列接在尾部,中間插入一個 0,然後從該 0 開始(含 0)所有數字 +1。操作若干次後,求前 M 項和,M ≤
POJ 3723 Conscription:Kruskal 求最大權森林轉化最小生成樹
問題建模 招募 N 名女兵、M 名男兵,每人基礎成本 10000。若異性間有關係值 d(0 < d < 10000),且一方已招募,另一方成本減少 d(即 10
C++ 默認參數陷阱:聲明與定義分離時的規則、重載消歧義與最佳實踐
核心規則:從右向左設置默認值 函數參數列表中,**若某參數有默認值,其右側所有參數必須有默認值**。 void func(int a, int b = 10,
POJ 3481 Double Queue:Treap 實現雙端優先隊列(最大/最小優先級服務)
問題描述 銀行服務系統:客戶有 ID (K) 和優先級 (P)。支持操作: 1 K P:添加客戶 2:服務最高優先級客戶(輸出 ID,刪除)
POJ 2104 K-th Number:劃分樹(主席樹前身)解決區間第 k 小問題
問題描述 給定長度 n (≤100,000) 的互不相同整數數組,回答 m (≤5,000) 個查詢:區間 [i, j] 中第 k 小的數是多少? 示例:a =
LeetCode 36 Valid Sudoku:三維標記數組 O(1) 驗證數獨合法性
題目描述 判斷 9×9 數獨盤面(部分填充,空格為 .)是否合法:每行、每列、每個 3×3 子宮內數字 1-9 不重複。僅需驗證已填充部分。 核心思路:三維布
PAT 1027 Colors in Mars:十進制轉十三進制 RGB 色彩值
題目背景 火星人用 13 進制(0-9, A-C)表示顏色,格式為 6 位數:前 2 位紅、中 2 位綠、後 2 位藍。給定三個十進制色值(0-168),輸出火
POJ 3580 SuperMemo:Splay 树區間加法、翻轉、旋轉、插入、刪除、查最小值綜合模板
問題描述 維護一個序列(初始長度 n ≤ 100,000),支持 6 種操作(m ≤ 100,000): ADD x y D:區間 [x, y] 每個
在 Visual Studio 2012 (MSVC) 下編譯 SDCC 編譯器完整指南
背景 SDCC (Small Device C Compiler) 是開源免費的 8051 等單片機 C 編譯器,源碼可移植。本文記錄在 Windows 下用