ZeroJudge 解題筆記：e409. Segment Tree 練習

作者：王一哲
日期：2026年5月22日


ZeroJudge 題目連結：e409. Segment Tree 練習

解題想法

這類型不斷地更新某個位置的值，不斷地查詢區域加總的題目，基本上都是用線段樹或二元索引樹處理。用 C++ 解題兩種寫法都能過關。用 Python 解題，遞迴版的線段樹與二元索引樹都太慢，後來是用非遞迴版的線段樹才過關。

Python 程式碼

遞迴版線段樹，從測資 #4 開始超時。

import sys
sys.setrecursionlimit(10000)
# --- 本題重點，自訂線段樹類別，單點更新，記錄區間最大值、最小值 ---
class SegmentTree:
    def __init__(self, data, n):
        self.data = data
        self.n = n
        self.imax = [0] * (4*self.n + 1)
        self.imin = [0] * (4*self.n + 1)
        if self.n > 0:
            self._build(0, 1, self.n)  # 題目的 A 是 1-index
    
    # --- 內部遞迴函式 ---
    def _build(self, node, start, end):
        # 遞迴出口
        if start == end:
            self.imax[node] = self.data[start]
            self.imin[node] = self.data[start]
            return
        # 遞迴，處理左、右半邊
        mid = (end - start) // 2 + start
        self._build(2*node + 1, start, mid)
        self._build(2*node + 2, mid + 1, end)
        # 更新 node 對應的最大值、最小值
        self.imax[node] = max(self.imax[2*node + 1], self.imax[2*node + 2])
        self.imin[node] = min(self.imin[2*node + 1], self.imin[2*node + 2])
    
    def _update(self, node, start, end, target, val):
        # 遞迴出口
        if start == end:
            self.imax[node] = val
            self.imin[node] = val
            self.data[target] = val
            return
        # 遞迴，處理左、右半邊
        mid = (end - start) // 2 + start
        if target <= mid:  # 在左側
            self._update(2*node + 1, start, mid, target, val)
        else:  # 在右側
            self._update(2*node + 2, mid + 1, end, target, val)
        # 更新 node 對應的最大值、最小值
        self.imax[node] = max(self.imax[2*node + 1], self.imax[2*node + 2])
        self.imin[node] = min(self.imin[2*node + 1], self.imin[2*node + 2])
    
    def _query(self, node, start, end, left, right):
        # 遞迴出口，[start, end] 與 [left, right] 沒有交集
        if end < left or start > right:
            return (-2000000000, 2000000000)
        # 遞迴出口，[left, right] 包含 [start, end]
        if left <= start and right >= end:
            return (self.imax[node], self.imin[node])
        # 遞迴，處理左、右半邊
        mid = (end - start) // 2 + start
        L = self._query(2*node + 1, start, mid, left, right)
        R = self._query(2*node + 2, mid + 1, end, left, right)
        return (max(L[0], R[0]), min(L[1], R[1]))
        
    # --- 外部呼叫函式 ---
    def update(self, target, val):
        self._update(0, 1, self.n, target, val)

    def query(self, left, right):
        res = self._query(0, 1, self.n, left, right)
        return res[0] - res[1]

