---
# System prepended metadata

title: 高二 運算思維 課程成果精華
tags: [已完成]

---

# 高二 運算思維 課程成果精華

> 作者：沈宗叡（暴力又被TLE）

## 前言

這份課程成果紀錄了高二選修「運算思維」課程中，一些有意思的推理題，我則會將推理思維程式化，使解題方法可以處理更一般化、更龐大的數據集。

為了可讀性，以下程式碼全都使用 Python 呈現。

這份報告僅節錄了部分我認為最有趣、最具挑戰性及代表性的題目，因此若是對完整內容有興趣，也可以到 [文件末尾](#附件) 閱讀其他更完整、詳細的報告。

若是閱讀紙本，可以到 [文件末尾](#本文的連結) 掃 QRcode 閱讀網頁版。

## 心得

原本以為這堂「運算思維」課，只是高中資訊課的另一個 alias——換個教室，從隔壁同學的螢幕 `pull` 幾行現成答案就能 AC 的作業，不過是一堆基礎的純 IO 語法題的枯燥堆砌。

然而太 naïve 的並非題目，而是我。

這門課根本不是教你如何 `print(input())`，而是反過來 `assert 你真的好好思考過了嗎？`。老師從天南地北 `scrape` 來一堆真正富含「運算思維」的題目，不是紙上談兵的語法練習，而是引導我們訓練一種能力：看見問題背後的邏輯結構與抽象模型，最終一般化並解決問題。

而我則比同儕更進一步，不只是 `case` 單一問題的答案，而是試著找出可推廣的解法，將解題流程 formalize 成程式邏輯，進而應對更大規模的數據挑戰，同時探索更多神奇的演算法世界。剛開始我只會 `for-loop` 枚舉、窮舉爆搜 $O(n^n)$ 直到海枯石爛，然而在深度挖掘之後將各種題目轉化為經典演算法問題：

- [小學生死神的使者](#小學生死神的使者-20241015) 與其 hardcoded 特判給定條件，我卻選擇建出變數圖，將部分條件轉化為 2-SAT 問題，再用 Tarjan 演算法縮 SCC 後 $O(n)$ 找可行解。
- [河道檢驗](#河道檢驗-2025328) 連窮舉都不知道怎麼實作，卻可以轉化成二分圖最大匹配、或上下界網路流問題，完美抓出最小成本。
- [跳島遊戲](#跳島遊戲-2025614) 這種連手算都想趕快 `quit()` 的題目，卻能巧妙地轉化成二分搜+最大流。

這樣深度鑽研這些難題的過程中難免頻繁 `catch` 到無數難以自行處理的 `Exception`，這也讓我鍛鍊了與 ChatGPT、Gemini 等 LLM 對話討論，或扯著 Google 的小漁網遨遊網路之洋，在無垠中撈出解法之鑰的能力。偶爾我也會 `import` 完全外行的朋友們幾句天真的 idea `as hint`。遇到那些連搜索關鍵字都看不懂的學術論文時，更淬鍊了我向各路大佬「不畏上問」的勇氣，與提問的智慧。

經歷如此糾結又暢爽的自主研究後，我有自信說：自己絕不是 copy others’ AC 刷 AC/sub 率，而是真正地在小小腦子無限次的 TLE 和 MLE 中 construct my own solution。

謝謝老師精心設計這門「運算思維」，也感恩每一題逼我腦洞大開的題目。雖然我僅僅高二，但我深信這些寫過的程式、思考過的每一個解題模型、精神證明過的每一個邏輯斷言，早已在我腦中 `malloc` 了一塊塊永不 `free` 掉的珍貴記憶。未來即便走得再遠，我也會持續保持這股對運算思維的熱情與探索精神，直到 `stack overflow`！

## 實作成果

### 消防設備 2024/9/21

> 給一無向圖，**選取**一點則其相鄰點皆被**覆蓋**，求最小**選取集合**使所有點皆被**覆蓋**？

經典的「最小支配集」問題，NP-complete 沒有多項式時間解、也沒有快速的近似算法，可以先對每個節點建表「選取後能覆蓋哪些點」，再直接枚舉所有 $O(2 ^ n)$ 個集合並 $O(n)$ 判斷是否完整覆蓋，總共 $O(E + V \times 2 ^ V)$，位元 DP 會是一樣的複雜度。

若圖是樹則可以貪心 $O(n)$，若樹上帶權則可以 DP $O(n)$。

- 枚舉所有集合並 $O(n)$ 判斷是否完整覆蓋

```python=
def minimum_dominating_set(
        n: int, edges: list[tuple[int, int]]
) -> tuple[int, list[int]]:
    def count_tail_zero(b: int) -> int:
        return (b & -b).bit_length() - 1

    adjacent = [1 << i for i in range(n)]
    for i, j in edges:
        adjacent[i] |= 1 << j
        adjacent[j] |= 1 << i

    ans = 0
    best = n
    for chosen in range(1 << n):
        if chosen.bit_count() > best:
            continue
        dominated = 0
        rest = chosen
        while rest:
            dominated |= adjacent[count_tail_zero(rest)]
            rest &= rest - 1
        if dominated.bit_count() == n:
            ans = chosen
            best = chosen.bit_count()

    chosen = []
    while ans:
        chosen.append(count_tail_zero(ans))
        ans &= ans - 1
    return best, chosen


print(*minimum_dominating_set(
    9,
    [(0, 1), (0, 2), (0, 8), (1, 2),
     (2, 6), (2, 7), (3, 4), (3, 5),
     (3, 6), (4, 5), (5, 6), (5, 7), (7, 8)]))

```

- 樹上貪心

定義三個狀態：

- `00`：不選此點，未被支配　　　 -> 父節點必選，支配此點 -> 父節點 `| 11`
- `01`：不選此點，已被子節點支配 -> 對父節點無影響　　　 -> 父節點 `| 00`
- `11`：選取此點，已被自己支配　 -> 父節點已被此點支配　 -> 父節點 `| 01`

可以注意到左邊一位代表「是否選取」，右邊一位代表「是否已支配」，如此一來轉移都只需要 `|` 一個數字即可，這就是二進位的魅力！
以下 `((~x & 1) << 1) | (~((x >> 1) ^ x) & 1)` 的公式，就是輸入左側子節點狀態、輸出右側父節點要 `|` 的值。

但根節點還需要特別注意，因為根節點沒有父節點，因此若是根節點為狀態 `00` 則也需要選取他。實作上可以特判（最穩妥）；另一種方法是再增加一個虛點作為根節點的父節點，這樣就能確保父節點必然被支配，而以下實作直接將根節點的父節點設為其本身，讓他「如果未被支配則自己支配自己」，只是在計算支配集點數時，得注意不要重複算到根節點，因此我是待狀態全部更新完再用一個 `sum` 統一計算。

```python=
def minimum_dominating_set_of_tree(
        n: int, edges: list[tuple[int, int]]
) -> tuple[int, list[int]]:
    adj_list = [[] for _ in range(n)]
    for a, b in edges:
        adj_list[a].append(b)
        adj_list[b].append(a)

    top_down = [0]
    parent = [None] * n
    parent[0] = 0
    for i in top_down:
        for j in adj_list[i]:
            if parent[j] is not None: continue
            parent[j] = i
            top_down.append(j)

    dp = [0] * n
    f = (3, 0, None, 1).__getitem__
    # f(x) = ((~x & 1) << 1) | (~((x >> 1) ^ x) & 1)
    for i in reversed(top_down):
        dp[parent[i]] |= f(dp[i])
    return (sum(v >> 1 for v in dp),
            [i for i, v in enumerate(dp) if v >> 1])

```

- 樹上帶權

定義 $dp_i$ 為 $i$ 整棵子樹的最小權支配集，$dp_{i,0}$ 為不選 $i$ 且 $i$ 尚未被支配的情況、$dp_{i,1}$ 為不選 $i$ 但 $i$ 已被子節點支配（任一子節點有選）的情況、$dp_{i,2}$ 為選 $i$ 的情況（$i$ 理所當然被自己支配）。
則：

$$
dp_{i,0} = \sum_{j \in i} \min(dp_{j,1}, dp_{j,2})
$$

$$
dp_{i,1} = \big( \sum_{j \in i} \min(dp_{j,1}, dp_{j,2}) \big) + \min_{j \in i} \big( {dp_{j,2} - \min(dp_{j,1}, dp_{j,2})} \big)
$$

$$
dp_{i,2} = \sum_{j \in i} \min(dp_{j,0}, dp_{j,1}, dp_{j,2})
$$

然而 $dp_{i,1}$ 的轉移有點複雜，看似要分別維護 $\sum$ 和 $\min$ 的兩個部分，但觀察到其 $\sum$ 的部分即為 $dp_{i,0}$，因此實作上 $dp_{i,1}$ 可以只維護其 $\min$ 的部分，要轉移或計算答案時再加上 $dp_{i,0}$ 即可。

```python=
from itertools import islice
from math import inf


def minimum_weight_dominating_set_of_tree(
        n: int, weights: list[int], edges: list[tuple[int, int]]
) -> int:
    dp = [(0, inf, x) for x in weights]
    adj_list = [[] for i in range(n)]
    for a, b in edges:
        adj_list[a].append(b)
        adj_list[b].append(a)

    parent = [None] * n
    parent[0] = True
    top_down = [0]
    for i in top_down:
        for j in adj_list[i]:
            if parent[j] is None:
                parent[j] = i
                top_down.append(j)

    for i in islice(reversed(top_down), n - 1):
        pa = parent[i]
        d0, d1, d2 = dp[i]
        d1 += d0
        m = min(d1, d2)
        p0, p1, p2 = dp[pa]
        dp[pa] = (p0 + m,  # 此點不選 子節點皆需已被支配
                 min(p1, d2 - m),  # 子節點皆需已被支配 且有子節點支配此點
                 p2 + min(d0, d1, d2))  # 選此點 子節點隨意
    d0, d1, d2 = dp[0]
    return min(d0 + d1, d2)

```

### 義賊廖添丁 2024/9/21

> 給一無向圖、起點終點，找出從起點經過所有節點到終點、邊不重複走的路徑。

可以 $O(E!)$ 窮舉所有邊的走訪順序。

```python=
def main():
    from sys import stdin
    e = stdin.readline

    """
    建圖 輸入所有邊和起終點 (省略)
    """

    def dfs(i, nb, eb, res):
        if i == t and nb == nodes:  # 於t結尾且經過所有點
            ans.append(tuple(res))
            return
        for e, j in G[i]:
            if (eb >> e) & 1 == 0:
                res.append(j)
                dfs(j, nb | (1 << j), eb | (1 << e), res)
                res.pop()
        return None

    n, m, s, t = map(int, e().split())
    nodes = (1 << n) - 1
    edges = (1 << m) - 1

    G = [[] for i in range(n)]
    for i in range(m):
        a, b = map(int, e().split())
        G[a].append((i, b))
        G[b].append((i, a))

    ans = []
    dfs(s, 1 << s, 0, [s])
    get = "甲abcdefghijk乙".__getitem__
    for a in ans: print("".join(map(get, a)))
main()
```

這題會不會加上一些圖論黑魔法後能有甚麼很快的解？

問問 ChatGPT，如果在起點和終點之間連上一條虛擬的邊，問題就會變成「找經過所有點恰一次的環」，使用 cycle basis 的圖論黑魔法可以將時間複雜度壓低。

首先，找到任意一棵生成樹，剩下 $E-(V-1)$ 條邊，這每一條邊各自加入到生成樹上後，都會形成一個獨一無二的環，這些環叫做「基本環基底」，總共有 $E-(V-1)$ 個。

任取數個基本環基底（$O(2^{E-(V-1)})$），對他們做 xor 操作（也就是保留出現次數為奇數的邊，次數為偶數的邊刪除），就會得到一個圖，這個圖若是連通，就將題目轉換成了「找經過所有點與所有邊恰一次的路徑」，只要窮舉所有邊的排列順序即可，而此時邊數通常已遠小於原先邊數，故速度更快。

以上這些東西我研究了一整個晚上，感謝 APCS 模擬測驗群兩位大佬 Wiwi Ho 和 WayneYam 的幫助。

時間複雜度：$O(E \times 2^{E-V+2} + (\text{E of valid_edge})!)$
空間複雜度：$O(V + E + V \times 2^{(\text{E of valid_edge})})$

```python=
def main():
    from sys import stdin
    from functools import cache
    e = stdin.readline

    """
    建圖 輸入所有邊和起終點 (省略)
    """

    n, m, s, t = map(int, e().split())
    edges = [tuple(map(int, e().split())) for _ in range(m)]
    # 起終點增加一條假邊 把問題變成找環 (表示複雜度時e中不包含此邊)
    edges.append((s, t))

    an = (1 << n) - 1
    ae = (1 << m + 1) - 1
    G = [[] for i in range(n)]
    for i, (a, b) in enumerate(edges):
        G[a].append((i, b))
        G[b].append((i, a))

    # bfs造生成樹 O(e)
    nb, eb = 1 << s, 0
    cur = [s]
    while cur:
        nxt = []
        for i in cur:
            for e, j in G[i]:
                if (nb >> j) & 1: continue
                eb |= 1 << e
                nb |= 1 << j
                nxt.append(j)
        cur = nxt
    re = ae ^ eb  # 沒包含在生成樹的邊 共(e-v+2)個

    # 找cycle_basis 不知道實際多少 絕對小於 O((e-v+2)*e)
    cycle_basis = []
    while re:
        eeb = re & -re
        re ^= eeb
        a, b = edges[eeb.bit_length() - 1]

        nb = 1 << a
        cur = [(a, eeb)]
        while True:
            nxt = []
            for i, eeb in cur:
                for e, j in G[i]:
                    if (nb >> j) & 1: continue
                    if (eb >> e) & 1 == 0: continue
                    nb |= 1 << j
                    if j == b:
                        cycle_basis.append(eeb | (1 << e))
                        break
                    nxt.append((j, eeb | (1 << e)))
                else: continue
                break
            else:
                cur = nxt
                continue
            break
    print("cycle_basis")
    for i in cycle_basis:
        print(bin(i).lstrip("0b").zfill(m + 1))
    print()

    # 窮舉所有cycle_basis的xor組合 挑出使圖連通的 O(2^(e-v+2) * e)
    valid_edges = []
    eb = 0
    mask = [0] * (m - n + 2)
    while True:
        # 窮舉2^(e-v+2)種組合
        for i, (v, cb) in enumerate(zip(mask, cycle_basis)):
            eb ^= cb
            mask[i] ^= 1
            if v == 0: break
        else: break
        if eb.bit_count() < n: continue

        # bfs看圖是否連通 O(e)
        nb = 1
        cur = [0]
        while cur:
            nxt = []
            for i in cur:
                for e, j in G[i]:
                    if (nb >> j) & 1: continue
                    if (eb >> e) & 1 == 0: continue
                    nb |= 1 << j
                    nxt.append(j)
            cur = nxt
        if nb == an and eb >> m: valid_edges.append(eb & ~(1 << m))
    print("valid_edges")
    for i in valid_edges:
        print(bin(i).lstrip("0b").zfill(m + 1))
    print()

    @cache
    def dfs(i, eb):
        if i == t and eb == valid_edge:  # 於t結尾 用到所有valid_edge
            return ((i, ), )
        res = []
        for e, j in G[i]:
            if (eb >> e) & 1 == 0:
                if (tails := dfs(j, eb | (1 << e))) is None: continue
                for tail in tails:
                    res.append((i, ) + tail)
        return res if res else None

    # 從valid_edges找路徑
    ans = []
    for valid_edge in valid_edges:
        ans.extend(dfs(s, 0))
        dfs.cache_clear()
    get = "甲abcdefghijk乙".__getitem__
    print("ans")
    for a in ans: print("".join(map(get, a)))

main()
```

### 小學生死神的使者 2024/10/15

> A、B 兩人中至少去一人。
> A、D 不能一起去。
> A、E、F 三人中要派兩人去。
> B、C 兩人不是都去就是都不去。
> C、D 兩人中去一人。
> 若 D 不去，則 E 也不去。
> 要派那些人去？

只有 $6$ 人，數字很小直接窮舉。
用 bit 來窮舉，簡潔又好看。

答案：ABCF

```python=
for bit in range(1 << 6):  # 窮舉六人的所有組合
    if bit & 0b11 == 0: continue                     # A、B兩人中至少去一人。
    if bit & 0b1001 == 0b1001: continue              # A、D不能一起去。
    if (bit & 0b110001).bit_count() != 2: continue   # A、E、F三人中要派兩人去。
    if (bit >> 1) & 1 != (bit >> 2) & 1: continue    # B、C兩人不是都去就是都不去。
    if (bit & 0b1100).bit_count() != 1: continue     # C、D兩人中去一人。
    if bit & 0b11000 == 0b10000: continue            # 若D不去，則E也不去。
    print("".join(c for i, c in enumerate("ABCDEF") if (bit >> i) & 1))  # 答案
```

這題也能轉換成 2-SAT 問題，建圖後 $O(n)$ 縮 SCC 解決。

- A、B 兩人中至少去一人。
  !A -> B, !B -> A
- A、D 不能一起去。
  A -> !D, D -> !A
- A、E、F 三人中要派兩人去。
  這個條件無法轉換為 2-CNF，必須窮舉
- B、C 兩人不是都去就是都不去。
  B -> C, C -> B, !B -> !C, !C -> !B
- C、D 兩人中去一人。
  C -> !D, D -> !C, !C -> D, !D -> C
- 若 D 不去，則 E 也不去。
  !D -> !E, E -> D

<img src="https://hackmd.io/_uploads/BkwUS2qSeg.png" alt="Image" width="50%"/>
<!-- ![image](https://hackmd.io/_uploads/BkwUS2qSeg.png) -->

而 AEF 取 2 的部分再枚舉 3 種情況即可。

```python=
from itertools import count, starmap
from operator import eq

text = """!A -> B
!B -> A
A -> !D
D -> !A
B -> C
C -> B
!B -> !C
!C -> !B
C -> !D
D -> !C
!C -> D
!D -> C
!D -> !E
E -> D
"""


def transform(s: str) -> int:
    s = s.strip()
    return ((ord(s[-1]) - ord("A")) << 1) | (s[0] != "!")


n = 6
n *= 2

G_ = [[] for _ in range(n)]
for line in text.splitlines():
    a, b = map(transform, line.split(" -> "))
    G_[a].append(b)


def tarjan(i: int):
    dfn[i] = low[i] = cnt()
    stk.append(i);
    instk[i] = True
    for j in G[i]:
        if not instk[j] and dfn[j] is not None: continue
        if dfn[j] is None: tarjan(j)
        low[i] = min(low[i], low[j])
    if low[i] == dfn[i]:
        x = scn()
        j = None
        while j != i:
            j = stk.pop()
            instk[j] = False
            scc[j] = x


C32 = ["A", "E", "F"]
for excluded in C32:  # AEF 中枚舉誰不去 剩下兩人去
    G = [v[:] for v in G_]
    for a in C32:
        k = (a == excluded)
        a = transform(a)
        G[a ^ k ^ 1].append(a ^ k)

    dfn = [None] * n
    low = [None] * n
    scc = [None] * n
    instk = [False] * n
    stk = []
    cnt = count().__next__
    scn = count().__next__

    for i, v in enumerate(dfn):
        if v is None:
            tarjan(i)

    it = iter(scc)
    if any(starmap(eq, zip(it, it))): continue
    it = iter(scc)
    print("chosen:", ", ".join(
        chr(ord("A") + i) for i, (a, b) in enumerate(zip(it, it)) if a > b
    ))

```

### 森林猴子的打字冒險 2024/10/30

> 給字串 $s, p$，判斷 $p$ 是否為 $s$ 的子序列。

易在 $O(n)$ 解決，以下是用 iterator 寫的 naïve 解法：

```python=
def is_subseqence(p: str, s: str) -> bool:
    p = iter(p)
    j = next(p)
    for i in s:
        if i == j and (j := next(p, None)) is None:
            return True
    return False
```

有一個更漂亮的 approach，若寫 `obj in iterator`，會因為 iterator 沒有實作 `__contains__`，而 fallback 到 `any(val == obj for val in iterator)`，因此有以下的極簡潔判斷 is subseqence 的寫法：

```python=
def is_subseqence(p: str, s: str) -> bool:
    s = iter(s)
    return all(c in s for c in p)
```

Python とだも、うぜくし！

### 區間質數數量 2024/12/3

（在我會的範圍內）有兩種解法，適合不同的情況：

使用 Miller--Rabin prime test 可以在理論 $O((\log n) ^ 2)$ 內判斷區間內的每個數字是不是質數。
實作上 FFT 常數太大所以就不寫了（~~因為我不會~~），因此以下的實作詢問每個數字是 $O((\log n) ^ 3)$，並特判特定因數，加速程式。
每次詢問一個區間的時間複雜度 $O(r \times (\log x) ^ 3)$，$r$ 為區間長度，$x$ 大略代表區間內的數值大小。

```python=
def count_prime(s: int, t: int) -> int:
    cnt = 0
    for n in range(s, t + 1):
        # 先特判 節省時間
        if n <= 1: continue
        elif n & 1 == 0:
            if n == 2: cnt += 1
        elif n <= 7: cnt += 1
        elif n % 3 == 0 or n % 5 == 0 or n % 7 == 0: continue
        else:
            # Miller-Rabin prime test
            d = n - 1
            r = (d & -d).bit_length() - 1
            d >>= r

            for a in (
                    (2, 7, 61) if n <= 1 << 32 else  # 篩 2³² 以內
                    (2, 325, 9375, 28178, 450775, 9780504, 1795265022)  # 可到 2⁶⁴
            ):
                if a % n == 0:
                    continue
                x = pow(a, d, n)
                if x == 1 or x == n - 1:
                    continue
                for _ in range(r - 1):
                    x = pow(x, 2, n)
                    if x == n - 1:
                        break  # 可能是質數 繼續下一輪驗證
                else:
                    # 不是質數
                    break
            else:
                # 通過所有驗證 是質數
                cnt += 1
    return cnt
```

使用埃拉托斯特尼質數篩，從 $1$ 跑到右端點。適合大區間多筆詢問。
雖然歐拉線性篩的理論複雜度更好，但做了很多除法常數偏大，通常反而較慢。
預處理時間複雜度：$O(n \log (\log n))$
每次詢問：$O(1)$ 由前綴和相減求區間和

```python=
from itertools import islice
from math import isqrt

def count_prime(query: list[tuple[int, int]]) -> list[int]:
    n = 10 ** 6 + 1
    sieve = [True] * n
    sieve[0] = sieve[1] = False
    prefix = 0  # 同時對篩做前綴和
    for i, v in enumerate(islice(sieve, isqrt(n))):
        if v is True:
            prefix += 1
            for j in range(i * i, n, i):
                sieve[j] = False
        sieve[i] = prefix
    sieve.append(0)  # sentinel for prefix

    answer = []
    for s, t in query:
        # 查詢 [s, t] 區間質數個數
        print(sieve[t] - sieve[s - 1])
    return answer
```

### 鐵達尼號的求生號碼 2024/12/17

約瑟夫問題，依序輸出被淘汰的人、最終倖存的人。
使用 BIT 維護剩下的人形成的前綴和，並在 BIT 上 $O(\log_2 n)$ 二分搜找下一個下船的人。

$Time: O(k \log_2 n), Space: O(n)$

```python=
def joseph_needham(
        # 總人數, 數到幾下船, 總共下船幾個
        n: int, m: int, k: int
) -> tuple[list[int], list[int]]:
    # build BIT
    bit = [i & -i for i in range(n + 1)]
    # n's highest bit
    hb = 1 << n.bit_length() - 1

    removed = []
    target = 0
    for r in range(n, n - k, -1):
        # update bisect target
        target = (target + m - 1) % r
        # bisect_right for target on BIT
        b = hb
        i = v = 0
        while b > 0:
            if (ni := i + b) <= n and (nv := v + bit[ni]) <= target:
                i, v = ni, nv
            b >>= 1
        # update BIT
        i += 1  # 0-based to 1-based
        removed.append(i)
        while i <= n:
            bit[i] -= 1
            i += i & -i

    # BIT to array
    for i in range(n, 0, -1):
        if (j := i + (i & -i)) <= n:
            bit[j] -= bit[i]

    survived = [i for i, v in enumerate(bit) if v]
    return removed, survived
```

### 編碼問題 2024/12/17

> 給定一個英文字串，請計算使用霍夫曼編碼對這串字串進行編碼所需的存儲空間（以位元為單位）。

霍夫曼編碼的精隨在於「依照頻率給予編碼」，即 `build_tree` 部分。
使用一個 `priority queue` ，每一輪取最小的兩個節點合併。可以用一次 Sort 還有兩個 `queue` 來達成常數更小的建樹，但前者的可讀性更高，也較容易實作。

DFS 都是用迭代而不是遞迴寫的，只能說非常優雅。

這個東西我也搞了半個晚上。

```python=
from collections import Counter
from heapq import heapify, heappop, heappush


def build_tree(s: str) -> tuple:  # O(nlogn) priority queue
    freq = Counter(s)
    n = len(freq)

    h = [(v, k) for k, v in freq.items()]
    heapify(h)
    # 給每一項加上獨特編碼 以免rank相同時 heapq跑去比較node 而TypeError
    h = [(v, i, k) for i, (v, k) in enumerate(h)]

    # tree = node: tuple[le: node, ri: node] | str
    i = n
    while len(h) > 1:
        u, _, le = heappop(h)
        v, _, ri = heappop(h)
        pa = (le, ri)
        heappush(h, (u + v, i, pa))
        i += 1
    return h[0][2]


def tree2dict(root: tuple) -> dict[str, int]:
    key = 0
    dfs = [(root, 1)]  # 每個編碼加上前綴1 防止int的前綴0都被削去
    dic = {}
    while dfs:
        cur, bit = dfs.pop()
        key = (key << 1) | bit
        if cur is None:  # visited node
            key >>= 2
        elif isinstance(cur, str):  # leaf
            dic[cur] = key
            key >>= 1
        else:
            le, ri = cur
            dfs.append((None, 0))  # sentinel
            dfs.append((le, 0))
            dfs.append((ri, 1))
    return dic


def compress(s: str, dic: dict) -> int:
    res = 0
    for bit in map(dic.get, s):
        res <<= bit.bit_length()
        res |= bit
    return res


def decompress(bit: int, root: tuple) -> str:
    res = []
    cur = dummy = (None, root)
    for i in map(int, f"{bit:b}"):
        cur = cur[i]
        if isinstance(cur, str):
            res.append(cur)
            cur = dummy
    return "".join(res)


s = input()
print(f"inputed string: {s}")

tree: tuple = build_tree(s)
dic: dict = tree2dict(tree)
compressed: str = compress(s, dic)
print(f"compressed int: {compressed}")
print(f"compressed bit: {compressed:b}")
print(f"bit length: {compressed.bit_length()}")
print(f"decompressed str: {decompress(compressed, tree)}")
```

### 河道檢驗 2025/3/28

這題有夠難，我研究了兩、三天...

> 給一個 DAG，求至少需要幾條路徑才能將所有**邊**覆蓋？點、邊可以重複。

這題跟 Path Cover 有很大關係，先來看看 Path Cover 問題：

> 給一有向圖，求最少需要幾條路徑才能將所有**點**覆蓋，點、邊不能重複。

一般情況下是 NP-hard，但在 DAG 上有多項式解法，可以轉為「二分圖匹配問題」，使用匈牙利算法或以最大流算法解決。

然而這題是覆蓋**邊**，且**點、邊可以重複**，因此需要一些轉化：

對於 $G(V, E)$ 上的所有邊 $u \to v$，在 $G'$ 加上兩條邊 $u \to e \to v$，接下來對於 $G'$ 上任意點對 $u, v$，如果存在 $u \to v$ 的路徑，則在 $G''$ 加上一條 $u \to v$ 邊。
$G''$ 上現在有 $|V| + |E|$ 個點，可以直接對他求 path cover：建立一個二分圖 $B$，左右各 $|V| + |E|$ 個點，對於所有 $G''$ 上的邊 $u \to v$ 在 $B$ 上左邊的 $u$ 和右邊的 $v$ 連邊。
在 $B$ 上求最大二分圖匹配 $M$，則所求即為 $|V| + |E| - M$。

此解的時間複雜度 $O((n+m) ^ 3)$ 

```python=
n, m = 9, 15
edges = [(0, 1), (1, 2), (2, 3), (0, 4),
         (4, 1), (4, 5), (5, 2), (5, 6),
         (6, 3), (0, 7), (4, 7), (7, 6),
         (7, 8), (6, 8), (8, 3)]

G = [[] for _ in range(n + m)]
indeg = [0] * (n + m)
for i, (a, b) in enumerate(edges, start=n):
    G[a].append(i)
    G[i].append(b)
    indeg[i] += 1
    indeg[b] += 1
root = indeg.index(0)

top_down = []
def dfs(i: int):
    top_down.append(i)
    for j in G[i]:
        indeg[j] -= 1
        if indeg[j] > 0: continue
        dfs(j)
    return

new_G = [set() for _ in range(n + m)]
dfs(root)
for i in reversed(top_down):
    for j in G[i]:
        new_G[i] |= new_G[j] | {j}

def path_cover(n, G):
    # O(nm) 匈牙利算法
    def match(i: int) -> bool:
        for j in G[i]:
            if ver[j] == s: continue
            ver[j] = s
            if pair[j] is None or match(pair[j]):
                pair[j] = i
                return True
        return False

    ver = [-1] * n
    pair = [None] * n
    max_match = 0
    for s in range(n):  # O(nm)
        max_match += match(s)
    return n - max_match

print(path_cover(n + m, new_G))
```

而原題也能直接轉換成「上下界最小流」：

> 給有源匯有向圖，求所有邊流量均 $\ge 1$ 的最小流。

上界可以隨意設定成足夠大的數。

先找出一個可行流：假設每個邊有 $1$ 的流，需先保證整個圖所有節點的入流和出流平衡。建立超源匯點 $S, T$，假設節點 $v$ 的 $\text{出流} - \text{入流} = x$，若 $x \gt 0$ 表示出流太多，要補一條 $S \to v$ 權值 $x$ 的邊；若 $x \lt 0$ 則表示入流太多，要補一條 $v \to T$ 權值 $-x$ 的邊。
如此除了 $S, T$ 以外的點都出入流平衡了。

接著要將「**有**源匯上下界可行流」問題轉換成「**無**源匯上下界可行流」，因此建立一條 $t \to s$ 容量無限的邊。在這個新圖上跑 $S \to T$ 最大流，若 $S$ 的出邊全部滿流代表有解。

在**新圖跑完最大流的流量基礎上**，在**原圖**跑 $t \to s$ 的最大流，就是在**殘餘網路**上能回推的最大流量，把第一輪最大流時 $t \to s$ 邊上的流量扣除第二輪回推的流量即為所求。

時間複雜度就是兩次最大流，以下使用 Dinic 則為 $O(n ^ 2 m)$。

```python=
from math import inf

n, m, s, t = 9, 15, 0, 3
edges = [(0, 1), (1, 2), (2, 3), (0, 4),
         (4, 1), (4, 5), (5, 2), (5, 6),
         (6, 3), (0, 7), (4, 7), (7, 6),
         (7, 8), (6, 8), (8, 3)]


def bounded_min_flow(n, edges, s, t, lo, hi) -> int:
    def dinic(s: int, t: int) -> int:
        def dfs(i, limit):
            if i == t:
                return limit
            sum_flow = 0  # 此點以下的最大流
            for j, edge_idx in G[i]:
                if flow[edge_idx] == cap[edge_idx]: continue
                if depth[j] != depth[i] + 1: continue
                pushed = dfs(j, min(limit - sum_flow, 
                                    cap[edge_idx] - flow[edge_idx]))
                sum_flow += pushed
                flow[edge_idx] += pushed
                flow[edge_idx ^ 1] -= pushed
                if sum_flow == limit: break
            if not sum_flow:  # 重要優化
                depth[i] = None
            return sum_flow

        n = len(G)
        max_flow = 0
        while True:
            bfs = [s]
            depth = [None] * n
            depth[s] = 0
            step = 1
            while bfs:
                nxt = []
                for i in bfs:
                    for j, edge_idx in G[i]:
                        if depth[j] is not None: continue  # visited
                        if flow[edge_idx] == cap[edge_idx]: continue
                        depth[j] = step
                        if j == t: break  # 到終點，bfs 結束
                        nxt.append(j)
                    else:
                        continue  # 未到終點，繼續 bfs 下個節點
                    break  # 到終點，bfs 結束
                else:  # 未到終點，繼續 bfs 下一輪
                    bfs = nxt
                    step += 1
                    continue
                break  # 到終點，bfs 結束
            else:
                break  # 未到終點，結束 Dinic 演算法

            max_flow += dfs(s, inf)
        return max_flow

    balance = [0] * n
    for a, b in edges:
        balance[a] -= lo
        balance[b] += lo

    new_edges = [(a, b, hi - lo) for a, b in edges]
    new_edges.append((t, s, inf))  # 轉換成無源匯點上下界可行流
    ss, tt = n, n + 1
    demand_sum = 0
    for i, v in enumerate(balance):
        if v > 0:
            new_edges.append((ss, i, v))
            demand_sum += v
        elif v < 0:
            new_edges.append((i, tt, -v))

    m = len(new_edges) << 1

    flow = [0] * m
    cap = [0] * m
    G = [[] for _ in range(n + 2)]
    for edge_idx, (i, j, w) in enumerate(new_edges):
        cap[edge_idx << 1] = w
        G[i].append((j, edge_idx << 1))
        G[j].append((i, edge_idx << 1 | 1))

    feasible_flow = dinic(ss, tt)
    if feasible_flow < demand_sum:
        return -1  # 無解

    G = [[] for _ in range(n)]
    for edge_idx, (i, j) in enumerate(edges):
        G[i].append((j, edge_idx << 1))
        G[j].append((i, edge_idx << 1 | 1))

    max_flow = dinic(t, s)
    return flow[len(edges) << 1] - max_flow

print(bounded_min_flow(n, edges, s, t, 1, 10 ** 10))
```

### 煙火 2025/5/9

> 給一字串 $s$ 與一些小字串 $t_i$，求 $s$ 可以拆解成多少種「$t_i$ 的組合」

使用 trie 並由後往前配對，能達到 $O(|s| ^ 2)$ 的時間複雜度；最佳解則使用 AC 自動機（Aho--Corasick Algorithm）同時配對所有字串，並只轉移需要轉移的狀態，時間複雜度為 $O(\text{轉移總次數}) = O(|s| + \sum |t_i|  + \sum t_i \text{ 在 } s \text{ 內出現的次數})$。

以下實作亦能處理 $t$ 重複的情況。

```python=
from collections import defaultdict, deque

def combinations(s: str, ts: list[str]) -> int:
    nested_dict = lambda: defaultdict(nested_dict)
    root = nested_dict()
    CNT = "#CNT"
    FAIL = "#FAIL"  # fail 指針
    VALID = "#VALID"  # 可轉移點(前一個有END的FAIL) (inspired by ChatGPT)
    DEPTH = "#DEPTH"

    def display(d: defaultdict, indent = 0) -> str:
        return "\n".join(
            f'{" - " * (i > 0 and indent)}{f"[{k}]{display(v, indent + 1)}"
            if isinstance(v, defaultdict) else f" #"}'
            for i, (k, v) in enumerate(
                ((k, v) for k, v in d.items() if k not in (FAIL, DEPTH, VALID))
            ))

    root[DEPTH] = 0
    for t in ts:
        dep = 0
        node = root
        for c in t:
            dep += 1
            node = node[c]
            node[DEPTH] = dep
        node[CNT] = node.get(CNT, 0) + 1

    root[FAIL] = root[VALID] = root

    queue = deque([root])
    while queue:
        node = queue.popleft()
        for k, v in node.items():
            if not k.isalpha(): continue
            queue.append(v)
            if node is root:
                v[FAIL] = root
            else:
                fail = node[FAIL]
                while k not in fail and fail is not root:
                    fail = fail[FAIL]
                v[FAIL] = fail.get(k, root)
            v[VALID] = v if CNT in v else v[FAIL][VALID]
    print(display(root))

    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    node = root
    for i, c in enumerate(s, start=1):
        while c not in node and node is not root:
            node = node[FAIL]
        node = node.get(c, root)
        fail = node[VALID]
        while fail is not root:
            dp[i] += dp[i - fail[DEPTH]] * fail.get(CNT)
            fail = fail[FAIL][VALID]
    return dp[n]

s = "abababaa"
ts = ["ab", "bab", "aba", "aa", "b"]

print(combinations(s, ts))
```

### 跳島遊戲 2025/6/14

> 無向圖上給定起終點，每個節點、邊都有流量上限。有 $k$ 流量在起點（其他節點初始流量皆為 $0$），每一回合每個節點上的流量可以流向四周，所有點決定好如何流動再進行流動，可以有部分流量留在原地。求至少幾回合才能到終點？

把每個帶權點也變成帶權邊，使新圖的點不帶權。接下來對「回合」二分搜，`check(round)` 建 `round + 1` 層圖，所有邊皆指向下一層（下一回合）的節點，最後在分層圖上跑最大流，判斷最大流是否 $>= k$。

時間複雜度是多項式但有億點炸。worst case 應該是 $O(\log_2(n + k) \times n ^ 2 m (n + k) ^ 3)$，其中 $O(n + k)$ 是答案上界。

最大流實作使用 Dinic。

```python=
from bisect import bisect_left
from itertools import count
from math import inf

def solve(nodes: list[int], edges: list[tuple[int, int]], k: int) -> int:
    # Dinic maxflow O(n²m)
    def dinic(
            n: int, edges: list[tuple[int, int, int]], s: int, t: int
    ) -> int:
        m = len(edges) << 1

        def dfs(i, flow):
            if i == t:
                return flow
            sum_flow = 0  # 此點以下的最大流
            for j, edge_idx in G[i]:
                weight_of_edge = weight_of_edges[edge_idx]
                if weight_of_edge == 0: continue
                if depth[j] != depth[i] + 1: continue
                pushed = dfs(j, min(flow, weight_of_edge))
                weight_of_edges[edge_idx] -= pushed
                weight_of_edges[edge_idx ^ 1] += pushed
                sum_flow += pushed
                flow -= pushed
                if flow == 0: break
            if sum_flow == 0:  # 重要優化
                depth[i] = None
            return sum_flow

        weight_of_edges = [0] * m
        G = [[] for _ in range(n)]
        for edge_idx, (i, j, w) in enumerate(edges):
            weight_of_edges[edge_idx << 1] = w
            G[i].append((j, edge_idx << 1))
            G[j].append((i, edge_idx << 1 | 1))

        ans = 0
        while True:
            bfs = [s]
            depth = [None] * n
            depth[s] = 0
            step = 1
            while bfs:
                nxt = []
                for i in bfs:
                    for j, edge_idx in G[i]:
                        if depth[j] is not None: continue  # visited
                        weight_of_edge = weight_of_edges[edge_idx]
                        if weight_of_edge == 0: continue  # 此路徑流量已滿
                        depth[j] = step
                        if j == t: break  # 到終點，bfs 結束
                        nxt.append(j)
                    else: continue  # 未到終點，繼續 bfs 下個節點
                    break  # 到終點，bfs 結束
                else:  # 未到終點，繼續 bfs 下一輪
                    bfs = nxt
                    step += 1
                    continue
                break  # 到終點，bfs 結束
            else: break  # 未到終點，結束 Dinic 演算法

            ans += dfs(s, inf)
        return ans

    def check(x: int) -> bool:
        new_edges = []
        nn = n << 1  # 每個節點變成一條邊 單層節點數*2
        for a, v in enumerate(nodes):  # 將每個節點變成邊
            a <<= 1
            new_edges.extend((i, i | 1, v) for i in range(a, a + nn * (x+1), nn))
            new_edges.extend((i, i + nn, v) for i in range(a, a + nn * x, nn))
        for a, b, w in edges:  # 每條無向邊 變成指向下一層時間的兩條有向邊
            frm, to = a << 1 | 1, (b << 1) + nn
            new_edges.extend((i, j, w) for i, j in zip(
                range(frm, frm + nn * x, nn), range(to, to + nn * x, nn))
            )
            frm, to = b << 1 | 1, (a << 1) + nn
            new_edges.extend((i, j, w) for i, j in zip(
                range(frm, frm + nn * x, nn), range(to, to + nn * x, nn)
            ))
        # 將所有時間流向終點的流量匯聚到虛匯點
        t = nn * (x + 1)
        new_edges.extend((i, t, k) for i in range(nn - 1, t, nn))
        res = dinic(t + 1, new_edges, 0, t)
        print(f"check(time={x}) -> {res = }")
        return res >= k

    n = len(nodes)
    hi = next(filter(check, (1 << i for i in count())))  # 倍增找出上界
    return bisect_left(  # 二分搜流量 >= k 的最小時間
        range(hi),
        True,
        key=check,
        lo=hi >> 1
    )
```

## 本文的連結

[高二 運算思維 課程成果精華](https://hackmd.io/@ericshen19555/while_high2_do_NPH)
<a href="https://hackmd.io/@ericshen19555/while_high2_do_NPH">
<img src="https://hackmd.io/_uploads/S1hvRUTrlg.png" alt="Image" width="30%"/>
</a>
<!-- ![image](https://hackmd.io/_uploads/S1hvRUTrlg.png) -->

## 附件

[所有題目 & code 的純紀錄](https://colab.research.google.com/drive/1Zua33r4O5c5U8umzuteKWIQGGAltdhdu?hl=en)
<a href="https://colab.research.google.com/drive/1Zua33r4O5c5U8umzuteKWIQGGAltdhdu?hl=en">
<img src="https://hackmd.io/_uploads/HJPCC8aSxg.png" alt="Image" width="30%"/>
</a>
<!-- ![image](https://hackmd.io/_uploads/HJPCC8aSxg.png) -->

[高二上資訊科課程成果](https://hackmd.io/@ericshen19555/Sk2IhIjOyl)
<a href="https://hackmd.io/@ericshen19555/Sk2IhIjOyl">
<img src="https://hackmd.io/_uploads/Hkg3APprxx.png" alt="Image" width="30%"/>
</a>
<!-- ![image](https://hackmd.io/_uploads/Hkg3APprxx.png) -->
