RonChen

摘要： 在信息學競賽中，經常需要處理和比較字符串。例如，判斷兩個字符串是否相等，或者在一個字符串中查找另一個字符串。直接進行字符串操作（如逐字符比較）的時間開銷與字符串長度成正比，當字符串很長或數量很多時，這種方法可能會非常慢。 字符串哈希是一種將任意長度的字符串通過一個哈希函數映射成一個固定長度的整數（或 閱讀全文

摘要： “狀態壓縮動態規劃”中的狀態，通常與集合相關聯。集合本身具有確定性、互異性和無序性 3 個性質，這也就決定了集合只關心每個元素的存在狀態，而這通常可以使用 0 或者 1 表示存在或者不存在。例如，有 8 個物品，對這 8 個物品的選取方案，必然是某個子集。令 1 表示選了，0 表示沒選，那么像 10 閱讀全文

摘要： std::bitset 是 C++ 標準庫中的一個類模板，用于高效地處理固定大小的位序列。它就像一個“位”的數組，但提供了比普通數組更豐富的操作接口，并且在空間上進行了優化。 當需要處理一組布爾標志、進行位掩碼操作或實現某些對位操作要求較高的算法時，bitset 是一個非常強大和方便的工具。 要使用 閱讀全文

摘要： 圖像編碼 圖像是人對視覺感知的物質再現。圖像可以由光學設備獲取，如照相機、鏡子、望遠鏡及顯微鏡等；也可以人為創作，如手工繪畫。圖像可以記錄、保存在紙質媒介、膠片等對光信號敏感的介質上。隨著數字采集技術和信號處理理論的發展，越來越多的圖像以數字形式存儲。 數字圖像包括矢量圖形與位圖圖像。 在計算機圖形 閱讀全文

摘要： 加法原理：做一件事情，有 \(n\) 類辦法，第 \(1\) 類辦法有 \(m_1\) 種方法，第 \(2\) 類辦法有 \(m_2\) 種方法，第 \(n\) 類辦法有 \(m_n\) 種方法，則完成這件事情的辦法有 \(m_1+m_2+\cdots+m_n\) 種。 加法原理屬于分類計數原理，分 閱讀全文

摘要： 復雜度分析 同一問題可能存在多種算法，而在實際運用中，往往要根據情況選擇某方面最優或者最合適的算法。為此，需要對有關算法的性能進行分析和比較。目前一般用算法執行過程所耗用的計算資源總量作為算法性能的衡量指標。時間資源和空間資源是最主要的兩種計算資源。已知輸入數據的規模，可以用時間復雜度來大致地度量算 閱讀全文

摘要： 例題：P1226 【模板】快速冪 給定三個整數 \(a,b,p\)，求 \(a^b \bmod p\)。\(0 \le a,b \le 2^{31}, \ a+b \gt 0, \ 2 \le p \lt 2^{31}\)。 最樸素的想法是直接用一個循環，將 \(a\) 連乘 \(b\) 次，每次乘 閱讀全文

摘要： STL set 例題：P5250 【深基17.例5】木材倉庫 分析：這個問題可以抽象為：維護一個集合，可以插入一個元素 \(x\)，同時判斷 \(x\) 是否已經存在；查詢 \(x\) 的前驅后繼，\(x\) 的前驅定義為小于 \(x\) 的最大的數，\(x\) 的后繼定義為大于 \(x\) 的最小 閱讀全文

摘要： 先看一個經典的“爬樓梯問題”，假設正在爬一個 \(n\) 階的樓梯，每次可以爬 \(1\) 階或 \(2\) 階。請問，總共有多少種不同的方法可以爬到樓頂？ 例如： \(1\) 階樓梯：只有一種方法（爬 \(1\) 階） \(2\) 階樓梯：有 \(2\) 種方法（爬 \(1+1\) 階，或直接爬 閱讀全文

摘要： 雙指針算法并不是一個具體的、單一的算法嗎，而是一種算法思想和技巧。它通過在數據結構上維護兩個指針，并讓它們按照一定的規則進行移動，從而在一次遍歷中解決問題。 核心目標：雙指針的主要目標是優化時間復雜度。通過巧妙地移動兩個指針，它能將許多問題中樸素解法的復雜度降低到 \(O(n)\)。它通過減少不必要 閱讀全文