# --- 主要的解題過程 ---
def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        MaxN, MaxQ = 1000005, 100005
        k = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        A = [0]*MaxN
        for i in range(1, k+1):
            A[i] = int(data[ptr])
            ptr += 1
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        C = [False]*MaxQ
        X = [0]*MaxQ
        Y = [0]*MaxQ

        # 題目中給定的産生資料函式
        def gen_dat():
            # 第一個迴圈
            limit = max(Q, N)
            i = k+1
            while i <= limit:
                A[i] = (A[i-2]*97 + A[i-1]*3) % m + 1
                i += 1
            # 第二個迴圈
            i = 1
            j = limit
            while i <= Q:
                C[i] = A[i] & 1
                X[i] = (A[i] + A[j]) % N + 1
                if C[i]: Y[i] = X[i]+ ( (A[i] << 3) + (A[j] << 5) + m ) % (N - X[i] + 1)
                else: Y[i] = ((A[i] << 3) + (A[j] << 5)) % m + 1
                i += 1
                j -= 1

        # 呼叫 gen_dat() 産生 A 的完整內容
        gen_dat()
        #print(A[:26])  # 印出前 26 項檢查內容
        # 讀取 operations 並輸出答案
        st = SegmentTree(A, N)
        for i in range(1, Q+1):
            op, x, y = C[i], X[i], Y[i]
            if op == 0:
                st.update(x, y)
            elif op == 1:
                result.append(f"{st.query(x, y):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：e406. Binary Indexed Tree 練習題

作者：王一哲
日期：2026年5月21日


ZeroJudge 題目連結：e406. Binary Indexed Tree 練習題

解題想法

這類型不斷地更新某個位置的值，不斷地查詢區域加總的題目，基本上都是用線段樹或二元索引樹處理。用 C++ 解題兩種寫法都能過關。用 Python 解題，則會因為線段樹需要遞迴很多次，速度太慢，無法過關。

Python 程式碼

二元索引樹，使用時間約為 1.1 s，記憶體約為 73 MB，通過測試。

class FenwickTree:
    def __init__(self, A):
        self.n = len(A) - 1
        self.A = A[:]
        self.tree = A[:]
        for i in range(1, self.n + 1):
            parent_idx = i + self._lowbit(i)
            if parent_idx <= self.n:
                self.tree[parent_idx] += self.tree[i]
    
    def _lowbit(self, x):
        return x & (-x)
    
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += self._lowbit(i)
    
    def update_val(self, i, val):
        delta = val - self.A[i]
        self.A[i] = val
        self.update(i, delta)
    
    def query(self, i):
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= self._lowbit(i)
        return total

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        k = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        A = [0] + list(map(int, data[ptr:ptr+k]))
        ptr += k
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        limit = max(N, Q)
        A += [0] * (limit - k + 1)  # 調整 A 的長度
        # 第1個迴圈，填入 A[k+1] ~ A[limit]
        for i in range(k+1, limit + 1):
            A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1
        
        # 第2個迴圈，計算 op, x, y 同時查詢或更新
        bit = FenwickTree(A)
        j = limit
        for i in range(1, Q+1):
            op = A[i] & 1
            x = (A[i] + A[j]) % N + 1
            if op:  # 查詢
                y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1)
                ans = (bit.query(y) - bit.query(x-1)) % m
                result.append(f"{ans:d}\n")
            else:  # 更新
                y = ((A[i] << 3) + (A[j] << 5)) % m + 1
                bit.update_val(x, y)
            j -= 1
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d272. 11583 - Alien DNA

作者：王一哲
日期：2026年5月20日


ZeroJudge 題目連結：d272. 11583 - Alien DNA

解題想法

依序檢查每個 DNA 序列，取新序列與舊序列的交集，如果交集是空集合，要切一刀。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 8.2 MB，通過測試。

t = int(input())  # t 組測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # 這組測資有 n 個序列
    common = set(list(input()))  # 共同的鹼基字母，預設為第 1 個序列
    cut = 0  # 切幾刀
    for _ in range(1, n):  # 讀取 n-1 個序列
        dna = set(list(input()))  # 新的序列包含的鹼基字母
        common.intersection_update(dna)  # 取交集更新 common
        if not common:  # 如果 common 是空的
            cut += 1  # cut 加 1
            common = dna  # 更新 common 為 dna
    print(cut)  # 印出答案

ZeroJudge 解題筆記：d269. 11579 - Triangle Trouble

作者：王一哲
日期：2026年5月19日


ZeroJudge 題目連結：d269. 11579 - Triangle Trouble

解題想法

讀取一行測資，將 $n$ 個邊長由大到小排序，再依序讀取連續 3 個邊長 $a, b, c$，如果最長的邊 $a$ 大於等於較短的兩個邊 $b, c$ 加總，無法組成三角形；反之，用海龍公式計算三角形面積。

