演算法與資料結構模板:Python 版

依據原始文章的主題架構,以 Python 重新設計與撰寫。說明文字、介面與實作均為重新整理;預設 Python 3.11+。

使用約定

  • 陣列與圖的節點預設為 0-indexed;Fenwick Tree 內部使用 1-indexed。
  • 無限大使用 INF = 10**30,可依題目資料範圍調整。
  • 圖的鄰接串列:無權圖為 graph[u] = [v, ...];加權圖為 graph[u] = [(v, w), ...]。
  • Python 遞迴深度有限。深樹優先用迭代 DFS;需要遞迴時再提高 sys.setrecursionlimit。
  • 模板中的型別標註可刪除,不影響執行。

基礎模組

競程常用的標準函式庫:

import sys
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right, insort
from heapq import heappop, heappush, heapify
from itertools import accumulate, permutations
from math import gcd, inf, isqrt

各模組的常見用途:

  • sys:高速輸入輸出、調整遞迴深度。
  • Counter:統計每個元素出現幾次。
  • defaultdict:存取不存在的 key 時,自動建立預設值。
  • deque:可從左右兩端 O(1) 加入或刪除,常用於 BFS、0-1 BFS、單調佇列。
  • bisect_left:在已排序陣列中找第一個 >= target 的位置。
  • bisect_right:在已排序陣列中找第一個 > target 的位置。
  • insort:插入元素並維持排序;搜尋位置是 O(log n),但串列搬移仍是 O(n)。
  • heappush、heappop、heapify:最小堆,常用於 Dijkstra、貪心與工作排程。
  • accumulate:累積運算,最常用來建立前綴和。
  • permutations:枚舉排列。
  • gcd:最大公因數。
  • inf:浮點正無限大;純整數題也常用 10**30 代表無限大。
  • isqrt:整數平方根,不會有浮點誤差。

競程基本骨架

import sys

input = sys.stdin.readline  # 比一般 input() 更適合大量逐行輸入
INF = 10**30               # 足夠大的整數,常用於最短路或 DP
MOD = 1_000_000_007        # 常見取模值,題目未要求時不用


def solve():
    # 主要解題程式寫在這裡
    pass


if __name__ == "__main__":
    # 直接執行這個檔案時才呼叫 solve()
    solve()

快速讀取全部整數

import sys

it = iter(map(int, sys.stdin.buffer.read().split()))
n = next(it)
values = [next(it) for _ in range(n)]

拆解

sys.stdin.buffer.read() 會一次把標準輸入的全部內容讀進來。

例如輸入:

5
10 20 30 40 50

讀進來的內容大致是:

b'5\n10 20 30 40 50\n'

前面的 b 表示資料是 bytes,也就是位元組資料。因為這裡只要讀整數,不必先把整份輸入解碼成一般字串,所以通常比逐行呼叫 input() 更快。

接著呼叫 .split(),它會按照空白、換行和 Tab 切開:

[b'5', b'10', b'20', b'30', b'40', b'50']

map(int, ...) 再把每一項轉成整數,概念上會得到:

5, 10, 20, 30, 40, 50

iter(...) 把這串數字變成 iterator(迭代器):

it = iter(...)

iterator 可以想成「記住目前讀到哪裡的取號器」。每呼叫一次 next(it),就拿出下一個數字,並自動往後移一格。

n = next(it)

第一次取出的數字是 5,所以:

n = 5

此時 iterator 的位置變化可以想成:

5 -> 10 -> 20 -> 30 -> 40 -> 50
     ^
   下一個

最後這行:

values = [next(it) for _ in range(n)]

因為 n = 5,等同於:

values = []
for _ in range(5):
    values.append(next(it))

它會依序取出 10、20、30、40、50,最後得到:

values = [10, 20, 30, 40, 50]

整段程式的用途

這段高速輸入:

it = iter(map(int, sys.stdin.buffer.read().split()))
n = next(it)
values = [next(it) for _ in range(n)]

在這個輸入格式下,相當於較直觀的逐行版本:

n = int(input())
values = list(map(int, input().split()))

差別在於逐行版每次只讀一行;sys.stdin.buffer.read() 則一次把全部輸入讀完。資料量很大時,整批讀取通常比較快;一般小題目則可優先使用較容易閱讀的 input()。

注意:使用 read() 後,全部輸入已經一次取走。後面應繼續用同一個 iterator 讀資料,不要再混用 input()。

資料結構

BIT(Fenwick Tree/樹狀陣列)

支援單點加值、前綴和與區間和;更新、查詢皆為 O(log n),空間 O(n)。公開索引採 0-indexed。

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
        self.values = [0] * n

    def add(self, index, delta):
        self.values[index] += delta
        i = index + 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def prefix_sum(self, right):
        """回傳 [0, right) 的總和。"""
        total = 0
        i = right
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def range_sum(self, left, right):
        """回傳 [left, right) 的總和。"""
        return self.prefix_sum(right) - self.prefix_sum(left)

    def set(self, index, value):
        self.add(index, value - self.values[index])

    def lower_bound(self, target):
        """所有值非負時,找最小 i,使 prefix_sum(i + 1) >= target。"""
        if target <= 0:
            return 0
        index = 0
        step = 1 << (self.n.bit_length() - 1)
        while step:
            nxt = index + step
            if nxt <= self.n and self.tree[nxt] < target:
                index = nxt
                target -= self.tree[nxt]
            step >>= 1
        return index
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

FenwickTree(n) 會建立三個重要欄位:

  • self.n:元素總數。
  • self.values:保存每個位置目前的真實值,讓 set() 能計算差值。
  • self.tree:Fenwick Tree 本體。它多開一格,內部索引使用 1 到 n。

add(index, delta) 的外部 index 是 0-indexed,所以先執行 i = index + 1。接著:

i += i & -i

i & -i 會取出 i 最低位的 1,代表目前節點負責的區間長度。每次加上它,就會跳到下一個包含此位置的父節點。

prefix_sum(right) 計算半開區間 [0, right)。它反向執行:

i -= i & -i

每次移除最低位的 1,把數個互不重疊的區間加起來。於是 [left, right) 可寫成「右前綴減左前綴」。

例如陣列為 [3, 1, 4, 2]:

bit.range_sum(1, 4)

等同計算 1 + 4 + 2 = 7。

set(index, value) 不是直接把樹節點設成 value,而是先求:

delta = value - self.values[index]

再用 add() 把差值更新進去。

複雜度: add()、prefix_sum()、range_sum()、set() 都是 O(log n);空間 O(n)。

容易出錯: 公開介面是 0-indexed,樹內部是 1-indexed;不要把兩者混在一起。

<!-- END ALGORITHM EXPLANATION -->

Segment Tree(迭代式線段樹)

可自訂合併運算。建樹 O(n),單點更新與區間查詢 O(log n);區間採半開 [left, right)。

class SegmentTree:
    def __init__(self, data, operation=min, identity=10**30):
        self.operation = operation
        self.identity = identity
        self.size = 1
        while self.size < len(data):
            self.size <<= 1
        self.tree = [identity] * (2 * self.size)
        self.tree[self.size:self.size + len(data)] = data
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = operation(self.tree[i << 1], self.tree[i << 1 | 1])

    def set(self, index, value):
        i = self.size + index
        self.tree[i] = value
        i >>= 1
        while i:
            self.tree[i] = self.operation(self.tree[i << 1], self.tree[i << 1 | 1])
            i >>= 1

    def query(self, left, right):
        left += self.size
        right += self.size
        result_left = self.identity
        result_right = self.identity
        while left < right:
            if left & 1:
                result_left = self.operation(result_left, self.tree[left])
                left += 1
            if right & 1:
                right -= 1
                result_right = self.operation(self.tree[right], result_right)
            left >>= 1
            right >>= 1
        return self.operation(result_left, result_right)
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

線段樹把陣列區間不斷切成左右兩半。self.size 會擴充到不小於原陣列長度的最小 2 次方,這樣每個節點都能有完整的左右子節點。

self.tree[self.size:self.size + len(data)] = data

葉節點從 self.size 開始放。接著由下往上合併:

self.tree[i] = operation(self.tree[i << 1], self.tree[i << 1 | 1])
  • i << 1 等同 i * 2,是左子節點。
  • i << 1 | 1 等同 i * 2 + 1,是右子節點。
  • operation 可以是 min、max、加法或其他可結合的運算。

set(index, value) 先修改葉節點,再一路除以 2 回到根節點,重新計算沿途答案。

query(left, right) 查詢半開區間 [left, right):

  • 若 left 是右子節點,代表它不能和左邊兄弟一起取,所以先收進答案,再右移。
  • 若 right 是右邊界,先往左移一格;該節點代表的完整區間可收進答案。
  • 之後兩端一起除以 2,往上一層繼續。

例如:

tree = SegmentTree([5, 2, 7, 1], min, 10**30)
tree.query(1, 4)  # min([2, 7, 1]),結果為 1

複雜度: 建樹 O(n);單點更新和區間查詢 O(log n);空間 O(n)。

容易出錯: identity 必須是運算的單位元素。求最小值用正無限大,求最大值用負無限大,求總和用 0。

<!-- END ALGORITHM EXPLANATION -->

Sparse Table(稀疏表)

適合靜態、具冪等性的區間運算,例如 min、max、gcd。建表 O(n log n),查詢 O(1)。

class SparseTable:
    def __init__(self, data, operation=min):
        if not data:
            raise ValueError("data must not be empty")
        self.operation = operation
        n = len(data)
        self.log = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log[i] = self.log[i >> 1] + 1
        self.table = [data[:]]
        k = 1
        while (1 << k) <= n:
            half = 1 << (k - 1)
            previous = self.table[-1]
            self.table.append([
                operation(previous[i], previous[i + half])
                for i in range(n - (1 << k) + 1)
            ])
            k += 1

    def query(self, left, right):
        k = self.log[right - left]
        return self.operation(
            self.table[k][left],
            self.table[k][right - (1 << k)],
        )
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

Sparse Table 適合「陣列不再修改,但要查很多次區間」的情況。

self.table[k][i] 表示:從 i 開始、長度為 2**k 的區間答案。

table[0][i]:長度 1
table[1][i]:長度 2
table[2][i]:長度 4
table[3][i]:長度 8

長度 2**k 可由兩段長度 2**(k-1) 合併:

operation(previous[i], previous[i + half])

查詢 [left, right) 時,先找不超過區間長度的最大 2 次方:

k = self.log[right - left]

接著取「從左端開始」與「到右端結束」的兩段。這兩段可能重疊,但 min、max、gcd 重複計算同一元素不會改變答案,所以可以 O(1) 查詢。

例如長度為 6 的區間,可用兩段長度 4 覆蓋;中間重疊沒有關係。

複雜度: 前處理 O(n log n),每次查詢 O(1),空間 O(n log n)。

容易出錯: 一般加法不能用這種重疊查詢,因為重疊元素會被加兩次。區間也不能為空。

<!-- END ALGORITHM EXPLANATION -->

DSU(Disjoint Set Union/並查集)

路徑壓縮搭配按大小合併,均攤近似 O(1)。

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.components -= 1
        return True

    def same(self, a, b):
        return self.find(a) == self.find(b)

    def component_size(self, x):
        return self.size[self.find(x)]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

DSU 用來維護「哪些元素屬於同一組」。一開始每個元素自己是一組:

self.parent = list(range(n))
self.size = [1] * n

find(x) 沿著 parent 找到集合代表。這行是路徑壓縮:

self.parent[x] = self.parent[self.parent[x]]

它把 x 直接接到祖父節點,使之後的查詢路徑更短。

union(a, b) 先找到兩個集合的代表。若相同,表示已經連通,回傳 False。不同時,將小集合接到大集合:

if self.size[a] < self.size[b]:
    a, b = b, a
self.parent[b] = a

這叫做「按大小合併」,可避免樹變得很深。

例如依序合併 (0, 1)、(2, 3)、(1, 3) 後,0、1、2、3 都會屬於同一組,而 component_size(2) 會得到 4。

複雜度: 搭配路徑壓縮與按大小合併後,單次操作均攤為 O(α(n)),實務上近似常數。

常見用途: Kruskal 最小生成樹、連通性查詢、離線加邊、判斷加入一條邊是否形成環。

<!-- END ALGORITHM EXPLANATION -->

Monotone Stack(單調棧)

找每個位置右側第一個嚴格較小元素,總時間 O(n)。改變比較符號即可處理「較大」或允許相等的版本。

def next_smaller_indices(values):
    answer = [-1] * len(values)
    stack: list[int] = []
    for i, value in enumerate(values):
        while stack and values[stack[-1]] > value:
            answer[stack.pop()] = i
        stack.append(i)
    return answer


def largest_rectangle(heights):
    best = 0
    stack: list[tuple[int, int]] = []
    for i, height in enumerate(heights + [0]):
        start = i
        while stack and stack[-1][1] > height:
            index, old_height = stack.pop()
            best = max(best, old_height * (i - index))
            start = index
        if not stack or stack[-1][1] < height:
            stack.append((start, height))
    return best
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

