BZOJ 1503 郁悶的出納員:SBT 懶標記維護工資統計
題目大意 操作: `I k`:插入工資 `k`(若 `k ≥ MIN`)。 `A d`:全體工資加 `d`。 `S d`:全體工資減 `d`,低於 `MIN`
HDU 5389 Zero Escape:數位 DP 優化分組方案數
題目大意 n 個人,每人 ID 為正整數。 兩門門檻值 `A`, `B`(1-9)。 將所有人分為兩組,各組 ID 的「數位根」(迭代求和至個位)分別等於 `
HDU 4260 The End of The World:漢諾塔剩餘步數遞歸計算
題目大意 標準漢諾塔:3 柱,n ≤ 63 個盤,從 A 移到 B,最優解步數 2^n - 1。 給定中間狀態(字符串表示每盤所在柱),求完成遷移所需剩餘步數
HDU 5384 Danganronpa:AC 自動機多模式匹配統計
題目大意 n 個文本串 A_i(總長 ≤ 1e5),m 個模式串 B_j(總長 ≤ 1e5)。 對每個 A_i,輸出所有 B_j 在其出現次數之和(模式串可重
FZU 強連通分量縮點 + 入度為零最小代價
題目大意 有向圖 N 點,每點有購買成本(部分點無成本 = 不可購買)。 購買一點後,其可達點全部「染色」。 求最小總成本使所有點染色;若不可能,輸出不可染色
POJ 3468 區間加/區間和:線段樹懶標記模板
題目大意 序列長度 N ≤ 100,000,初始值 ±1e9。 Q ≤ 100,000 操作: `C a b c`:區間 [a,b] 每個元素加 c(|c|≤
C++ PIMPL 惯用法:接口與實現分離
動機 類定義中若包含私有數據成員,任何修改(增減成員、改變類型)都會導致所有包含該頭文件的編譯單元重新編譯。PIMPL(Pointer to IMPLement
Codeforces 316C Replacement:連續點號替換的 O(1) 查詢維護
題目大意 字符串 s(長度 n ≤ 3e5),包含小寫字母和 .。 操作:將 s[x] 改為字符 c,每次修改後輸出 f(s) = 消除所有連續 .. 所需最
POJ 2115 循環次數:同餘方程 + 64 位整數處理 2^k 模數
問題轉化 for 循環:i = x; i != y; i = (i + m) mod 2^n。求最小循環次數 t 使 x + m*t ≡ y (mod 2^n)
POJ 1061 青蛙約會:擴展歐幾里得算法解一元一次同餘方程
數學建模 兩青蛙同向跳,起點 x,y,步長 m,n,周長 L。求最小 t 使: x + m*t ≡ y + n*t (mod L) ⇔ (m-n)t ≡ y-x
HDU 4265 Science!:二分答案 + 最大流分解完美匹配
問題模型 n 人 n 個按鈕,Y/N 矩陣表示人能否站按鈕。每輪所有人各站一個不同按鈕,且同一人不能在不同輪次站同一按鈕。求最大輪數 k 並輸出 k 組完美匹配
HDU 5378:樹上標號概率 DP + 模逆元計算方案數
問題重述 n 節點樹,標號 1~n 排列。若節點標號是其子樹中最大值,稱該節點為「好」。求恰有 k 個好節點的排列數。答案 = n! × 概率 p。 DP 狀
LeetCode 104 Maximum Depth of Binary Tree:遞歸求二叉樹最大深度
題目描述 給定二叉樹根節點,求最大深度。深度定義為從根到最遠葉子節點的節點數。空樹深度為 0。 遞歸解法 節點深度 = max(左子樹深度, 右子樹深度) +
URAL 1057 Amount of Degrees:數位 DP 統計 B 進制下恰好 K 個不同冪次和的數
問題轉化 求區間 [X,Y] 中滿足:數 = K 個互不相同的 B 的整數次冪之和的整數個數。 即:該數的 B 進制表示中恰好有 K 個 1,其餘為 0(因為每
PAT(A) 1063 Set Similarity:STL set 求 Jaccard 相似度
題目要求 給 N 個集合(元素為整數),Q 次查詢:兩集合的 Jaccard 相似度 = |A∩B| / |A∪B| × 100%,保留一位小數。N≤50, 元
HDU 5386 Cover:逆向剝離 + 貪心構造操作序列
題目大意 n×n 矩陣,兩類操作: L x y:第 x 列全置 y H x y:第 x 行全置 y 給初始矩陣、目標矩陣、m 個操作(順序未定)。求操作排列順序
POJ 1625 Censored!:AC 自動機 + DP + 高精度計數合法字符串
問題建模 給定字符集(可能超過 128,需映射)、P 個禁用模式串。求長度為 M 的字符串中不包含任何禁用模式的數量。N=字符集大小, M≤100, P≤100