Codeforces 396A:數論與組合數學計算因數序列數
題目大意 給定 n 個整數 a_i,令 m = ∏ a_i。求有多少個長度為 n 的正整數序列 (b_1,...,b_n) 滿足 ∏ b_i = m。答案模 1
HDU 4122 Alice's Mooncake Shop:單調隊列優化動態規劃
題目大意 月餅店在整點製作月餅,不同時段成本不同。訂單給定時間、數量。可提前製作冷藏,每小時存儲成本 S,保質期 T 小時。求滿足所有訂單的最小總成本。 時間
HDU 1431 素數回文:生成回文數並判斷素性
題目大意 求區間 [a, b](b ≤ 1e8)內所有既是素數又是回文的數。 生成回文數而非篩素數 直接篩 1e8 內素數記憶體過大。觀察:回文數極少。生成所
UVALive 6622 Absurdistan Roads:最小生成樹 + 補充邊構造圖
題目大意 給定 n ≤ 2000 點的最短路距離矩陣,用恰好 n 條邊構造一張圖,使其最短路矩陣等於給定矩陣。保證解存在。 構造思路 先用 Prim 算法構
HDU 4082 Hou Yi's Secret:暴力枚舉三角形判斷相似計數
題目大意 給定 n ≤ 18 個點,求由這些點組成的三角形中,最多有多少個相似三角形。相似定義:三角形對應角相等。 暴力枚舉可行性 n ≤ 18,三角形總數
POJ 3469 Dual Core CPU:最小割模型分配任務到雙核
題目大意 有 n 個任務,可在 CPU A 或 B 上運行,耗時分別為 a_i, b_i。m 對任務若分配到不同 CPU 產生額外開銷 w。求最小總開銷。 最
POJ 2051 / UVALive 3135 Argus:優先隊列模擬定時任務調度
題目大意 註冊若干查詢,每個有 ID (Q_num) 和周期 (Period)。所有查詢同時啟動,首次在 Period 秒後返回結果,之後每隔 Period 秒
FZU Super A^B mod C:歐拉定理降冪求大指數模
題目大意 計算 A^B mod C,其中 1 ≤ A,C ≤ 1e9,B 是最多 10^6 位的大整數。多組測試數據。 數學原理:歐拉定理降冪 若 gcd(A
Codeforces 21C Stripe 2:前綴和枚舉分割點計數
題目大意 給定長度 n 的整數序列,將其分成三段非空連續部分,使得第一段和等於第二段和,或等於第三段和,或第二段和等於第三段和。求滿足條件的分割方法數。(原題描
HDU 2149 Public Sale:巴什博弈求先手必勝加價策略
題目大意 兩人輪流加價,每次加 1~M,價格 ≥ N 者得標。Lele 先手,求第一次加價多少能保證獲勝。輸出所有必勝初始加價,遞增序;無解輸出 none。
HDU 1217 Arbitrage:Floyd 算法檢測貨幣套利機會
題目大意 給定 n 種貨幣和 m 1(即套利)。 圖模型與 Floyd 變形 建立有向圖,邊權為匯率。求任意 i→j 的最大匯率乘積。用 Floyd 算法:
POJ 3614 Sunscreen:貪心 + 優先隊列分配防曬霜
題目大意 C 隻奶牛,每隻有可接受陽光強度區間 [minSPF, maxSPF]。L 種防曬霜,每種有 SPF 值和數量。每隻奶牛最多用一瓶。最大化能防曬的奶牛
POJ 3670 Intervals:最小費用流解決區間 k 覆蓋問題
題目大意 給定若干區間,每個區間有權值。選擇區間覆蓋數軸,每個點最多被覆蓋 k 次。最大化總權值。 網絡流建模 經典「區間 k 覆蓋」轉最小費用最大流: 離
Codeforces 484B Maximum Value:類篩法枚舉模數優化求最大餘數
題目大意 給定 N 個整數 a[i],求 max(a[i] % a[j]),滿足 a[i] ≥ a[j]。 核心觀察 對於固定的 aj,ai % aj 的最大
Codeforces 484A Bits:貪心構造區間內最大 popcount 最小數值
題目大意 給定區間 [l, r],找一個數 x ∈ [l, r],使得 popcount(x)(二進制 1 的個數)最大;若有多個,取最小的 x。 貪心策略
Codeforces 484D Kindergarten:動態規劃最大化分段差值和
題目大意 給定長度 N 的序列 a[i],將其分成若干連續段,每段價值為 max - min。求最大總價值。 DP 狀態設計 dp[i][0]:前 i 個元素
Codeforces 484E Sign on Fence:可持久化線段樹 + 二分查詢最大高度
題目大意 給定長度 N 的數組 h[i] 表示柵欄高度。Q 次查詢,每次給 l, r, w,求區間 [l, r] 中連續長度 ≥ w 的子區間的最大可能高度(即
HDU 5078 Revenge of LIS II:求第二長上升子序列長度
題目大意 給定長度 N ≤ 1000 的序列,求第二長上升子序列(SLIS)的長度。子序列不同定義:長度不同,或同一位置元素下標不同。若有多個 LIS,則 SL