3.2k 字 3 分鐘

# 分治法 # 概念 什麼是分而治之法？ 針對一個有 n 筆輸入的問題，它的策略是把輸入分解成 k (1< k ≤ n) 個獨立的小集合，這導致原問題變成 k 個小問題。 小問題各自獨立地解決後產生各自的解，一共有 k 組解。 分而治之法最後必須將這 k 組解有系統地合併以產生原問題的解。 # 步驟 如果要處理的資料量已經夠少，那麼用直接的方式解決，否則，把輸入資料分解成兩個獨立的小集合 求出每一個小問題的解；並且 把這兩個小問題的解組合起來，成為原來的大問題的解。 以下有範例演示喔～～ # 例題 # d219: 00374 - Big Mod # 內容 計算 R =...
2.5k 字 2 分鐘

# 方法 跟窮舉超像，就是設法模擬出答案的狀況 跟窮舉差別就在 -> 狀況通常都比較複雜一點點，要再多考慮一下 # 例題 # c006: 10550 - Combination Lock # 內容 你今天的任務需要來開一個鎖（如右圖）。在鎖上有一個轉盤，上面有 40 個刻度（0 到 39 來代表）。開鎖的密碼由 3 個號碼組成，例如：15-25-8。要打開這種鎖要按照以下步驟： 順時鐘方向轉轉盤 2...
1.8k 字 2 分鐘

# 並查集 (Disjoint Set Union) # 基礎觀念 並查集是一種樹形的資料結構，用於處理不交集的 ** 合併 union 及查詢 find ** 問題。 並查集 可用於查詢網路中兩個節點的狀態， 這裡的網路是一個抽象的概念， 不僅僅指網際網路中的網路， 也可以是人際關係的網路、交通網路等。 並查集 除了可以用於查詢 網路 中兩個節點的狀態， 還可以用於數學中集合相關的操作， 如求兩個集合的並集等。 並查集 對於查詢兩個節點的 連線狀態...