next_smaller_indices() 的 stack 保存「還沒找到右側較小值」的索引,而且對應數值維持單調不減。

掃描到新值 value 時:

while stack and values[stack[-1]] > value:
    answer[stack.pop()] = i

若棧頂比新值大,代表新值就是棧頂右側第一個較小元素。索引被彈出後不會再進棧,因此所有元素總共只進出一次。

例如 [4, 2, 5, 1]:

  • 4 遇到 2,答案是索引 1。
  • 2 和 5 遇到 1,答案都是索引 3。
  • 1 右側沒有更小值,保留 -1。

largest_rectangle() 的棧保存 (最早起點, 高度)。遇到較矮柱子時,表示較高柱子的矩形不能再向右延伸,因此立刻計算:

old_height * (i - index)

最後附加的 0 是哨兵,強迫所有剩餘高度出棧,不必在迴圈後再寫一次清理。

複雜度: 兩個模板都是 O(n) 時間、O(n) 空間。

容易出錯: > 和 >= 對重複值的處理不同;題目要求嚴格較小、較小或相等時要調整比較符號。

<!-- END ALGORITHM EXPLANATION -->

Monotone Deque(單調雙端佇列)

滑動視窗最大值為 O(n);佇列存索引,便於移除過期元素。

from collections import deque


def sliding_window_maximum(values, k):
    if k <= 0 or k > len(values):
        return []
    queue: deque[int] = deque()
    answer = []
    for i, value in enumerate(values):
        while queue and queue[0] <= i - k:
            queue.popleft()
        while queue and values[queue[-1]] <= value:
            queue.pop()
        queue.append(i)
        if i + 1 >= k:
            answer.append(values[queue[0]])
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

佇列中保存索引而不是值,因為索引可以判斷元素是否已離開視窗。

每次處理索引 i 時先移除過期元素:

while queue and queue[0] <= i - k:
    queue.popleft()

接著從右側刪掉不可能再成為最大值的元素:

while queue and values[queue[-1]] <= value:
    queue.pop()

若舊值小於或等於新值,新值不但比較大,而且活得更久,所以舊值永遠不可能成為未來視窗的最大值。

例如 values = [1, 3, 2, 5]、k = 3:

  • 視窗 [1, 3, 2] 的最大值是 3。
  • 視窗向右移成 [3, 2, 5];加入 5 時會從右側移除 2 和 3,最大值變成 5。

佇列左端永遠是目前視窗最大值的索引。

複雜度: 每個索引最多進出佇列一次,總時間 O(n),空間 O(k)。

<!-- END ALGORITHM EXPLANATION -->

圖論

BFS(廣度優先搜尋)

無權圖最短距離為 O(V + E)。

from collections import deque


def bfs(graph, source):
    n = len(graph)
    distance = [-1] * n
    parent = [-1] * n
    distance[source] = 0
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if distance[v] == -1:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    return distance, parent


def restore_path(parent, target):
    path = []
    while target != -1:
        path.append(target)
        target = parent[target]
    return path[::-1]

網格 BFS:

def grid_bfs(grid, start):
    rows, columns = len(grid), len(grid[0])
    distance = [[-1] * columns for _ in range(rows)]
    sr, sc = start
    distance[sr][sc] = 0
    queue = deque([start])
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while queue:
        row, column = queue.popleft()
        for dr, dc in directions:
            nr, nc = row + dr, column + dc
            if (0 <= nr < rows and 0 <= nc < columns
                    and grid[nr][nc] != "#" and distance[nr][nc] == -1):
                distance[nr][nc] = distance[row][column] + 1
                queue.append((nr, nc))
    return distance
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

第一段程式處理無權圖。distance 初始為 -1,同時代表「尚未造訪」;起點距離設成 0。

BFS 使用 FIFO 佇列:先進去的節點先處理,所以會按距離 0、1、2、... 一層一層向外擴張。第一次到達某節點時,就是最少邊數的路徑。

distance[v] = distance[u] + 1
parent[v] = u

parent[v] 記錄「從哪個節點走到 v」,因此 restore_path() 可從終點沿父節點倒走,再把結果反轉。

例如邊為 0-1、0-2、1-3,從 0 開始:

distance = [0, 1, 1, 2]

第二段 grid_bfs() 把每個格子視為節點,只嘗試上下左右四個方向。條件同時檢查:

  • 新座標沒有超出矩陣。
  • 不是牆壁 #。
  • 還沒被造訪。

複雜度: 一般圖 O(V + E);rows × columns 網格為 O(rows × columns)。

容易出錯: 將節點放入佇列時就要立刻標記距離,不能等取出時才標記,否則同一節點可能重複入列。

<!-- END ALGORITHM EXPLANATION -->

0-1 BFS

邊權只能是 0 或 1。權重 0 的節點推到左側,權重 1 推到右側,時間 O(V + E)。

def zero_one_bfs(graph, source):
    distance = [10**30] * len(graph)
    distance[source] = 0
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v, weight in graph[u]:
            candidate = distance[u] + weight
            if candidate < distance[v]:
                distance[v] = candidate
                if weight == 0:
                    queue.appendleft(v)
                else:
                    queue.append(v)
    return distance
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

0-1 BFS 只適用邊權為 0 或 1 的圖。它與 Dijkstra 的概念相似,但不需要 heap。

若走一條權重 0 的邊,距離沒有增加,應優先處理:

queue.appendleft(v)

若權重是 1,距離增加一,放到右端:

queue.append(v)

因此 deque 內的節點會大致依距離由小到大排列。

例如 0 -> 1 權重 1,0 -> 2 權重 0,2 -> 1 權重 0。雖然直接到 1 的成本是 1,但 2 會被放到左端優先處理,最後找到 0 -> 2 -> 1,成本為 0。

if candidate < distance[v]:
    ...  # 找到更短路徑時才更新

只有找到更短距離才更新,避免無意義的重複加入。

複雜度: O(V + E) 時間、O(V) 額外空間。

容易出錯: 若邊權出現 2、負數或其他值,就不能使用這個模板。

<!-- END ALGORITHM EXPLANATION -->

DFS(深度優先搜尋)

def iterative_dfs(graph, source):
    visited = [False] * len(graph)
    order = []
    stack = [source]
    while stack:
        u = stack.pop()
        if visited[u]:
            continue
        visited[u] = True
        order.append(u)
        for v in reversed(graph[u]):
            if not visited[v]:
                stack.append(v)
    return order
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

DFS 會沿一條路盡量走到底,再回頭探索其他分支。此版本用 stack 模擬遞迴,因此不會遇到 Python 遞迴深度限制。

u = stack.pop()

串列尾端是棧頂,後放入的節點會先被處理。若節點已造訪就略過;否則標記並加入 order。

for v in reversed(graph[u]):
    ...  # 反向推入棧,維持預期的走訪順序

反轉鄰居只是為了讓迭代版的造訪順序接近遞迴版。假設鄰居是 [1, 2, 3],反向推入棧後,1 會最先被取出。

小例子: 0 連到 1、2,1 再連到 3。依鄰接串列順序,結果可能是 [0, 1, 3, 2]。

複雜度: O(V + E) 時間、最壞 O(V) 空間。

常見用途: 連通元件、拓撲概念、樹遍歷、環偵測、Euler Tour。

<!-- END ALGORITHM EXPLANATION -->

Dijkstra(非負權最短路徑)

使用二元堆,時間 O((V + E) log V)。含負權邊時不能使用。

from heapq import heappop, heappush


def dijkstra(graph, source):
    n = len(graph)
    distance = [10**30] * n
    parent = [-1] * n
    distance[source] = 0
    heap = [(0, source)]
    while heap:
        current_distance, u = heappop(heap)
        if current_distance != distance[u]:
            continue
        for v, weight in graph[u]:
            candidate = current_distance + weight
            if candidate < distance[v]:
                distance[v] = candidate
                parent[v] = u
                heappush(heap, (candidate, v))
    return distance, parent
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

distance[v] 保存目前找到的最短距離,heap 保存 (距離, 節點)。Python tuple 會先比較第一項,所以距離最小的狀態最先被取出。

current_distance, u = heappop(heap)

同一節點可能因為後來找到更短路徑而被重複放進 heap。這段會丟掉過期狀態:

if current_distance != distance[u]:
    continue

對每條 u -> v、權重 weight 的邊做鬆弛:

candidate = current_distance + weight
if candidate < distance[v]:
    ...  # 更新 distance、parent,再推入 heap

若新距離更短,就更新 distance[v]、記錄 parent[v] = u,再把新狀態推入 heap。

例如 0 -> 1 成本 5,0 -> 2 成本 1,2 -> 1 成本 2。演算法會把到 1 的答案從 5 改成 3。

複雜度: 使用鄰接串列與二元堆時為 O((V + E) log V)。

容易出錯: 不能有負權邊;若有負權邊應考慮 Bellman–Ford 或其他方法。

<!-- END ALGORITHM EXPLANATION -->

Floyd–Warshall(全源最短路)

時間 O(n^3)、空間 O(n^2);可處理負權邊,但若 distance[i][i] < 0 代表存在負環。

def floyd_warshall(matrix):
    distance = [row[:] for row in matrix]
    n = len(distance)
    for k in range(n):
        for i in range(n):
            if distance[i][k] >= 10**30:
                continue
            dik = distance[i][k]
            for j in range(n):
                distance[i][j] = min(distance[i][j], dik + distance[k][j])
    return distance
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

distance[i][j] 表示從 i 到 j 的目前最短距離。初始化時:

  • distance[i][i] = 0。
  • 有直接邊就填邊權。
  • 沒有邊填 INF。

三層迴圈的最外層 k 表示:現在允許使用編號 0..k 的節點作為中繼點。

distance[i][j] = min(
    distance[i][j],
    distance[i][k] + distance[k][j],
)

也就是比較「原本的路」與「先走到 k、再從 k 走到 j」哪個比較短。

例如原本 0 -> 2 成本 10,但 0 -> 1 成本 3、1 -> 2 成本 4,當 k = 1 時答案會更新成 7。

複雜度: O(n³) 時間、O(n²) 空間,適合節點數較小但需要大量任意兩點查詢的題目。

負環判斷: 完成後若任何 distance[i][i] < 0,表示存在可到達的負權環。

<!-- END ALGORITHM EXPLANATION -->

Topological Sort(Kahn 拓撲排序)

只適用有向無環圖;若結果少於 n 個節點,圖中存在環。

def topological_sort(graph):
    indegree = [0] * len(graph)
    for edges in graph:
        for v in edges:
            indegree[v] += 1
    queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

拓撲排序只適用有向無環圖。indegree[v] 表示有多少條邊指向 v,也就是還有多少先決條件尚未完成。

先把所有入度為 0 的節點加入佇列:

queue = deque(i for i, degree in enumerate(indegree) if degree == 0)

每取出一個節點 u,就視為已完成它,並刪除它指向鄰居的影響:

indegree[v] -= 1

若某鄰居的入度降到 0,代表其所有前置節點都已完成,可以加入佇列。

例如依賴關係 0 -> 2、1 -> 2,一開始 0、1 都可處理;兩者完成後 2 才能進入答案。

若最後 order 少於節點總數,代表剩下節點互相依賴,圖中存在環,所以回傳 None。

複雜度: O(V + E)。

延伸: 若題目要求字典序最小的拓撲序,可把 deque 改成最小堆。

<!-- END ALGORITHM EXPLANATION -->

Kruskal(最小生成樹)

邊格式為 (weight, u, v);時間 O(E log E)。若最後選不到 n - 1 條邊,圖不連通。

def kruskal(n, edges):
    dsu = DSU(n)
    total = 0
    chosen = []
    for weight, u, v in sorted(edges):
        if dsu.union(u, v):
            total += weight
            chosen.append((u, v, weight))
    return (total, chosen) if len(chosen) == n - 1 else None
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

Kruskal 的貪心策略是:從權重最小的邊開始考慮,只要不形成環就選入。

for weight, u, v in sorted(edges):
    ...  # 依邊權由小到大處理

邊使用 (weight, u, v),因此 Python 排序會優先依權重由小到大。

if dsu.union(u, v):
    ...  # 合併成功代表加入此邊不會形成環

若 u 和 v 原本不在同一集合,union() 會成功,表示加入此邊不會形成環;接著累加權重並記錄選中的邊。若原本已連通,加入它一定會形成環,所以略過。

一棵含 n 個節點的生成樹必須剛好有 n - 1 條邊。若最後不足,代表原圖不連通,無法建立生成樹。

複雜度: 排序為 O(E log E);DSU 操作近似常數。

容易出錯: 無向邊只需放一次進 edges;若題目要最大生成樹,可改成依權重由大到小排序。

<!-- END ALGORITHM EXPLANATION -->

LCA(最近公共祖先/Binary Lifting)

前處理 O(n log n),每次查詢 O(log n)。

