HDU 3718 Similarity:KM 算法解字符映射最大匹配
問題建模 給定標準答案串(長 n),每行一個測試串。要求建立字符一對一映射,使相同位置字符匹配數最大。 構造二分圖:左側 26 個大寫字母(答案串字符),右側
HDOJ 1016 Prime Ring Problem:DFS 回溯構造素數環
問題描述 將 1..n(n < 20,n 為偶數)排成一環,相鄰兩數之和為素數,且第一位固定為 1。按字典序輸出所有方案。 DFS 回溯框架 預處理 pri
POJ 1673 三角形垂心:幾何證明與坐標計算
幾何問題重述 給定三角形 ABC,在每邊外部作正方形,連接正方形頂點得線段,取中點與對應三角形頂點連線並延長,三線交於一點。證明該點為三角形垂心,並求座標。
線性篩法求歐拉函數與素數表:O(n) 時間預處理 GCD 為素數的數對計數
問題轉化 求 1 ≤ x, y ≤ N 且 gcd(x, y) 為素數的有序數對個數。 令 g = gcd(x, y) 為素數 p,則 x = p·x, y =
HDU 3062 Party:2-SAT 模型與 Tarjan 強連通分量判斷可滿足性
問題轉化 每對夫妻為一組布爾變量 (x, x),互斥(不能同時真)。 矛盾關係建邊: A, B 不能同時選 → A ⇒ ¬B, B ⇒ ¬A; A, B 不能
HDU 3722 Card Game:KM 算法求最大權完美匹配
問題建模 給定 n 個字符串,每次選兩個不同串 a, b,得分為 a 的前綴與 b 的後綴的最長公共長度。每個串最多用一次,求最大總分。 構造二分圖:左、右兩側
《算法導論》第 13 章 紅黑樹:性質、旋轉、插入、刪除全解析與 C++ 實現
紅黑樹五大性質 節點非紅即黑; 根節點為黑; 葉子(NIL)為黑; 紅節點的孩子必為黑; 任一節點到其子孫葉子的所有路徑包含相同數目的黑節點(黑高一致)。
九度 1044 Pre-Post:前序後序確定 m 叉樹的子樹組合計數
問題分析 給定一棵 m 叉樹的前序遍歷與後序遍歷,求有多少棵不同的樹能產生這兩個遍歷序列。關鍵在於遞歸劃分子樹: 前序首字符 = 後序尾字符 = 根; 去掉根
C++ 多態的三大前提條件與運行時綁定實戰演示
多態的三個必要條件 存在繼承體系:必須有基類與派生類構成的繼承層次; 虛函數重寫:基類聲明 virtual 成員函數,派生類同名同參覆寫; 基類指針/引用調用
POJ 3230 Travel:動態規劃求旅行最大收益
問題描述 旅行者在 n 個城市間移動,共 m 天。每天可選擇留在原城或移動到另一城市,移動/停留需支付費用 mat[i][j](i==j 表示停留費用)。第 i
Codeforces 482C Game with Strings:狀壓 DP + 概率期望巧解
問題重述 給定 n 個長度為 m 的字符串,等概率隨機藏起一個。玩家每步等概率詢問一個未揭示的位置,直到能唯一確定藏起的字符串。求玩家的期望詢問步數。 約束:n
二叉搜索樹與並查集:核心操作、代碼實現與應用場景全解析
二叉搜索樹(BST) 二叉搜索樹是一種經典的動態數據結構,滿足:左子樹所有鍵值 < 根節點 < 右子樹所有鍵值。這一性質使得查找、插入、刪除操作在平
SPOJ 1476 Maximum Profit:最大權閉合子圖解析與 ISAP 最大流實現
問題背景:最大權閉合子圖 在圖論中,「最大權閉合子圖」是指在一個有向圖中,找到一個點權總和最大的閉合子圖。所謂閉合子圖,即若某個節點被選入子圖,則其所有出邊指向
C++ 函數完整教程:定義、調用、重載、模板、默認參數、遞歸與內聯
C++ 函數完整教程:定義、調用、重載、模板、默認參數、遞歸與內聯 函數基礎 程序模塊化核心,主函數調度各功能函數 庫函數(系統提供)vs 用戶自定義函數
編譯型語言函數調用深度解析(三):裸函數、調用約定與逆向實戰
編譯型語言函數調用深度解析(三):裸函數、調用約定與逆向實戰 裸函數 __declspec(naked) 無序言/結語:編譯器不生成 push ebp; m
wxWidgets wxStandardPaths:獲取系統標準路徑的實用工具類
wxWidgets wxStandardPaths:獲取系統標準路徑的實用工具類 應用場景 跨平台獲取系統標準目錄:文檔、應用數據、用戶數據、臨時、可執行文件
SDUTOJ 2482 二叉排序樹:構建並比較前序/後序遍歷判斷同構
SDUTOJ 2482 二叉排序樹:構建並比較前序/後序遍歷判斷同構 題目大意 給定字串構建二叉排序樹(BST)。輸入 n 個查詢字串,判斷每個字串構建的 B
POJ 2431 Expedition:貪心 + 優先隊列解決加油最少停靠數
POJ 2431 Expedition:貪心 + 優先隊列解決加油最少停靠數 題目大意 卡車距城鎮 L,初始油 P。路徑上 N (≤10,000) 個加油站,