# 高二 運算思維 課程成果精華
> 作者：沈宗叡（暴力又被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%"/>
<!--  -->
而 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>
<!--  -->
## 附件
[所有題目 & 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>
<!--  -->
[高二上資訊科課程成果](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>
<!--  -->
Sign in with Wallet
Connect another wallet