Codeforces 196E Opening Portals:多源 SPFA + 克魯斯卡尔重構圖
問題描述 給定無向加權連通圖 n 點 m 邊,其中 k 個點有傳送門。起點為 1。玩家需走到所有傳送門點開啟它們。已開啟的傳送門之間可瞬移(代價 0)。求開啟所
HDU 1394 Minimum Inversion Number:線段樹求旋轉後最小逆序數
問題描述 給定一個由 1..n 排列組成的序列,允許將第一個元素移到末尾(循環左移)。求所有旋轉中逆序對數的最小值。n ≤ 5000。 核心規律:旋轉對逆序數
HDU 4920 Matrix Multiplication:位運算優化矩陣乘法模 3
問題描述 給定兩個 n×n 矩陣 A, B,求 C = (A × B) mod 3。n ≤ 800,元素值模 3 後僅有 0, 1, 2 三種。 優化思路:利
HDU 1285 確定比賽排名:基於入度的拓撲排序實現
問題描述 同 HDU 1285:給定 n 個頂點、m 條有向邊 a→b(表示 a 排在 b 前),輸出滿足條件的拓撲序列。若多解,編號小優先。 算法流程:入度
HDU 2795 Billboard:線段樹解決公告張貼問題
問題描述 有一塊高 h、寬 w 的宣傳欄。有 n 條公告,每條高 1、寬 lenᵢ。公告必須貼在「最上面、最靠左」的可用位置。判斷每條公告能否貼上,能則輸出其左
POJ 2827 Buy Tickets:線段樹解決插隊問題
問題描述 有 n 個人依次排隊買票。第 i 個人希望插到當前隊列的第 Posᵢ 個位置(0-based),並帶有值 Valᵢ。所有人按順序插入後,求最終隊列從前
HDU 1285 確定比賽名次:拓撲排序與優先隊列優化
問題描述 有 n 支隊伍,m 條比賽結果 a b 表示隊伍 a 勝過 b。要求輸出一個合法的排名序列,滿足:若存在從 u 到 v 的有向路徑,則 u 必須排在
POJ 2250 Compromise:單詞級最長公共子序列 (LCS)
問題描述 給定兩段文本,每段由若干小寫單詞組成,以 # 結束。要求找出兩段文本中最長公共子序列(LCS)的單詞序列。如果有多解,輸出任意一個即可。 解題思路:
HDU 4911 Inversion:利用歸並排序求逆序對的最小值
問題描述 給定一個長度為 n 的序列 a₁, a₂, …, aₙ,允許最多進行 k 次相鄰元素交換。請找出交換後可能達到的最小逆序對數量。逆序對定義為滿足 1
POJ 3934 Queue:動態規劃計算可見對數的排隊方案數
問題描述 n 個身高各不相同的孩子排隊。兩孩子可見 ⇔ 之間無孩子比他們更高(或無孩子)。求恰有 m 對可見孩子的排列數,模 9937。n ≤ 80, m ≤
POJ 3546 The Dragon of Loowater:貪心策略殺龍記
題目故事與模型 洛沃特王國有一條多頭龍,每顆頭有直徑 d_i;國內有 m 位騎士,身高 h_j。騎士身高 ≥ 龍頭直徑才能砍下該頭,代價 = 騎士身高(金幣)。
POJ 2245 Lotto:組合生成問題的 DFS 經典解法
題目大意 從 1~49 中選擇 k 個數字 (6 < k < 13) 組成集合 S,列出所有從 S 中選 6 個數字的組合。輸出需按字典序排序,測資間空一行,最
《資料結構與演算法分析》學習筆記(三):鏈表 ADT 完整實作
鏈表基礎概念 鏈表由一系列節點組成,每個節點包含資料域(存放元素值)與指標域(指向下一節點位址)。不同於陣列的連續記憶體,鏈表透過指標串聯離散節點,支援高效的插
C++ 拷貝構造函數與賦值運算符重載:核心區別、臨時對象陷阱與最佳實踐
C++ 拷貝構造函數與賦值運算符重載:核心區別、臨時對象陷阱與最佳實踐 這是 C++ 面試必考、工程必懂的核心知識點。本文通過 String 類實戰演示兩者區別
《數據結構與算法分析》學習筆記(二):算法分析與最大子序列和四種解法
《數據結構與算法分析》學習筆記(二):算法分析與最大子序列和四種解法 本章核心:掌握時間複雜度估算方法,通過「最大子序列和」問題展示從 O(N³) 到 O(N)
全排列遞歸算法深度解析:三種核心思路與代碼實現
全排列遞歸算法深度解析:三種核心思路與代碼實現 全排列是算法入門必學問題,也是面試高頻考點。給定 n 個互不相同的元素,輸出所有 n! 種排列。本文系統梳理三種
用陣列實現從檔案搜尋帳戶與驗證密碼:C++ 實戰教學
前言:為什麼選擇陣列而非結構體與鏈表? 最近有同學在開發銀行管理系統時遇到難題:如何從檔案中搜尋帳戶並驗證密碼?一般來說,高效的做法是使用鏈表搭配結構體,既節省
C++ 單例模式完整指南:從基礎到線程安全實現
C++ 單例模式完整指南:從基礎到線程安全實現 單例模式確保一個類在整個程序生命週期中只有一個實例,並提供全局訪問點。適用於線程池、緩存、日誌、設備驅動、資料庫