class LCA:
    def __init__(self, tree, root = 0):
        n = len(tree)
        self.log = max(1, n.bit_length())
        self.depth = [-1] * n
        self.up = [[root] * n for _ in range(self.log)]
        self.depth[root] = 0
        stack = [root]
        while stack:
            u = stack.pop()
            for v in tree[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    self.up[0][v] = u
                    stack.append(v)
        for bit in range(1, self.log):
            previous = self.up[bit - 1]
            self.up[bit] = [previous[previous[v]] for v in range(n)]

    def kth_ancestor(self, node, steps):
        bit = 0
        while steps:
            if steps & 1:
                node = self.up[bit][node]
            steps >>= 1
            bit += 1
        return node

    def query(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a
        a = self.kth_ancestor(a, self.depth[a] - self.depth[b])
        if a == b:
            return a
        for bit in range(self.log - 1, -1, -1):
            if self.up[bit][a] != self.up[bit][b]:
                a, b = self.up[bit][a], self.up[bit][b]
        return self.up[0][a]

    def distance(self, a, b):
        ancestor = self.query(a, b)
        return self.depth[a] + self.depth[b] - 2 * self.depth[ancestor]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

up[bit][v] 表示節點 v 往上跳 2**bit 步後到達的祖先。

前處理先用 DFS 建立:

  • depth[v]:節點深度。
  • up[0][v]:直接父節點。

再用:

self.up[bit][v] = previous[previous[v]]

求出 2、4、8、... 步祖先。

查詢 query(a, b) 分兩階段:

  1. 若深度不同,先把較深節點往上跳,使兩者同一深度。
  2. 從最大 bit 往下檢查;若兩者跳 2**bit 步後仍不同,就一起跳。最後兩者的父節點就是 LCA。

例如 0 是根,1、2 是其孩子,3、4 是 1 的孩子:LCA(3, 4) = 1,LCA(3, 2) = 0。

距離公式為:

depth[a] + depth[b] - 2 * depth[lca]

複雜度: 前處理 O(n log n);每次 LCA 或第 k 個祖先查詢 O(log n)。

<!-- END ALGORITHM EXPLANATION -->

Binary Lifting(通用倍增)

class BinaryLifting:
    def __init__(self, next_node, max_steps):
        levels = max(1, max_steps.bit_length())
        self.jump = [next_node[:]]
        for _ in range(1, levels):
            previous = self.jump[-1]
            self.jump.append([previous[previous[x]] for x in range(len(next_node))])

    def move(self, node, steps):
        bit = 0
        while steps:
            if steps & 1:
                node = self.jump[bit][node]
            bit += 1
            steps >>= 1
        return node
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

這個模板不限定是樹。只要每個狀態都有唯一的下一個狀態 next_node[x],就能快速跳很多步。

self.jump[0][x] = next_node[x]

代表跳 1 步;下一層透過跳兩次前一層建立:

previous[previous[x]]

因此 jump[1] 是 2 步、jump[2] 是 4 步、jump[3] 是 8 步。

move(node, steps) 把 steps 拆成二進位。例如 13 = 8 + 4 + 1,只需使用第 3、2、0 層,各跳一次。

if steps & 1:
    node = self.jump[bit][node]

每次處理最低位後右移 steps。

複雜度: 前處理 O(n log K),查詢 O(log K),其中 K 是最大步數。

常見用途: 函數圖跳躍、祖先查詢、重複狀態轉移。

<!-- END ALGORITHM EXPLANATION -->

Bipartite Check(二分圖判定)

def bipartite_coloring(graph):
    color = [-1] * len(graph)
    for source in range(len(graph)):
        if color[source] != -1:
            continue
        color[source] = 0
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    queue.append(v)
                elif color[v] == color[u]:
                    return None
    return color
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

二分圖可以把每個節點塗成 0 或 1,且每條邊的兩端顏色都不同。

color = [-1] * n 中的 -1 表示尚未染色。因為圖可能不連通,所以外層迴圈會從每個尚未染色的節點開始一次 BFS。

color[v] = color[u] ^ 1

XOR 1 會把 0 變 1、1 變 0,因此鄰居會得到相反顏色。

若遇到已染色鄰居,而且:

color[v] == color[u]

表示一條邊的兩端同色,無法二分,立即回傳 None。

例如三角形 0-1-2-0 無法使用兩色完成,因為第三條邊必定連接相同顏色;偶數長度環則可以二分。

複雜度: O(V + E)。

常見判斷: 無向圖是二分圖,等價於圖中沒有奇數長度環。

<!-- END ALGORITHM EXPLANATION -->

Cycle Detection(環偵測)

有向圖使用三色標記;0 未造訪、1 搜尋中、2 已完成。

def has_directed_cycle(graph):
    color = [0] * len(graph)

    def visit(start):
        stack = [(start, 0)]
        color[start] = 1
        while stack:
            u, edge_index = stack[-1]
            if edge_index == len(graph[u]):
                color[u] = 2
                stack.pop()
                continue
            v = graph[u][edge_index]
            stack[-1] = (u, edge_index + 1)
            if color[v] == 1:
                return True
            if color[v] == 0:
                color[v] = 1
                stack.append((v, 0))
        return False

    return any(color[u] == 0 and visit(u) for u in range(len(graph)))


def has_undirected_cycle(graph):
    visited = [False] * len(graph)
    for source in range(len(graph)):
        if visited[source]:
            continue
        visited[source] = True
        stack = [(source, -1)]
        while stack:
            u, parent = stack.pop()
            for v in graph[u]:
                if not visited[v]:
                    visited[v] = True
                    stack.append((v, u))
                elif v != parent:
                    return True
    return False
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

有向圖版本使用三種顏色:

  • 0:尚未造訪。
  • 1:正在目前 DFS 路徑中。
  • 2:此節點及其後續都已處理完成。

迭代棧保存 (節點, 下一條要看的邊索引),用來模擬遞迴進入與返回。

若從 u 看見 color[v] == 1,表示邊指回目前路徑上的祖先,這是一條 back edge,因此存在有向環。

無向圖版本則保存 (u, parent)。看到已造訪的鄰居時,如果它不是父節點,就表示從另一條路回到舊節點,形成環。

例如無向邊 0-1、1-2、2-0:從 2 看見已造訪且不是父節點的 0,即可判定有環。

複雜度: 兩個版本皆為 O(V + E)。

容易出錯: 有向圖不能只用一般 visited;必須區分「仍在目前路徑」和「已經完成」。

<!-- END ALGORITHM EXPLANATION -->

Tree Diameter(樹直徑)

無權樹做兩次 BFS。

def tree_diameter(tree):
    def farthest(source):
        distance = [-1] * len(tree)
        distance[source] = 0
        queue = deque([source])
        while queue:
            u = queue.popleft()
            for v in tree[u]:
                if distance[v] == -1:
                    distance[v] = distance[u] + 1
                    queue.append(v)
        node = max(range(len(tree)), key=distance.__getitem__)
        return node, distance

    a, _ = farthest(0)
    b, distance = farthest(a)
    return distance[b], a, b
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

樹直徑是樹上兩節點間的最長簡單路徑。無權樹可以用兩次 BFS:

  1. 從任意節點(程式用 0)出發,找到最遠節點 a。
  2. 再從 a 出發,找到最遠節點 b。
  3. distance[b] 就是直徑長度,a、b 是直徑兩端。

為什麼有效:第一次 BFS 找到的最遠節點一定可以作為某條直徑的端點;從它再找最遠點,就會到達另一端。

例如鏈狀樹 0-1-2-3:從 0 找到最遠的 3,再從 3 找到最遠的 0,直徑為 3 條邊。

node = max(range(len(tree)), key=distance.__getitem__)

這行取得 distance 最大的索引。

複雜度: 兩次 BFS 仍是 O(V + E);樹中 E = V - 1,所以是 O(V)。

加權樹: 若邊有非負權重,可把內層 BFS 改為 DFS 並累加距離。

<!-- END ALGORITHM EXPLANATION -->

Euler Tour(DFS 序)

子樹對應 Euler 序中的連續半開區間 [tin[u], tout[u])。

def euler_tour(tree, root = 0):
    n = len(tree)
    tin = [0] * n
    tout = [0] * n
    parent = [-1] * n
    order = []
    stack = [(root, -1, 0)]
    while stack:
        u, p, state = stack.pop()
        if state == 0:
            parent[u] = p
            tin[u] = len(order)
            order.append(u)
            stack.append((u, p, 1))
            for v in reversed(tree[u]):
                if v != p:
                    stack.append((v, u, 0))
        else:
            tout[u] = len(order)
    subtree_size = [tout[u] - tin[u] for u in range(n)]
    return order, tin, tout, parent, subtree_size
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

Euler Tour 會把樹攤平成一維陣列。此模板在第一次進入節點時記錄:

tin[u] = len(order)
order.append(u)

處理完所有子節點、準備離開時記錄:

tout[u] = len(order)

因此節點 u 的整棵子樹會剛好落在:

order[tin[u]:tout[u]]

例如根 0 有孩子 1、2,而 1 有孩子 3。一種 DFS 序可能是 [0, 1, 3, 2];節點 1 的子樹區間是 [1, 3),對應 [1, 3]。

棧中的 state:

  • 0:第一次進入節點。
  • 1:所有子節點已安排處理,現在離開節點。

這種寫法在不使用遞迴的情況下,仍能同時取得進入與離開時間。

複雜度: O(n) 時間、O(n) 空間。

常見用途: 搭配 Fenwick Tree 或 Segment Tree 做子樹加總、子樹更新與祖先判斷。

<!-- END ALGORITHM EXPLANATION -->

Subtree Size(子樹大小)

在上一節的 Euler Tour 中,subtree_size[u] = tout[u] - tin[u]。若只需要子樹大小,也可用後序累加:

def subtree_sizes(tree, root = 0):
    parent = [-1] * len(tree)
    order = [root]
    for u in order:
        for v in tree[u]:
            if v != parent[u]:
                parent[v] = u
                order.append(v)
    size = [1] * len(tree)
    for u in reversed(order[1:]):
        size[parent[u]] += size[u]
    return size
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

第一個迴圈建立父節點與由上到下的 order:

parent[v] = u
order.append(v)

一開始每個節點的子樹至少包含自己,所以:

size = [1] * len(tree)

接著必須反向走訪 order。這樣孩子一定會在父節點之前完成:

for u in reversed(order[1:]):
    size[parent[u]] += size[u]

每個節點把自己的子樹大小加給父節點,最後根節點的大小會是整棵樹節點數。

例如 0 的孩子是 1、2,1 的孩子是 3:

size[3] = 1
size[1] = 2
size[2] = 1
size[0] = 4

order[1:] 刻意跳過根,因為根的 parent 是 -1,不需要再往上加。

複雜度: 每條樹邊看固定次數,時間 O(n)、空間 O(n)。

<!-- END ALGORITHM EXPLANATION -->

DSU 離線刪邊(反向加邊)

若操作只有刪除與詢問連通性,可先移除所有將被刪的邊,再倒序把邊加回。

def offline_dynamic_connectivity(n, edges, operations):
    normalize = lambda a, b: (a, b) if a < b else (b, a)
    cut_edges = {normalize(u, v) for kind, u, v in operations if kind == "cut"}
    dsu = DSU(n)
    for u, v in edges:
        if normalize(u, v) not in cut_edges:
            dsu.union(u, v)
    answer = []
    for kind, u, v in reversed(operations):
        if kind == "ask":
            answer.append(dsu.same(u, v))
        else:
            dsu.union(u, v)
    return answer[::-1]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

DSU 很會「加邊」,卻不容易真的刪邊。因此離線演算法把時間倒過來:正向的刪邊,在反向就變成加邊。

先收集所有將被刪除的邊:

cut_edges = {
    normalize(u, v)
    for kind, u, v in operations
    if kind == "cut"
}

normalize() 把無向邊固定成較小端點在前,避免 (1, 3) 和 (3, 1) 被視為不同邊。

接著只把「最後仍存在」的邊加入 DSU。然後倒序處理操作:

  • 原本的 ask:此刻直接用 dsu.same(u, v) 回答。
  • 原本的 cut:反向時間中代表把這條邊加回,執行 union(u, v)。

因為答案是倒序收集,最後要 answer[::-1] 回到原操作順序。

小例子: 原本先問 0、2 是否連通,再刪除 1-2,再問一次。反向時先處理第二次詢問,再把 1-2 加回,最後處理第一次詢問。

複雜度: O((E + Q) α(n)),近似線性。

限制: 此簡化模板假設無向邊不重複,且每條邊不會被重複刪除。

<!-- END ALGORITHM EXPLANATION -->

動態規劃

0/1 Knapsack(0/1 背包)

每件物品最多選一次,因此容量必須由大到小更新。時間 O(nC)、空間 O(C)。

def zero_one_knapsack(items, capacity):
    dp = [0] * (capacity + 1)
    for weight, value in items:
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]

若要判斷是否能湊出某個總和:

def subset_sum(values, target):
    possible = 1
    for value in values:
        possible |= possible << value
    return bool((possible >> target) & 1)
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

dp[current] 表示容量不超過 current 時能取得的最大價值。

每件物品 (weight, value) 只能選一次,所以容量必須由大到小更新:

for current in range(capacity, weight - 1, -1):
    ...  # 容量倒序,避免同一物品重複使用

這樣讀取的 dp[current - weight] 仍是「尚未使用目前物品」的上一輪狀態。轉移表示兩種選擇:

dp[current] = max(
    dp[current],                  # 不選目前物品
    dp[current - weight] + value # 選目前物品
)

例如容量 5,物品為 (2, 3)、(3, 4),兩件都選剛好裝滿,答案是 7。

第二段 subset_sum() 使用整數 bitset。第 s 個 bit 為 1,代表總和 s 可達:

possible |= possible << value

左移 value 位等於把所有既有總和都加上 value。

複雜度: 一般 DP 為 O(nC) 時間、O(C) 空間;bitset 版本通常更快,但仍受目標總和大小影響。

容易出錯: 若容量由小到大更新,同一物品會在同一輪被重複使用,變成完全背包。

<!-- END ALGORITHM EXPLANATION -->

Unbounded Knapsack(完全背包)

每件物品可重複選;容量由小到大更新。

def unbounded_knapsack(items, capacity):
    dp = [0] * (capacity + 1)
    for weight, value in items:
        for current in range(weight, capacity + 1):
            dp[current] = max(dp[current], dp[current - weight] + value)
    return dp[capacity]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

完全背包與 0/1 背包的主要差別只有容量迴圈方向:

for current in range(weight, capacity + 1):
    ...  # 容量正序,允許重複使用目前物品

由小到大更新時,dp[current - weight] 可能已在本輪使用過目前物品,所以同一物品可以再次被選。

例如容量 6,只有物品 (weight=2, value=3):

dp[2] = 3
dp[4] = dp[2] + 3 = 6
dp[6] = dp[4] + 3 = 9

最後答案為 9,代表選了三次。

複雜度: O(nC) 時間、O(C) 空間。

判斷方式:

  • 每件最多一次:容量倒序。
  • 每件可重複:容量正序。
<!-- END ALGORITHM EXPLANATION -->

Coin Change(硬幣問題)

最少硬幣數:

def minimum_coins(coins, target):
    dp = [target + 1] * (target + 1)
    dp[0] = 0
    for amount in range(1, target + 1):
        for coin in coins:
            if coin <= amount:
                dp[amount] = min(dp[amount], dp[amount - coin] + 1)
    return -1 if dp[target] > target else dp[target]

組合數(順序不計):硬幣放外層。排列數(順序要計):金額放外層。

def coin_change_combinations(coins, target, mod=None):
    dp = [0] * (target + 1)
    dp[0] = 1
    for coin in coins:
        for amount in range(coin, target + 1):
            dp[amount] += dp[amount - coin]
            if mod:
                dp[amount] %= mod
    return dp[target]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

第一段求湊出 target 所需的最少硬幣數。dp[amount] 的初始值設為 target + 1,代表尚不可達;dp[0] = 0 表示湊出 0 元不需要硬幣。

dp[amount] = min(dp[amount], dp[amount - coin] + 1)

表示最後使用一枚 coin,前面先湊出 amount - coin。

例如硬幣 [1, 3, 4]、目標 6,最佳是 3 + 3,答案 2,不是貪心選 4 + 1 + 1 的 3 枚。

第二段計算組合數。硬幣放在外層,能確保 [1, 2] 和 [2, 1] 只算同一種組合:

for coin in coins:
    for amount in range(coin, target + 1):
        ...  # 硬幣在外層,因此不同順序只算一次

若題目把不同順序視為不同方法,應改成 amount 外層、coin 內層。

複雜度: 兩個版本皆為 O(len(coins) × target) 時間、O(target) 空間。

<!-- END ALGORITHM EXPLANATION -->

LIS(最長遞增子序列)

只求長度可用 patience sorting,時間 O(n log n)。嚴格遞增使用 bisect_left;非嚴格遞增改用 bisect_right。

from bisect import bisect_left


def lis_length(values):
    tails = []
    for value in values:
        index = bisect_left(tails, value)
        if index == len(tails):
            tails.append(value)
        else:
            tails[index] = value
    return len(tails)

還原其中一組 LIS:

def longest_increasing_subsequence(values):
    if not values:
        return []
    tails = []
    tail_indices = []
    previous = [-1] * len(values)
    for i, value in enumerate(values):
        position = bisect_left(tails, value)
        if position == len(tails):
            tails.append(value)
            tail_indices.append(i)
        else:
            tails[position] = value
            tail_indices[position] = i
        if position:
            previous[i] = tail_indices[position - 1]
    result = []
    index = tail_indices[-1]
    while index != -1:
        result.append(values[index])
        index = previous[index]
    return result[::-1]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

tails[length - 1] 保存「長度為 length 的遞增子序列,其結尾可能有的最小值」。它不是最後答案本身,但長度一定正確。

index = bisect_left(tails, value)

找第一個 >= value 的位置:

  • 若找不到,value 可以接在所有尾端之後,LIS 長度加一。
  • 若找到,就用較小的 value 替換原尾端,讓未來更容易接上更大的數。

例如 [3, 5, 2, 4]:

3 -> [3]
5 -> [3, 5]
2 -> [2, 5]
4 -> [2, 4]

所以長度是 2。

第二段用 tail_indices 記住每個長度目前尾端的原陣列索引,previous[i] 則指向 values[i] 在該 LIS 中的前一個元素。最後從最長尾端反向追蹤並反轉,即可還原一組答案。

複雜度: O(n log n) 時間、O(n) 空間。

嚴格性: 嚴格遞增用 bisect_left;允許相等的非遞減序列改用 bisect_right。

<!-- END ALGORITHM EXPLANATION -->

LCS(最長公共子序列)

時間 O(nm);以下以滾動陣列降為 O(m) 空間。

def lcs_length(a, b):
    if len(a) < len(b):
        a, b = b, a
    previous = [0] * (len(b) + 1)
    for x in a:
        current = [0]
        for j, y in enumerate(b, 1):
            if x == y:
                current.append(previous[j - 1] + 1)
            else:
                current.append(max(previous[j], current[-1]))
        previous = current
    return previous[-1]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

LCS 允許跳過元素,但不能改變順序。完整狀態原本是 dp[i][j]:a 前 i 個字元和 b 前 j 個字元的 LCS 長度。

若目前字元相同:

current.append(previous[j - 1] + 1)

答案來自左上角再加 1。若不同,就選擇跳過 a 或跳過 b:

max(previous[j], current[-1])
  • previous[j]:跳過目前的 a 字元。
  • current[-1]:跳過目前的 b 字元。

程式只保留上一列 previous 和目前列 current,把空間從 O(nm) 降到 O(min(n, m))。

例如 a = "ABC"、b = "AC",LCS 是 "AC",長度為 2。

複雜度: O(nm) 時間、O(min(n, m)) 空間。

<!-- END ALGORITHM EXPLANATION -->

Edit Distance(編輯距離)

插入、刪除、替換的成本皆為 1。

def edit_distance(a, b):
    if len(a) < len(b):
        a, b = b, a
    previous = list(range(len(b) + 1))
    for i, x in enumerate(a, 1):
        current = [i]
        for j, y in enumerate(b, 1):
            current.append(min(
                current[-1] + 1,
                previous[j] + 1,
                previous[j - 1] + (x != y),
            ))
        previous = current
    return previous[-1]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

previous[j] 和 current[j] 分別代表上一列與目前列 DP。每個狀態比較三種操作:

current[-1] + 1                      # 插入
previous[j] + 1                      # 刪除
previous[j - 1] + (x != y)           # 替換或不操作

(x != y) 在 Python 中是布林值,但參與加法時 False = 0、True = 1:

  • 字元相同,不需成本。
  • 字元不同,替換成本為 1。

第一列 0, 1, 2, ... 表示把空字串變成 b 前綴需要連續插入;每列的第一個值 i 表示把 a 前綴全部刪除。

例如把 cat 變成 cut,只需把 a 替換成 u,距離為 1。

複雜度: O(nm) 時間、O(min(n, m)) 空間。

<!-- END ALGORITHM EXPLANATION -->

Grid DP(網格 DP)

由左上走到右下,只能向右或向下,求最小成本;時間 O(rows × columns)。

def minimum_grid_path(cost):
    rows, columns = len(cost), len(cost[0])
    dp = [10**30] * columns
    dp[0] = 0
    for row in range(rows):
        for column in range(columns):
            from_up = dp[column]
            from_left = dp[column - 1] if column else 10**30
            dp[column] = cost[row][column] + min(from_up, from_left)
    return dp[-1]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

題目只允許從左上角往右或往下,因此到達 (row, column) 的前一步只可能來自上方或左方。

from_up = dp[column]
from_left = dp[column - 1] if column else 10**30

在更新前,dp[column] 仍保存上一列同欄的答案;dp[column - 1] 已更新成目前列左邊格子的答案。

dp[column] = cost[row][column] + min(from_up, from_left)

加入目前格子的成本,選較便宜的進入方向。

第一格使用初始 dp[0] = 0,因此答案會從 cost[0][0] 正確開始。不存在的左方以 INF 表示。

例如:

1 3
2 1

最佳路徑是 1 -> 2 -> 1,總成本 4。

複雜度: O(rows × columns) 時間、O(columns) 空間。

<!-- END ALGORITHM EXPLANATION -->

Interval DP(區間 DP)

典型狀態是 dp[left][right],按區間長度由短到長計算。下例為矩陣鏈乘最少乘法次數,時間 O(n^3)。

def matrix_chain_cost(dimensions):
    n = len(dimensions) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for left in range(n - length + 1):
            right = left + length - 1
            dp[left][right] = min(
                dp[left][middle] + dp[middle + 1][right]
                + dimensions[left] * dimensions[middle + 1] * dimensions[right + 1]
                for middle in range(left, right)
            )
    return dp[0][n - 1] if n else 0
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

區間 DP 的狀態依賴較短區間,因此外層先枚舉 length,從長度 2 慢慢增加。

矩陣鏈中,dimensions = [d0, d1, ..., dn] 表示第 i 個矩陣大小為 dimensions[i] × dimensions[i+1]。

dp[left][right] 是把第 left..right 個矩陣相乘的最少成本。枚舉最後一次切割位置 middle:

dp[left][middle] + dp[middle + 1][right]
+ dimensions[left] * dimensions[middle + 1] * dimensions[right + 1]

前兩項是左右兩半各自的成本,最後一項是把兩個結果矩陣乘起來的成本。

例如尺寸 [10, 30, 5, 60]:先算 (10×30)(30×5) 再乘 (5×60),通常比另一種括號順序省很多。

複雜度: O(n³) 時間、O(n²) 空間。

共同模式: 回文、石子合併、括號化等題目也常用「區間長度 → 左端 → 分割點」三層迴圈。

<!-- END ALGORITHM EXPLANATION -->

Bitmask DP(狀態壓縮 DP)

旅行推銷員:dp[mask][u] 表示從 0 出發,走過 mask 中節點且停在 u 的最小成本。時間 O(n²2ⁿ)。

def traveling_salesperson(distance):
    n = len(distance)
    full = 1 << n
    dp = [[10**30] * n for _ in range(full)]
    dp[1][0] = 0
    for mask in range(full):
        for u in range(n):
            if not (mask >> u) & 1:
                continue
            for v in range(n):
                if (mask >> v) & 1:
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(
                    dp[new_mask][v], dp[mask][u] + distance[u][v]
                )
    return min(dp[-1][u] + distance[u][0] for u in range(n))

枚舉 mask 的所有非空子集合:

subset = mask
while subset:
    # 使用 subset
    subset = (subset - 1) & mask
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

第 v 個 bit 是否為 1,代表節點 v 是否已走過:

(mask >> v) & 1

dp[mask][u] 表示從節點 0 出發,走過 mask 中所有節點,最後停在 u 的最小成本。初始:

dp[1][0] = 0

因為 mask = 1 只有第 0 bit 為 1。

轉移到尚未造訪的 v:

new_mask = mask | (1 << v)

最後所有節點都走過後,再加上回到起點的成本。

第二段:

subset = (subset - 1) & mask

可依序枚舉 mask 的所有非空子集合,不會產生 mask 以外的 bit。

複雜度: TSP 為 O(n²2ⁿ) 時間、O(n2ⁿ) 空間,只適合 n 較小的題目。

<!-- END ALGORITHM EXPLANATION -->

Game DP(Nim/Sprague–Grundy)

Nim 的必勝條件是所有石堆大小 XOR 不為 0。

from functools import reduce
from operator import xor


def nim_first_player_wins(piles):
    return reduce(xor, piles, 0) != 0

一般無環公平組合遊戲可計算 SG 值:

def mex(values):
    seen = set(values)
    result = 0
    while result in seen:
        result += 1
    return result


def grundy_numbers(graph):
    sg = [-1] * len(graph)

    def solve(state):
        if sg[state] == -1:
            sg[state] = mex(solve(next_state) for next_state in graph[state])
        return sg[state]

    for state in range(len(graph)):
        solve(state)
    return sg
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

Nim 中每回合可從任一石堆拿走正數顆石頭。所有石堆大小 XOR:

reduce(xor, piles, 0)

若結果不為 0,先手存在必勝走法;若為 0,在雙方最佳策略下先手必敗。

例如 [1, 2, 3]:1 ^ 2 ^ 3 = 0,先手必敗;[1, 2, 4] 的 XOR 不為 0,先手必勝。

一般公平組合遊戲用 SG 值。終止狀態沒有後繼狀態,其後繼 SG 集合為空,所以 mex({}) = 0。

sg[state] = mex(solve(next_state) for next_state in graph[state])

mex 是集合中未出現的最小非負整數。例如 {0, 1, 3} 的 mex 是 2。

多個獨立子遊戲組合時,把各自 SG 值 XOR;非零為必勝。

限制: grundy_numbers() 假設遊戲狀態圖無環,否則遞迴不會正常結束。

<!-- END ALGORITHM EXPLANATION -->

Tree DP(樹 DP)

最大權重獨立集:相鄰節點不能同時選。skip[u] 不選 u,take[u] 選 u。

def maximum_weight_independent_set(tree, weight, root=0):
    parent = [-1] * len(tree)
    order = [root]
    for u in order:
        for v in tree[u]:
            if v != parent[u]:
                parent[v] = u
                order.append(v)
    skip = [0] * len(tree)
    take = weight[:]
    for u in reversed(order):
        for v in tree[u]:
            if parent[v] == u:
                skip[u] += max(skip[v], take[v])
                take[u] += skip[v]
    return max(skip[root], take[root])
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

最大權重獨立集要求相鄰節點不能同時選。每個節點有兩個狀態:

  • take[u]:選擇 u。
  • skip[u]:不選 u。

若選 u,孩子一定不能選:

take[u] += skip[v]

若不選 u,每個孩子可自由選擇較好的狀態:

skip[u] += max(skip[v], take[v])

第一個迴圈先建立父節點與由上到下的順序;第二個迴圈反向處理,確保計算父節點前,所有孩子都已完成。

例如只有一條邊 0-1,權重為 [5, 8],答案會選節點 1,得到 8;若根還有另一個權重 7 的孩子,則可同時選兩個孩子得到 15。

複雜度: O(n) 時間、O(n) 空間。

<!-- END ALGORITHM EXPLANATION -->

Weighted Job Scheduling(加權工作排程)

工作格式 (start, end, profit),選互不重疊的工作使收益最大。排序與二分後為 O(n log n)。

from bisect import bisect_right


def weighted_job_scheduling(jobs):
    jobs = sorted(jobs, key=lambda job: job[1])
    ends = [end for _, end, _ in jobs]
    dp = [0] * (len(jobs) + 1)
    for i, (start, _, profit) in enumerate(jobs, 1):
        compatible = bisect_right(ends, start, hi=i - 1)
        dp[i] = max(dp[i - 1], dp[compatible] + profit)
    return dp[-1]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

工作格式是 (start, end, profit)。先依結束時間排序,dp[i] 表示只考慮前 i 個工作時的最大收益。

對第 i 個工作,用:

compatible = bisect_right(ends, start, hi=i - 1)

找出在目前工作開始前已結束的工作數量。因為 dp 多一個初始 0,這個數量可直接當成 DP 索引。

接著比較:

dp[i - 1]                  # 不選目前工作
dp[compatible] + profit    # 選目前工作

例如工作 (1, 3, 5)、(2, 5, 6)、(4, 6, 5),第一和第三不重疊,總收益 10,優於只選第二個的 6。

複雜度: 排序 O(n log n),每個工作二分 O(log n),總計 O(n log n);空間 O(n)。

<!-- END ALGORITHM EXPLANATION -->

貪心

區間排程(Interval Scheduling)

結束時間越早越先選,可得到最多互不重疊區間。

def maximum_non_overlapping_intervals(intervals):
    chosen = []
    last_end = -10**30
    for start, end in sorted(intervals, key=lambda interval: interval[1]):
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

目標是選最多個互不重疊區間。貪心規則是「每次選結束最早的區間」:它為後面的工作留下最多空間。

for start, end in sorted(intervals, key=lambda interval: interval[1]):
    ...  # 優先考慮結束時間最早的區間

last_end 保存上一個已選區間的結束時間。若:

start >= last_end

代表新區間可接在後面,就把它加入答案並更新 last_end。

例如 (1, 4)、(2, 3)、(3, 5):先選結束最早的 (2, 3),接著可選 (3, 5),共兩個;若先選 (1, 4) 就只能得到一個。

複雜度: 排序 O(n log n),掃描 O(n)。

邊界: 此模板把 end == next_start 視為不重疊;若題意的端點是閉區間,條件可能要改成 start > last_end。

<!-- END ALGORITHM EXPLANATION -->

多機區間排程(k-Screen Scheduling)

每個節目只能安排一次;找結束時間不晚於開始時間且最晚空出的機器。Python 標準庫沒有 multiset,下例以排序陣列實作,適合中等資料量;大資料可改用 sortedcontainers.SortedList。

from bisect import bisect_right, insort


def k_machine_scheduling(intervals, k):
    available = [-10**30] * k
    count = 0
    for start, end in sorted(intervals, key=lambda interval: interval[1]):
        index = bisect_right(available, start) - 1
        if index >= 0:
            available.pop(index)
            insort(available, end)
            count += 1
    return count
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

有 k 台機器時,available 保存每台機器目前工作的結束時間,並維持排序。

仍先按新工作的結束時間排序。對 (start, end),尋找不晚於 start 的最晚結束時間:

index = bisect_right(available, start) - 1

選「最晚但仍可用」的機器,是為了保留更早空出的機器給可能更早開始的其他工作。

找到後先移除舊結束時間,再插入新的 end:

available.pop(index)
insort(available, end)

例如兩台機器目前結束時間為 [3, 7],新工作從 5 開始,應使用結束於 3 的機器;結束於 7 的尚不可用。

複雜度: 此標準串列版本每次插入、刪除可能 O(k),總計最壞 O(nk)。大資料應使用支援有序 multiset 的結構。

<!-- END ALGORITHM EXPLANATION -->

最小化完成時間(Task Scheduling)

若每個工作的處理時間為 duration、完成後另有延遲 tail,常用 tail 由大到小安排,使整體完成時間最小。

def minimize_completion_time(tasks):
    current = 0
    answer = 0
    for duration, tail in sorted(tasks, key=lambda task: -task[1]):
        current += duration
        answer = max(answer, current + tail)
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

每個工作有 (duration, tail):先花 duration 處理,之後還需等待 tail 才真正完成。機器同時只能處理一件工作,但 tail 可和之後的工作重疊。

因此 tail 越長越應優先開始:

sorted(tasks, key=lambda task: -task[1])

current 是目前累積的處理時間。完成某工作處理後,它的最終完成時刻是:

current + tail

答案取所有工作的最大值。

例如工作 (3, 10) 和 (2, 1):先做第一件,完成時刻分別為 13、6,總答案 13;反過來第一件會到 15 才完成。

複雜度: O(n log n)。

理解方式: 長 tail 若太晚開始,很容易成為整體最後完成的瓶頸。

<!-- END ALGORITHM EXPLANATION -->

截止時間排程:Reverse Sweep

若每個工作有 (duration, deadline),全部都必須完成,從最晚截止時間往前排可求最晚開始時刻。

def latest_start_time(tasks):
    current = 10**30
    for duration, deadline in sorted(tasks, key=lambda task: task[1], reverse=True):
        current = min(current, deadline) - duration
    return current
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

每個工作為 (duration, deadline),所有工作都必須完成。程式從時間軸右側往左排。

先按 deadline 由晚到早排序。對每個工作:

current = min(current, deadline) - duration
  • min(current, deadline):工作最晚只能在自己的 deadline 或下一個已排工作開始前完成。
  • 再減去 duration:得到此工作的開始時間。

例如工作 (3, 10)、(2, 6):先把第一件放在 [7, 10],第二件最晚放在 [4, 6],中間可有空檔,整體最晚開始時間為 4。

若結果為負數,代表必須在時間 0 以前開始;若題目禁止,可能表示排程不可行。

複雜度: 排序 O(n log n),掃描 O(n)。

<!-- END ALGORITHM EXPLANATION -->

截止時間排程:Forward Sweep(EDF)

目標是選最多能在截止時間前完成的工作:按截止時間掃描;若超時,移除目前耗時最大的工作。

from heapq import heappop, heappush


def maximum_on_time_jobs(tasks):
    total = 0
    selected = []
    for duration, deadline in sorted(tasks, key=lambda task: task[1]):
        total += duration
        heappush(selected, -duration)
        if total > deadline:
            total += heappop(selected)
    return len(selected)
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

目標是選最多能準時完成的工作。先按 deadline 由早到晚掃描,因為最早截止者最緊急。

每個工作先暫時加入:

total += duration
heappush(selected, -duration)

selected 用負值模擬最大堆。若累積時間超過目前 deadline,表示目前選擇無法全部準時完成,此時移除耗時最長的工作:

total += heappop(selected)

因為彈出的是負數,加回去等同從 total 扣除該 duration。移除最長工作能釋放最多時間,同時只少一個工作。

例如 (4, 4)、(3, 5)、(1, 5):加入前兩件後超時,移除耗時 4 的工作,之後可保留 3 和 1,共兩件。

複雜度: O(n log n)。

<!-- END ALGORITHM EXPLANATION -->

最小費用合併(Huffman/Min Cost Merge)

每次合併最小的兩堆,時間 O(n log n)。

from heapq import heapify, heappop, heappush


def minimum_merge_cost(sizes):
    heap = sizes[:]
    heapify(heap)
    total = 0
    while len(heap) > 1:
        merged = heappop(heap) + heappop(heap)
        total += merged
        heappush(heap, merged)
    return total
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

每次合併兩堆時,成本是兩堆大小之和;合併後的新堆還會參與後續合併。因此越早產生的大數,越可能被重複計費。

最佳策略是每次取最小的兩堆:

merged = heappop(heap) + heappop(heap)

把合併成本加入 total,再把新堆放回 heap。

例如 [1, 2, 7]:

先合併 1+2 = 3,成本 3
再合併 3+7 = 10,總成本 13

若先合併 2+7=9,再合併 1+9=10,總成本會是 19。

複雜度: 建 heap O(n),進行 n-1 次合併,每次 O(log n),總計 O(n log n)。

應用: Huffman 編碼、檔案合併、繩索連接問題。

<!-- END ALGORITHM EXPLANATION -->

Multiset 貪心配對:最大匹配(Ticket Assignment)

對每個上限 limit,取不大於它的最大票價。排序陣列版刪除為 O(n),適合中等資料量。

def assign_tickets(prices, limits):
    prices.sort()
    answer = []
    for limit in limits:
        index = bisect_right(prices, limit) - 1
        answer.append(prices.pop(index) if index >= 0 else -1)
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

對每位顧客的預算 limit,要出售「不超過預算的最高票價」。

index = bisect_right(prices, limit) - 1

bisect_right 找第一個大於 limit 的位置,往左一格就是最大合法票價。若 index < 0,代表所有票都太貴,答案為 -1。

配到票後要從可用票中刪除:

prices.pop(index)

例如票價 [5, 7, 8],顧客預算依序 [7, 8]:第一位拿 7,第二位拿 8。

為什麼不拿更便宜的 5?把 5 留給未來預算較低的顧客,通常能完成更多匹配。

複雜度: 二分是 O(log n),但串列中間刪除是 O(n),因此最壞 O(qn)。大資料需要真正的有序 multiset 或 Fenwick Tree。

<!-- END ALGORITHM EXPLANATION -->

Multiset 貪心配對:最小費用(Min Cost Matching)

排序後同序配對可最小化絕對差總和。

def minimum_absolute_matching(a, b):
    if len(a) != len(b):
        raise ValueError("two groups must have the same size")
    return sum(abs(x - y) for x, y in zip(sorted(a), sorted(b)))
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

兩組元素數量相同,要一對一配對並最小化絕對差總和。將兩組各自排序後,同位置配對:

zip(sorted(a), sorted(b))

這樣不會出現交叉配對。若 a1 <= a2、b1 <= b2,將 a1 配 b2、a2 配 b1 不會比同序配對更好。

例如:

a = [1, 10]
b = [2, 9]

同序成本是 |1-2| + |10-9| = 2;交叉成本是 |1-9| + |10-2| = 16。

複雜度: 排序 O(n log n),配對加總 O(n)。

限制: 此模板要求兩組大小相同;若可略過元素或有額外限制,通常要改用 DP 或其他匹配方法。

<!-- END ALGORITHM EXPLANATION -->

遞增陣列(Increasing Array)

只允許增加元素,使陣列成為非遞減;線性掃描即可。

def minimum_increments_to_nondecreasing(values):
    moves = 0
    current = -10**30
    for value in values:
        if value < current:
            moves += current - value
        else:
            current = value
    return moves
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

題目只允許增加元素,不能減少。current 保存處理到目前為止,下一個值至少必須達到的高度。

若 value < current,只能把它增加到 current:

moves += current - value

若 value >= current,不需要修改,並把新的基準更新成 value。

例如 [3, 2, 5, 1]:

3 保持 3
2 增加到 3,成本 1
5 保持 5
1 增加到 5,成本 4
總成本 5

最後陣列等價於 [3, 3, 5, 5]。

複雜度: O(n) 時間、O(1) 額外空間。

容易出錯: current 只在遇到更大值時更新;把小值補高後,基準仍是原本的 current。

<!-- END ALGORITHM EXPLANATION -->

集合等分(Set Partition)

把總和盡量平均分成兩組,可轉成容量為 sum(values) // 2 的 0/1 子集合和。

def minimum_partition_difference(values):
    total = sum(values)
    reachable = 1
    for value in values:
        reachable |= reachable << value
    half = total // 2
    best = max(i for i in range(half + 1) if (reachable >> i) & 1)
    return total - 2 * best
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

設所有數總和為 total。若其中一組總和為 s,另一組就是 total - s,差值為:

total - 2*s

因此只需找不超過 total // 2 的最大可達子集合和。

reachable 是 bitset:第 s bit 為 1,代表能選出總和 s。

reachable |= reachable << value

把所有舊總和複製一份並加上 value,同時保留不選 value 的舊狀態。

例如 [1, 2, 4],總和 7,一半為 3;可達最大值是 3 = 1 + 2,所以最小差為 7 - 2*3 = 1。

複雜度: 從演算法觀點取決於總和 S;Python 大整數位元運算通常比逐格布林 DP 快很多。

限制: 此技巧直接適用非負整數;含負數時需位移索引或改用集合 DP。

<!-- END ALGORITHM EXPLANATION -->

間隔覆蓋(Minimum Intervals to Cover Range)

要覆蓋 [target_left, target_right],每步從所有起點不晚於目前位置的區間中,選右端最遠者。

def minimum_cover(intervals, target_left, target_right):
    intervals.sort()
    i = 0
    current = target_left
    count = 0
    while current < target_right:
        farthest = current
        while i < len(intervals) and intervals[i][0] <= current:
            farthest = max(farthest, intervals[i][1])
            i += 1
        if farthest == current:
            return -1
        current = farthest
        count += 1
    return count
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

current 表示目前已保證覆蓋到的位置。每一輪把所有 start <= current 的區間納入候選,並找右端最遠的:

farthest = max(farthest, intervals[i][1])

選最遠右端可以讓每次使用的區間發揮最大效果,因而得到最少區間數。

若一輪結束後:

farthest == current

代表沒有任何區間能從目前位置繼續延伸,目標範圍無法完整覆蓋,回傳 -1。

例如要覆蓋 [0, 10],區間有 (0, 4)、(2, 8)、(4, 10):先從可用者選到 4,再考慮起點不超過 4 的區間,可直接延伸到 10。

複雜度: 排序 O(n log n),每個區間只掃一次,掃描 O(n)。

<!-- END ALGORITHM EXPLANATION -->

間距最小化(Gap Minimization)

在每段長度 gap 中可插入點,二分最小可能最大間距。required(max_gap) 必須隨 max_gap 單調不增。

def minimize_maximum_gap(points, extra_points):
    points = sorted(points)
    gaps = [b - a for a, b in zip(points, points[1:])]

    def required(max_gap):
        return sum((gap - 1) // max_gap for gap in gaps)

    left, right = 1, max(gaps, default=0)
    while left < right:
        middle = (left + right) // 2
        if required(middle) <= extra_points:
            right = middle
        else:
            left = middle + 1
    return left
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

答案具有單調性:如果最大間距 x 可行,那麼任何更大的間距也一定可行,因此可以二分答案。

對原本長度為 gap 的一段,若要求每小段最多 max_gap,需要插入:

(gap - 1) // max_gap

例如 gap = 10:

  • 最大間距 5,插入 1 點,切成 5 + 5。
  • 最大間距 3,插入 3 點,切成不超過 3 的四段。

required(middle) <= extra_points 代表目前間距可行,可以嘗試更小答案;否則要放寬。

if required(middle) <= extra_points:
    right = middle
else:
    left = middle + 1

複雜度: 每次檢查 O(n),二分約 O(log max_gap) 次,總計 O(n log max_gap)。

<!-- END ALGORITHM EXPLANATION -->

PQ 貪心移除(Priority Queue Greedy Removal)

選最多工作且總耗時不超過限制:逐一加入最大堆,超限時移除最耗時者。

def maximum_tasks_within_time(durations, limit):
    selected = []
    total = 0
    for duration in durations:
        total += duration
        heappush(selected, -duration)
        if total > limit:
            total += heappop(selected)
    return len(selected)
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

逐一把工作加入候選,total 保存目前總耗時,最大堆保存已選工作的 duration。

Python heapq 是最小堆,因此放入負值:

heappush(selected, -duration)

若 total > limit,代表目前選太多工作。為了只移除一件就釋放最多時間,應刪除耗時最長者:

total += heappop(selected)

彈出的是最大的 duration 的負值,所以加回 total 等同扣除它。

例如 durations [4, 2, 3]、限制 5:加入 4、2 後超限,移除 4,留下 2;再加入 3,剛好總耗時 5,共兩件。

複雜度: 每項最多進出 heap 一次,O(n log n)。

前提: 這種貪心適用「每件價值相同,只想選最多件」的情況。

<!-- END ALGORITHM EXPLANATION -->

掃描線(Sweep Line)

半開區間 [start, end) 的同座標事件應先處理結束 -1,再處理開始 +1。

def maximum_overlap(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    active = answer = 0
    for _, delta in sorted(events, key=lambda event: (event[0], event[1])):
        active += delta
        answer = max(answer, active)
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

每個區間 [start, end) 轉成兩個事件:

(start, +1)  # 有一個區間開始
(end, -1)    # 有一個區間結束

事件依座標排序後,active 就是目前同時存在的區間數,答案取歷史最大值。

同一座標時按 delta 排序,-1 會在 +1 前處理。這符合半開區間:在時間 t 結束的工作,和時間 t 開始的工作不算重疊。

例如 [1, 3) 和 [3, 5):座標 3 先执行 -1 再执行 +1,最大重疊仍是 1。

若題意使用閉區間 [start, end],同座標應先處理開始事件,排序規則要改。

複雜度: 建立 2n 個事件並排序,為 O(n log n);掃描 O(n)。

<!-- END ALGORITHM EXPLANATION -->

滑動中位數(Sliding Median)

雙堆加延遲刪除可達 O(n log k)。small 保存較小的一半(以負值模擬最大堆),large 保存較大的一半。

from collections import Counter
from heapq import heappop, heappush


def sliding_median(values, k):
    small, large = [], []
    delayed = Counter()
    small_size = large_size = 0

    def prune(heap, sign):
        while heap and delayed[sign * heap[0]]:
            value = sign * heappop(heap)
            delayed[value] -= 1

    def rebalance():
        nonlocal small_size, large_size
        if small_size > large_size + 1:
            heappush(large, -heappop(small))
            small_size -= 1
            large_size += 1
            prune(small, -1)
        elif small_size < large_size:
            heappush(small, -heappop(large))
            small_size += 1
            large_size -= 1
            prune(large, 1)

    def add(value):
        nonlocal small_size, large_size
        if not small or value <= -small[0]:
            heappush(small, -value)
            small_size += 1
        else:
            heappush(large, value)
            large_size += 1
        rebalance()

    def remove(value):
        nonlocal small_size, large_size
        delayed[value] += 1
        if value <= -small[0]:
            small_size -= 1
            if value == -small[0]:
                prune(small, -1)
        else:
            large_size -= 1
            if large and value == large[0]:
                prune(large, 1)
        rebalance()

    answer = []
    for i, value in enumerate(values):
        add(value)
        if i >= k:
            remove(values[i - k])
        if i + 1 >= k:
            answer.append(-small[0])
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

程式用兩個 heap:

  • small:較小的一半,用負值模擬最大堆;-small[0] 是中位數候選。
  • large:較大的一半,使用一般最小堆。

平衡條件是 small 和 large 一樣大,或 small 多一個元素。故視窗長度為奇數時,中位數是 -small[0];偶數時此模板回傳較小的中位數。

heap 不支援任意位置刪除,所以 remove() 只在 delayed[value] 記帳。prune() 發現堆頂已被標記時,才真正彈出,稱為延遲刪除。

small_size、large_size 計算的是有效元素數,不包含等待刪除的舊元素。rebalance() 在兩堆間移動堆頂,恢復大小條件。

例如視窗 [1, 5, 2]:較小半可為 [1, 2],較大半為 [5],中位數是 2。

複雜度: 每個元素加入、移除與搬動均為 O(log k),總計 O(n log k);空間 O(k) 加延遲標記。

容易出錯: 有重複值時不能只用 set,必須用 Counter 記錄待刪數量。

<!-- END ALGORITHM EXPLANATION -->

搜尋與排序

Binary Search(二分搜)

找第一個使單調布林函式 check(x) 成立的整數:

def first_true(left, right, check):
    """答案必須存在於閉區間 [left, right]。"""
    while left < right:
        middle = (left + right) // 2
        if check(middle):
            right = middle
        else:
            left = middle + 1
    return left

找最後一個成立者:

def last_true(left, right, check):
    while left < right:
        middle = (left + right + 1) // 2
        if check(middle):
            left = middle
        else:
            right = middle - 1
    return left

已排序陣列可直接用 bisect_left(values, target) 找第一個 >= target 的位置,用 bisect_right 找第一個 > target 的位置。

<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

二分搜答案要求 check(x) 具有單調性,例如:

False False False True True True

first_true() 要找第一個 True。每次取中點:

middle = (left + right) // 2
  • 若 check(middle) 成立,middle 可能就是答案,但左側可能還有更小答案,所以令 right = middle。
  • 若不成立,答案一定在右側,令 left = middle + 1。

當 left == right 時只剩一個候選位置。

last_true() 找最後一個成立者,中點使用:

(left + right + 1) // 2

刻意向右取整,可避免只剩兩個數時 left 不再前進而形成無限迴圈。

例如最小可行容量為 7,搜尋 [0, 10],check(x) 為 x >= 7,first_true() 會得到 7。

複雜度: O(log(range)) 次 check()。

容易出錯: 必須先證明單調性,並確認答案一定存在於初始區間。

<!-- END ALGORITHM EXPLANATION -->

Ternary Search(三分搜)

離散單峰函式求最小值;最後保留少量位置暴力比較。

def discrete_ternary_search(left, right, function):
    while right - left >= 3:
        third = (right - left) // 3
        middle1 = left + third
        middle2 = right - third
        if function(middle1) > function(middle2):
            left = middle1 + 1
        else:
            right = middle2 - 1
    position = min(range(left, right + 1), key=function)
    return position, function(position)

連續實數版本:

def real_ternary_search(left, right, function, iterations=100):
    for _ in range(iterations):
        middle1 = (2 * left + right) / 3
        middle2 = (left + 2 * right) / 3
        if function(middle1) > function(middle2):
            left = middle1
        else:
            right = middle2
    position = (left + right) / 2
    return position, function(position)
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

三分搜適用單峰或單谷函式。求最小值時,函式應先下降後上升。

離散版本在區間中取兩點:

middle1 = left + third
middle2 = right - third

若 function(middle1) > function(middle2),表示往右仍在下降,最小值不會位於最左側,可移動 left;否則移動 right。

離散整數可能有平台或相等區段,所以當候選範圍少於三格時,直接:

min(range(left, right + 1), key=function)

實數版本沒有「剩幾個整數」的概念,因此固定迭代約 100 次。每輪把區間縮成約 2/3,最後取中點。

複雜度: 離散版 O(log range) 次函式計算;實數版是 iterations 次。

容易出錯: 函式若有多個分離的局部極值,三分搜不保證找到全域最佳解。

<!-- END ALGORITHM EXPLANATION -->

Two Pointers/Sliding Window(雙指標/滑動視窗)

排序後判斷三數和:

def three_sum_exists(values, target):
    values = sorted(values)
    n = len(values)
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            total = values[i] + values[left] + values[right]
            if total == target:
                return True
            if total < target:
                left += 1
            else:
                right -= 1
    return False

最長不含重複元素子陣列:

def longest_distinct_subarray(values):
    last_position = {}
    left = 0
    answer = 0
    for right, value in enumerate(values):
        if value in last_position:
            left = max(left, last_position[value] + 1)
        last_position[value] = right
        answer = max(answer, right - left + 1)
    return answer

最多含 k 種不同值的子陣列數量:

from collections import defaultdict


def count_subarrays_with_at_most_k_distinct(values, k):
    frequency = defaultdict(int)
    left = distinct = answer = 0
    for right, value in enumerate(values):
        if frequency[value] == 0:
            distinct += 1
        frequency[value] += 1
        while distinct > k:
            old = values[left]
            frequency[old] -= 1
            if frequency[old] == 0:
                distinct -= 1
            left += 1
        answer += right - left + 1
    return answer

兩人一組且總重不超過上限,求最少組數:

def minimum_pairs_with_limit(weights, limit):
    weights.sort()
    left, right = 0, len(weights) - 1
    groups = 0
    while left <= right:
        if left < right and weights[left] + weights[right] <= limit:
            left += 1
        right -= 1
        groups += 1
    return groups

兩組數值在容許差 tolerance 內做最大匹配:

def maximum_close_matching(a, b, tolerance):
    a.sort()
    b.sort()
    i = j = answer = 0
    while i < len(a) and j < len(b):
        if b[j] < a[i] - tolerance:
            j += 1
        elif b[j] > a[i] + tolerance:
            i += 1
        else:
            answer += 1
            i += 1
            j += 1
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

本節有五種常見模式。

1. 三數和

先排序並固定 i,再用 left、right 夾逼:總和太小就增加左端,太大就減少右端。每個固定 i 只需線性掃描,因此總時間 O(n²)。

2. 最長無重複子陣列

last_position[value] 保存某值上次出現位置。若重複,左端至少跳到上次位置的下一格:

left = max(left, last_position[value] + 1)

max 很重要,避免左端倒退。

3. 最多 k 種不同值的子陣列數

右端每加入一個值就更新頻率;種類數超過 k 時移動左端。窗口合法後,以 right 結尾的合法子陣列共有 right - left + 1 個。

4. 兩人一組且重量有限

每輪最重者一定要佔一組;若能和最輕者搭配就一起帶走,否則最重者單獨一組。

5. 容許誤差的一對一匹配

兩組排序後,哪一側值太小就移動哪一側;落在容許範圍內就同時配對並前進。

例如無重複窗口處理 [1, 2, 1, 3]:看到第二個 1 時,left 從 0 跳到 1,最後最長窗口 [2, 1, 3] 長度為 3。

共同重點: 指標只向前走、不回頭,通常能把雙層暴力降成 O(n);需要排序的版本則另加 O(n log n)。

<!-- END ALGORITHM EXPLANATION -->

Meet in the Middle(折半搜尋)

把 n 個元素分半,枚舉兩側子集合和,常把 O(2ⁿ) 降為 O(2^(n/2)) 等級。

from collections import Counter


def subset_sums(values):
    sums = [0]
    for value in values:
        sums += [current + value for current in sums]
    return sums


def count_subsets_with_sum(values, target):
    middle = len(values) // 2
    left_counts = Counter(subset_sums(values[:middle]))
    return sum(left_counts[target - right] for right in subset_sums(values[middle:]))
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

直接枚舉 n 個元素所有子集合要 2**n 次。折半搜尋把陣列切成左右兩半,各自只需約 2**(n/2) 個子集合。

subset_sums() 從只有空集合和 0 開始:

sums = [0]

加入新值時,將所有既有總和各加上它,再接回原串列:

sums += [current + value for current in sums]

這同時代表「不選」和「選」目前元素。

左半總和使用 Counter 計數,因為不同子集合可能產生相同總和。對每個右半總和 right,需要左半補出 target - right:

left_counts[target - right]

例如 [1, 2, 3, 4]、目標 5,可找到 {1,4}、{2,3} 等組合。

複雜度: 約 O(2^(n/2)) 時間與空間;通常適合 n 約 40 左右而數值範圍很大的題目。

<!-- END ALGORITHM EXPLANATION -->

Merge Sort:Inversion Count(逆序對計數)

def inversion_count(values):
    def sort_and_count(array):
        if len(array) <= 1:
            return array, 0
        middle = len(array) // 2
        left, left_count = sort_and_count(array[:middle])
        right, right_count = sort_and_count(array[middle:])
        merged = []
        i = j = 0
        count = left_count + right_count
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                count += len(left) - i
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, count

    return sort_and_count(values)[1]

Fenwick Tree 版本(先離散化):

def inversion_count_fenwick(values):
    ranks = {value: rank for rank, value in enumerate(sorted(set(values)))}
    bit = FenwickTree(len(ranks))
    answer = 0
    for value in reversed(values):
        rank = ranks[value]
        answer += bit.prefix_sum(rank)
        bit.add(rank, 1)
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

逆序對是 i < j 但 values[i] > values[j] 的索引對。

合併排序版本先遞迴把左右兩半排序。合併時若:

left[i] > right[j]

因為左半已排序,所以 left[i:] 的所有元素都比 right[j] 大,一次增加:

len(left) - i

例如左半 [2, 5, 7]、右半目前值 3,5、7 都和 3 形成逆序對,一次加 2。

Fenwick 版本先把值離散化成排名,再由右往左掃。已插入的元素都位於目前位置右側:

bit.prefix_sum(rank)

計算已插入且排名較小的數量,也就是目前元素形成的逆序對數。

使用 sorted(set(values)) 可讓相同值取得相同排名;相等元素不算逆序對。

複雜度: 兩個版本皆為 O(n log n) 時間、O(n) 空間。

<!-- END ALGORITHM EXPLANATION -->

數學

Fast Exponentiation(快速冪)

Python 內建 pow(base, exponent, modulus) 已使用快速冪。手寫版本如下,時間 O(log exponent)。

def mod_power(base, exponent, modulus):
    result = 1
    base %= modulus
    while exponent:
        if exponent & 1:
            result = result * base % modulus
        base = base * base % modulus
        exponent >>= 1
    return result
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

指數用二進位表示。例如 13 = 8 + 4 + 1,不必把底數乘 13 次,只需反覆平方。

if exponent & 1:
    result = result * base % modulus

若目前最低 bit 是 1,就把這一位代表的冪乘進答案。

base = base * base % modulus
exponent >>= 1

底數平方,代表從 base^1 依序變成 base^2、base^4、base^8...;指數右移一位,繼續處理下一個 bit。

例如 3^13 會組合 3^1 × 3^4 × 3^8。

每次乘法後立即 % modulus,可保持數字較小;Python 雖不會整數溢位,但大整數乘法仍會變慢。

複雜度: O(log exponent) 時間、O(1) 空間。

Python 內建: 實務上可直接使用 pow(base, exponent, modulus)。

<!-- END ALGORITHM EXPLANATION -->

Sieve of Eratosthenes(埃氏篩)

時間約 O(n log log n),空間 O(n)。

def prime_sieve(limit):
    is_prime = bytearray(b"\x01") * (limit + 1)
    if limit >= 0:
        is_prime[0] = 0
    if limit >= 1:
        is_prime[1] = 0
    for prime in range(2, int(limit**0.5) + 1):
        if is_prime[prime]:
            start = prime * prime
            is_prime[start:limit + 1:prime] = b"\x00" * (((limit - start) // prime) + 1)
    primes = [number for number in range(2, limit + 1) if is_prime[number]]
    return primes, is_prime

最小質因數篩,方便快速質因數分解:

def smallest_prime_factors(limit):
    spf = list(range(limit + 1))
    for prime in range(2, int(limit**0.5) + 1):
        if spf[prime] == prime:
            for multiple in range(prime * prime, limit + 1, prime):
                if spf[multiple] == multiple:
                    spf[multiple] = prime
    return spf
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

埃氏篩先假設 0..limit 都是質數,再把 0、1 標成非質數。

若 prime 尚未被劃掉,它就是質數;其倍數都不是質數。從:

start = prime * prime

開始即可,因為更小倍數早已被較小質數處理。

is_prime[start:limit + 1:prime] = b"\x00" * count

這是 Python 的切片批次賦值,一次把所有倍數設成 0,通常比 Python 層的逐項迴圈快。

第二段最小質因數篩 spf[x] 保存 x 最小的質因數。分解 x 時可反覆取 spf[x] 並令 x //= spf[x]。

例如 spf[84] = 2,除後得到 42,再取 2、3、7,所以 84 = 2² × 3 × 7。

複雜度: 埃氏篩約 O(n log log n),空間 O(n)。

<!-- END ALGORITHM EXPLANATION -->

Factorial Trailing Zeros(階乘尾零)

十進位尾零來自因數 10 = 2 × 5;階乘中 2 較多,只需計算 5 的次方貢獻。

def factorial_trailing_zeros(n):
    answer = 0
    while n:
        n //= 5
        answer += n
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

十進位尾零由因數 10 = 2 × 5 產生。n! 中因數 2 遠多於 5,所以只需計算總共有幾個因數 5。

n //= 5
answer += n

第一次加上 5 的倍數數量;第二次加上 25 的倍數額外提供的第二個 5;之後還有 125、625...。

例如 n = 100:

100 // 5  = 20
100 // 25 = 4
總計 24 個尾零

程式透過反覆把 n 除以 5 得到同樣結果。

複雜度: O(log₅ n) 時間、O(1) 空間。

容易出錯: 不能只算 n // 5,因為 25、125 等數字含有不只一個因數 5。

<!-- END ALGORITHM EXPLANATION -->

Kadane's Algorithm(最大子陣列和)

可正確處理全負數陣列,時間 O(n)。

def maximum_subarray_sum(values):
    if not values:
        raise ValueError("values must not be empty")
    ending_here = answer = values[0]
    for value in values[1:]:
        ending_here = max(value, ending_here + value)
        answer = max(answer, ending_here)
    return answer
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

ending_here 表示「一定以目前位置結尾」的最大子陣列和。加入新值時只有兩種選擇:

ending_here = max(
    value,               # 從目前位置重新開始
    ending_here + value  # 接在前一段後面
)

answer 保存所有位置的最佳結果。

例如 [4, -6, 3, 2]:

4:ending = 4,answer = 4
-6:ending = -2,answer = 4
3:重新開始,ending = 3
2:接上去,ending = 5,answer = 5

最佳子陣列是 [3, 2]。

初始值使用 values[0] 而不是 0,所以全負數陣列也能正確回傳最大單一元素。例如 [-5, -2] 的答案是 -2。

複雜度: O(n) 時間、O(1) 額外空間。

<!-- END ALGORITHM EXPLANATION -->

前綴和

1D Prefix Sum(一維前綴和)

prefix[i] 表示前 i 個值的總和,區間 [left, right) 為 prefix[right] - prefix[left]。

from itertools import accumulate

values = [3, 1, 4, 1, 5]
prefix = [0, *accumulate(values)]


def range_sum_1d(prefix, left, right):
    return prefix[right] - prefix[left]

差分陣列可做多次區間加值:

def range_additions(n, updates):
    difference = [0] * (n + 1)
    for left, right, delta in updates:  # [left, right)
        difference[left] += delta
        difference[right] -= delta
    result = []
    current = 0
    for i in range(n):
        current += difference[i]
        result.append(current)
    return result
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

prefix = [0, *accumulate(values)]

前面的 0 代表取零個元素的總和。若 values = [3, 1, 4]:

prefix = [0, 3, 4, 8]

半開區間 [left, right) 的總和是:

prefix[right] - prefix[left]

因為前 right 個元素的總和減掉前 left 個,就只剩中間區間。例如 [1, 3) 為 8 - 3 = 5,對應 1 + 4。

第二段差分陣列用於多次區間加值。對 [left, right) 加 delta:

difference[left] += delta
difference[right] -= delta

最後做一次前綴累加,就能還原每個位置實際增加多少。

複雜度: 建前綴和 O(n),每次區間查詢 O(1);差分每次更新 O(1),最後還原 O(n)。

<!-- END ALGORITHM EXPLANATION -->

2D Prefix Sum(二維前綴和)

矩形採半開座標 [top, bottom) × [left, right);建表 O(rows × columns),查詢 O(1)。

class PrefixSum2D:
    def __init__(self, matrix):
        rows, columns = len(matrix), len(matrix[0])
        self.prefix = [[0] * (columns + 1) for _ in range(rows + 1)]
        for row in range(rows):
            row_sum = 0
            for column in range(columns):
                row_sum += matrix[row][column]
                self.prefix[row + 1][column + 1] = self.prefix[row][column + 1] + row_sum

    def query(self, top, left, bottom, right):
        p = self.prefix
        return p[bottom][right] - p[top][right] - p[bottom][left] + p[top][left]
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

prefix[r][c] 表示原矩陣左上角到 (r-1, c-1) 的矩形總和,也就是前 r 列、前 c 欄。

建表時 row_sum 保存目前這一列從第 0 欄累加到當前欄的總和:

self.prefix[row + 1][column + 1] = self.prefix[row][column + 1] + row_sum

上方矩形加目前列片段,就得到新的左上矩形。

查詢 [top, bottom) × [left, right) 使用容斥:

大矩形
- 上方
- 左方
+ 被重複減掉的左上角

對應程式:

p[bottom][right] - p[top][right] - p[bottom][left] + p[top][left]

複雜度: 建表 O(rows × columns)、查詢 O(1)、空間 O(rows × columns)。

容易出錯: 前綴表多一列一欄的 0,可省掉邊界特判;查詢座標採半開區間。

<!-- END ALGORITHM EXPLANATION -->

3D Prefix Sum(三維前綴和)

長方體查詢使用三維容斥;以下座標皆為半開區間。

class PrefixSum3D:
    def __init__(self, data):
        x_size, y_size, z_size = len(data), len(data[0]), len(data[0][0])
        self.prefix = [
            [[0] * (z_size + 1) for _ in range(y_size + 1)]
            for _ in range(x_size + 1)
        ]
        p = self.prefix
        for x in range(1, x_size + 1):
            for y in range(1, y_size + 1):
                for z in range(1, z_size + 1):
                    p[x][y][z] = (
                        data[x - 1][y - 1][z - 1]
                        + p[x - 1][y][z] + p[x][y - 1][z] + p[x][y][z - 1]
                        - p[x - 1][y - 1][z] - p[x - 1][y][z - 1]
                        - p[x][y - 1][z - 1] + p[x - 1][y - 1][z - 1]
                    )

    def query(self, x1, y1, z1, x2, y2, z2):
        p = self.prefix
        return (
            p[x2][y2][z2]
            - p[x1][y2][z2] - p[x2][y1][z2] - p[x2][y2][z1]
            + p[x1][y1][z2] + p[x1][y2][z1] + p[x2][y1][z1]
            - p[x1][y1][z1]
        )
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

三維前綴和把二維容斥擴充到三個軸。prefix[x][y][z] 表示座標原點到 (x-1, y-1, z-1) 的長方體總和。

建表時:

  • 加入三個方向的面:x-1、y-1、z-1。
  • 減掉三個被重複加入的交叉區域。
  • 加回被前一步多減的共同交集。

查詢長方體 [x1,x2) × [y1,y2) × [z1,z2) 也遵循相同的三維容斥,共有 2³ = 8 個角落項。

理解符號的方法:每個下界被選用一次就改變一次正負號。最右上後角 p[x2][y2][z2] 為正;含一個下界的三項為負;含兩個下界的三項為正;三個下界全含時為負。

複雜度: 建表 O(XYZ)、每次查詢 O(1)、空間 O(XYZ)。

建議: 先熟悉二維容斥,再記三維版本;大型三維陣列很耗記憶體。

<!-- END ALGORITHM EXPLANATION -->

其他技巧

Permutation(排列枚舉)

itertools.permutations 會把相同值的不同位置視為不同,因此輸入有重複值時可能產生重複排列。

from itertools import permutations

for arrangement in permutations([1, 2, 3]):
    print(arrangement)

# 去除重複排列(小資料適用)
unique = set(permutations([1, 1, 2]))

手寫下一個字典序排列:

def next_permutation(values):
    i = len(values) - 2
    while i >= 0 and values[i] >= values[i + 1]:
        i -= 1
    if i < 0:
        values.reverse()
        return False
    j = len(values) - 1
    while values[j] <= values[i]:
        j -= 1
    values[i], values[j] = values[j], values[i]
    values[i + 1:] = reversed(values[i + 1:])
    return True
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

permutations([1, 2, 3]) 會產生所有 3! = 6 種排列,而且每個結果是 tuple。

若輸入有重複值,例如 [1, 1, 2],兩個 1 的位置仍被視為不同,因此會產生重複 tuple。小資料可用:

set(permutations([1, 1, 2]))

去重,但會額外使用記憶體。

next_permutation() 產生下一個字典序排列:

  1. 從右找第一個 values[i] < values[i+1] 的轉折點。
  2. 從右找第一個大於 values[i] 的值並交換。
  3. 把 i 右側反轉成最小順序。

例如 [1, 3, 2]:轉折點是 1,和右側大於它的最小候選 2 交換,再反轉尾端,得到 [2, 1, 3]。

若整列已是遞減,代表沒有下一個排列;函式把它反轉成最小排列並回傳 False。

複雜度: 單次 next_permutation() 為 O(n);枚舉全部排列必然是 O(n! × n)。

<!-- END ALGORITHM EXPLANATION -->

Gray Code(格雷碼)

相鄰兩個碼只差一個 bit;第 i 個 Gray code 是 i ^ (i >> 1)。

def gray_codes(bits):
    return [format(i ^ (i >> 1), f"0{bits}b") for i in range(1 << bits)]


def gray_to_binary(gray):
    value = 0
    while gray:
        value ^= gray
        gray >>= 1
    return value
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

Gray Code 的特性是相鄰兩個值的二進位表示只改變一個 bit。

第 i 個 Gray Code:

i ^ (i >> 1)

例如 2-bit:

i:   00 01 10 11
Gray:00 01 11 10

相鄰結果分別只改一位。

format(value, f"0{bits}b") 會輸出固定 bits 位,不足的左側補 0。

gray_to_binary() 反向轉換時,將 Gray Code 與其不斷右移的版本 XOR:

value ^= gray
gray >>= 1

直到 gray 變成 0。

複雜度: 產生全部 bits 位 Gray Code 需要 O(2^bits) 個結果;單次轉換為 O(bits)。

應用: 位元狀態枚舉、旋轉編碼器、希望相鄰狀態只變一個 bit 的問題。

<!-- END ALGORITHM EXPLANATION -->

Fast Hash(防 hack 雜湊)

Python 的 str、bytes 雜湊預設每個行程隨機化;整數雜湊則較可預測。一般題目直接用 dict/set 即可。若平台刻意構造整數碰撞,可用隨機遮罩包裝鍵:

import secrets

_HASH_MASK = secrets.randbits(64)


def protected_key(value):
    return value ^ _HASH_MASK


frequency = {}
value = 123456789
key = protected_key(value)
frequency[key] = frequency.get(key, 0) + 1

若之後需要還原原值,XOR 同一遮罩即可。

<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

Python 的 dict 和 set 平均查詢是 O(1),但極端碰撞可能退化。字串與 bytes 的雜湊通常已有每個行程隨機化;整數雜湊較直接。

_HASH_MASK = secrets.randbits(64)

建立每次執行都不同的 64-bit 遮罩。存入整數鍵前:

protected = value ^ _HASH_MASK

XOR 會可逆地打亂鍵值。若需要還原:

original = protected ^ _HASH_MASK

因為同一遮罩 XOR 兩次會回到原值。

此技巧主要用來避免有人針對可預測整數鍵安排惡意輸入。一般競程題直接使用原始整數作為 dict key 通常已足夠。

複雜度: 每次轉換 O(1)。

注意: 這不是密碼學加密,也不會改善演算法本身的錯誤複雜度。

<!-- END ALGORITHM EXPLANATION -->

四數之和(Hash)

計算 a + b + c + d = target 的四元組數量;時間 O(n²)、空間 O(n²)。

from collections import Counter


def four_sum_count(a, b, c, d, target=0):
    left_sums = Counter(x + y for x in a for y in b)
    return sum(left_sums[target - z - w] for z in c for w in d)

同一陣列找四個不同索引,可在掃描中只把已位於目前兩索引左側的 pair 放入表:

def four_distinct_indices(values, target):
    pair = {}
    n = len(values)
    for j in range(1, n):
        for k in range(j + 1, n):
            needed = target - values[j] - values[k]
            if needed in pair:
                i, h = pair[needed]
                return i, h, j, k
        for i in range(j):
            pair.setdefault(values[i] + values[j], (i, j))
    return None
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

第一段處理四個陣列。先枚舉所有 a + b 並用 Counter 記錄次數:

left_sums = Counter(x + y for x in a for y in b)

再枚舉 c + d。若四數總和要等於 target,左半需要:

target - z - w

Counter 的值是方法數,所以直接累加即可。

第二段要在同一陣列找四個不同索引。掃描到 (j, k) 時,pair 只保存結束索引小於 j 的舊 pair,因此找到的 (i, h, j, k) 天然互不重疊。

先查詢目前 j、k,查完後才把 (i, j) 放入表,順序不能反過來。

例如 [2, 7, 4, 0, 9]、目標 13,可找到 2 + 7 + 4 + 0 = 13。

複雜度: 兩種版本皆約 O(n²) 時間、O(n²) 空間,比四層暴力 O(n⁴) 快很多。

<!-- END ALGORITHM EXPLANATION -->

Josephus Problem(約瑟夫問題)

最後存活者的 0-indexed 編號可用 O(n) 遞推求得。

def josephus_survivor(n, step):
    survivor = 0
    for size in range(2, n + 1):
        survivor = (survivor + step) % size
    return survivor

需要完整淘汰順序且 n 較小時:

from collections import deque


def josephus_order(n, step):
    people = deque(range(n))
    order = []
    while people:
        people.rotate(-(step - 1))
        order.append(people.popleft())
    return order
<!-- BEGIN ALGORITHM EXPLANATION -->

拆解

josephus_survivor() 只求最後存活者。假設已知道人數 size - 1 時的答案,加入第 size 個人後,因為第一輪會向前移動 step,新答案為:

survivor = (survivor + step) % size

從只有一人時答案 0 開始,逐步推到 n 人。

例如 n = 5、step = 2:

size 1:0
size 2:(0+2)%2 = 0
size 3:(0+2)%3 = 2
size 4:(2+2)%4 = 0
size 5:(0+2)%5 = 2

最後存活者是 0-indexed 的 2,若題目編號從 1 開始要再加 1。

完整淘汰順序版本使用 deque。每輪:

people.rotate(-(step - 1))

把即將被淘汰的人轉到左端,再 popleft()。

複雜度: 只求存活者為 O(n) 時間、O(1) 空間;deque 模擬會受旋轉距離影響,適合較小資料。

<!-- END ALGORITHM EXPLANATION -->

Pragma 加速:Python 對應做法

C++ 的 #pragma GCC optimize 沒有 Python 等價語法。競程中應優先做以下調整:

  1. 使用正確的時間複雜度;這比任何微調都重要。
  2. 大量輸入使用 sys.stdin.buffer.read(),輸出先收集再 "\n".join(...)。
  3. 熱迴圈內把常用方法綁到區域變數,例如 push = heapq.heappush。
  4. 避免在迴圈內反覆切片、建立大型暫存串列或使用深遞迴。
  5. 位元集合適合用 Python 任意精度整數,例如子集合和的 bits |= bits << value。
  6. 若評測允許,可使用 PyPy;但含大量物件或特殊套件時 CPython 可能較合適。

快速 I/O 完整骨架:

import sys


def solve(data):
    iterator = iter(data)
    n = int(next(iterator))
    values = [int(next(iterator)) for _ in range(n)]
    return str(sum(values))


if __name__ == "__main__":
    tokens = sys.stdin.buffer.read().split()
    sys.stdout.write(solve(tokens))
<!-- BEGIN PRAGMA EXPLANATION -->

快速 I/O 完整骨架拆解

程式進入點先讀取所有輸入:

tokens = sys.stdin.buffer.read().split()

結果是由 bytes 組成的串列,例如輸入 3\n10 20 30\n 會變成:

[b'3', b'10', b'20', b'30']

接著把整份資料傳給 solve(tokens)。在 solve() 內:

iterator = iter(data)

將串列轉成 iterator。next(iterator) 每次取出一個 bytes;int() 可以直接把 b'10' 轉成整數 10,不必先呼叫 .decode()。

n = int(next(iterator))
values = [int(next(iterator)) for _ in range(n)]

第一個數字是資料筆數 n,接著恰好讀取 n 個值。若輸入提供的數字不足,next() 會拋出 StopIteration,通常表示輸入格式或讀取數量寫錯。

solve() 回傳字串:

return str(sum(values))

最後使用:

sys.stdout.write(solve(tokens))

一次輸出結果。sys.stdout.write() 不會自動補換行;需要換行時可改成:

sys.stdout.write(solve(tokens) + "\n")

若要輸出很多行,先收集字串再一次寫出:

answers = ["10", "20", "30"]
sys.stdout.write("\n".join(answers))

這樣能減少大量小型輸出呼叫。

適用時機: 輸入資料量很大,而且格式主要由空白分隔的整數組成。

注意: buffer.read() 已把輸入全部取走,後續不要再混用 input();若題目需要逐行保留空白或讀取含空格字串,也不適合直接全部 .split()。

<!-- END PRAGMA EXPLANATION -->

常見移植差異與陷阱

  • C++ long long 對應 Python int;Python 整數不會固定寬度溢位。
  • C++ 整數除法向 0 截斷;Python // 向負無限取整。負數題目須確認規格。
  • C++ lower_bound/upper_bound 對應 bisect_left/bisect_right。
  • C++ 最大堆 priority_queue 對應 Python heapq 的負值技巧;Python 3.14+ 才另有 max-heap API。
  • C++ set/map 有序;Python set 無序,dict 保留插入順序但不按鍵排序。
  • Python 標準庫缺少平衡樹 multiset。高頻任意刪除、前驅與後繼查詢可用座標壓縮 + Fenwick Tree,或在規則允許時使用 sortedcontainers。
  • 建立二維陣列要用 [[0] * m for _ in range(n)],不可用 [[0] * m] * n,否則每列會指向同一物件。
  • Dijkstra 僅適用非負權;拓撲排序只適用 DAG;Sparse Table 的 O(1) 重疊查詢需要冪等運算。
  • 半開區間 [left, right) 最貼近 Python 的 range、切片與 bisect,可減少邊界錯誤。

來源架構:郭10的 Blog:演算法、資料結構模板。本文件為 Python 重新實作版,最後整理日期:2026-08-11。