Python 程式碼

使用時間約為 67 ms，記憶體約為 14.4 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    T = int(data[0])  # T 組測資
    ptr = 1
    while ptr < len(data):  # 執行 T 次
        n = int(data[ptr])  # 首項是邊的數量
        ptr += 1
        edges = sorted(map(float, data[ptr:ptr+n]), reverse=True)  # 邊長，由大到小排序
        ptr += n
        imax = 0.0  # 最大面積
        for i in range(n-2):  # 依序讀取邊長，每次 3 項
            a, b, c = edges[i:i+3]  # 邊長
            if a >= b + c:  # 最長的邊大於等於另外兩個邊相加
                continue  # 無法組成三角形，找下一組
            s = (a + b + c) * 0.5  # 用海龍公式求三角形面積
            area = (s * (s-a) * (s-b) * (s-c))**0.5
            if area > imax: imax = area  # 更新最大值
        result.append(f"{imax:.2f}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d261. 11000 - Bee

作者：王一哲
日期：2026年5月18日


ZeroJudge 題目連結：d261. 11000 - Bee

解題想法

只有第一隻母蜂不會死，剩下的公蜂、母蜂每年結束都會死去。第 $i$ 年的母蜂數量等於 $1$ 加上第 $i-1$ 年的公蜂數量，第 $i$ 年的公蜂數量等於第 $i-1$ 年的公蜂加母蜂數量。

Python 程式碼

使用時間約為 15 ms，記憶體約為 8.4 MB，通過測試。

def solve():
    import sys

    maxn = 50
    f = [0]*(maxn + 1)
    m = [0]*(maxn + 1)
    f[0] = 1
    for i in range(1, maxn + 1):
        f[i] = 1 + m[i-1]
        m[i] = f[i-1] + m[i-1]

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == -1: break
        result.append(f"{m[n]:d} {f[n]+m[n]:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d260. 11455 - Behold my quadrangle

作者：王一哲
日期：2026年5月17日


ZeroJudge 題目連結：d260. 11455 - Behold my quadrangle

解題想法

先將 4 個邊排序後分別存入 $a, b, c, d$，如果 $a, b, c, d$ 皆相等，輸出 square；如果 $a$ 等於 $b$ 且 $c$ 等於 $d$，輸出 rectangle；如果 $a + b + c > d$，輸出 quadrangle；其它狀況輸出 banana。

Python 程式碼

使用時間約為 22 ms，記憶體約為 8.4 MB，通過測試。

T = int(input())
for _ in range(T):
    a, b, c, d = sorted(map(int, input().split()))
    if a == b == c == d:
        print("square")
    elif a == b and c == d:
        print("rectangle")
    elif a + b + c > d:
        print("quadrangle")
    else:
        print("banana")

如果是多筆測資可以改成這樣，使用時間約為 15 ms，記憶體約為 8.2 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        T = int(data[ptr])
        ptr += 1
        for _ in range(T):
            a, b, c, d = sorted(map(int, data[ptr:ptr+4]))
            ptr += 4
            if a == b == c == d:
                result.append("square\n")
            elif a == b and c == d:
                result.append("rectangle\n")
            elif a + b + c > d:
                result.append("quadrangle\n")
            else:
                result.append("banana\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d258. 11313 - Gourmet Games

作者：王一哲
日期：2026年5月16日


ZeroJudge 題目連結：d258. 11313 - Gourmet Games

解題想法

用一個 while 迴圈，當 $n \geq m$ 時繼續執行，每次執行時將集數 $cnt$ 加上 n//m，$n$ 改為 n = n//m + n%m。由於最後只能有一個優勝者，$n$ 最後必須等於 1，如果 $n$ 等於 1 輸出 $cnt$，反之輸出 cannot do this。

Python 程式碼

使用時間約為 29 ms，記憶體約為 8.2 MB，通過測試。

t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    cnt = 0
    while n >= m:
        cnt += n//m
        n = n//m + n%m
    print(cnt if n == 1 else "cannot do this")

使用時間約為 30 ms，記憶體約為 10.6 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split() 
    t = int(data[0])
    ptr = 1
    for _ in range(t):  # 只能跑 t 次，否則會吃 OLE
        n = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        cnt = 0
        while n >= m:
            cnt += n//m
            n = n//m + n%m
        if n == 1: result.append(f"{cnt:d}\n")
        else: result.append("cannot do this\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d256. 11388 - GCD LCM

作者：王一哲
日期：2026年5月15日


ZeroJudge 題目連結：d256. 11388 - GCD LCM

解題想法

假設兩個數字 $a, b$ 的最大公因數 $G = GCD(a, b)$，最小公倍數 $L = LCM(a, b)$，而且題目要求「如果有多組解，輸出 $a$ 最小的一組」，答案就是 $a = G$，$b = L$，因為 $a$ 之中不能有 $G$ 以外大於 $1$ 的因數。如果 $L$ 不能被 $G$ 整除，則輸出 $-1$。

Python 程式碼

使用時間約為 15 ms，記憶體約為 8.8 MB，通過測試。

T = int(input())
for _ in range(T):
    G, L = map(int, input().split())
    if L%G != 0: print("-1")
    else: print(G, L)

C++ 程式碼

使用時間約為 1 ms，記憶體約為 1.5 MB，通過測試。

#include <cstdio>

int main() {
    int T; scanf("%d", &T);
    for(int t=0; t<T; t++) {
        int G, L; scanf("%d %d", &G, &L);
        if (L%G != 0) puts("-1");
        else printf("%d %d\n", G, L);
    }
    return 0;
}

ZeroJudge 解題筆記：d253. 00674 - Coin Change

作者：王一哲
日期：2026年5月14日


ZeroJudge 題目連結：d253. 00674 - Coin Change

解題想法

每種面額的硬幣使用數量不限，是無限背包問題，用動態規畫解題，假設 $dp[i]$ 是總金額 i 的組合數，初始值是 $dp[0] = 1$。先建表，計算總金額 0 到 7489 的組合數，再讀取測資、查表、輸出答案。

Python 程式碼

使用時間約為 12 ms，記憶體約為 9.9 MB，通過測試。

def solve():
    import sys

    coins = (1, 5, 10, 25, 50)  # 硬幣面額
    maxn = 7489
    dp = [0]*(maxn + 1)  # 總金額 i 有幾種組合
    dp[0] = 1  # 初始值，金額 0 只有 1 種組合
    for coin in coins:  # 無限背包問題
        for i in range(coin, maxn + 1):
            dp[i] += dp[i - coin]
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        result.append(f"{dp[n]:d}\n")
    
    sys.stdout.write("".join(result))
    
if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d242. 00481 - What Goes Up

作者：王一哲
日期：2026年5月13日


ZeroJudge 題目連結：d242. 00481 - What Goes Up

解題想法

這題要找最長遞增子序列 (longest increasing subsequence, LIS) 的內容，網路上有不少的教學。我是記錄目前 lis 對應的字元索引值，最後再將這些索引值對應的字元組成字串，反序後輸出。

Python 程式碼

使用時間約為 0.9 s，記憶體約為 64.9 MB，通過測試。

def get_lis(nums):
    if not nums: return []
    n = len(nums)
    prev = [-1]*n
    tails = []
    for i, num in enumerate(nums):
        low, high = 0, len(tails)-1
        while low <= high:
            mid = (high - low) // 2 + low
            if num > nums[tails[mid]]: low = mid + 1
            else: high = mid - 1
        if low == len(tails): tails.append(i)
        else: tails[low] = i
        if low > 0: prev[i] = tails[low-1]
    lis = []
    curr = tails[-1]
    while curr != -1:
        lis.append(nums[curr])
        curr = prev[curr]
    return lis[::-1]

def solve():
    import sys
    
    result = []
    arr = list(map(int, sys.stdin.read().split()))
    lis = get_lis(arr)
    result.append(f"{len(lis):d}\n-\n")
    for v in lis: result.append(f"{v:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()