矩陣乘法 2 (CodeVS 3147) 子矩陣和查詢優化 (前綴和)
問題描述 給兩個 n×n 矩陣 A, B (n ≤ 2000),m 次查詢 (m ≤ 50000)。每次查詢 C = A×B 中子矩陣 [a..c]×[b..d
HDU 1061 Rightmost Digit (快速冪求最後一位)
問題 給定正整數 N (1 ≤ N ≤ 10⁹),求 N^N 的最後一位數字(個位數)。多測試用例,T ≤ ?。 解法:快速冪取模 10 利用二進制分解指數,
POJ 1698 Alice's Chance 最大流模板題 (Dinic 算法)
問題建模 有 N 個電影項目,每項需連續工作 D 天。W 周內每周 7 天,給出每周可工作的日期。問能否安排滿足所有項目天數。構建流網絡: 超級源點 S 連向
求滿足 GCD=n, LCM=m 的正整數對個數 (數學推導 + 枚舉因數)
問題描述 給定 n, m (1 ≤ n,m ≤ 10¹⁰),求有多少對正整數 (a,b) 使得 gcd(a,b)=n 且 lcm(a,b)=m。 數學轉化
整數二進制中 1 的個數統計:位運算與 Brian Kernighan 算法性能對比 (Java)
問題 計算 32 位整數二進制表示中 1 的個數。比較兩種方法的運行時間: 位運算並行累加法:利用掩碼分治 (0x55555555, 0x33333333 .
NYOJ 306 走迷宮 (DFS + 二分答案)
問題描述 N×N 迷宮 (2≤N≤100),每格有難度值 (0~120)。從左上角 (1,1) 走到右下角 (N,N),可上下左右移動。尋找一條路徑,使路徑上最
Lucene 搜索類實現:索引搜索與字符串匹配對比 (Java)
功能概述 實現一個搜索類 Search,提供兩種搜索方式: Lucene 索引搜索:利用 IndexSearcher、TermQuery 對已建立索引的文檔進
Codeforces 471C MUH and House of Cards (數學規律 + 枚舉)
問題描述 給定 n 張卡牌,搭建金字塔式結構:第 i 層需 2*i + (i-1) = 3i - 1 張牌。若搭建 k 層,總需 ∑(3i-1) = (3k+1
POJ 1742 多重背包可行性問題 (硬幣組合面值計數)
問題大意 有 n 種硬幣,面值 A[i],數量 C[i]。查詢 1~m 中有多少面值能被這些硬幣精確湊出(不找零)。n ≤ 100, m ≤ 100000, 多
HDU 1879 繼續暢通工程 (最小生成樹 Prim 算法)
問題描述 給定 N 個村莊 (1 < N < 100) 及其間所有可能道路的建設成本與是否已建成(1=已建,0=未建)。已建道路成本視為 0。求使所有村莊連通的
POJ 1548 Robots 最小路徑覆蓋 (二分圖最大匹配)
問題轉化 給定若干機器人坐標,機器人只能向右或向下移動。求最少需要多少條路徑覆蓋所有機器人(每條路徑從某機器人出發,沿右/下方向移動)。經典結論:最小路徑覆蓋
LeetCode 求和問題總結:2Sum, 3Sum, 4Sum, K Sum 通用解法
前言 LeetCode 中的 2Sum、3Sum、4Sum 及其變體(如 3Sum Closest)是經典面試題,核心考察排序後雙指針與去重技巧。本文將這些問題
POJ 2502 Subway 地鐵最短路徑 (Dijkstra 算法)
問題背景 你從安靜的郊區搬到大城市,上學需結合步行與搭乘地鐵。步行速度 10 km/h,地鐵速度 40 km/h。假設到達車站即有班車可搭乘,可任意換乘路線。給
HDU 1037 Keep on Truckin' 解題詳解
問題描述 Boudreaux 和 Thibodeaux 駕駛一輛 18 輪卡車運送貨物,路經三座地下通道。卡車高度為 168 英吋。輸入三個整數,分別代表三座地
UVA 10655 Contemplation! Algebra:矩陣快速冪求 a^n + b^n
問題描述 已知 p = a+b,q = ab,求 a^n + b^n。輸入多組 p,q,n,以 0 0 結束。結果保證 64 位有符號整數範圍內。 解題思路
HDU 1033 Edge:折紙展開曲線繪製
問題描述 一張長方形紙只沿短邊平行線折疊,每次折疊方向為 A(頂面合)或 V(底面合)。展開後看長邊形成折線,輸入折疊序列(如 AVV),輸出 PostScri
POJ 1719 Shooting Contest:二分匹配選白格子
問題描述 r 行 c 列矩陣,每列恰好兩個白格子。需每列選一個白格子,使每行至少被選一次。判斷是否可行,可行則輸出每列選擇的行號(多解任意)。 解題思路 r
POJ 1556 The Doors:計算幾何 + 最短路
問題描述 走廊寬 10,有 n 扇門,每扇門上下各有一個缺口(由兩條線段表示)。從左側 (0,5) 走到右側 (10,5),只能穿過門的缺口。求最短路徑長度。