LeetCode 解題筆記：2126. Destroying Asteroids

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


LeetCode 題目連結：2126. Destroying Asteroids

解題想法

中級難度的題目。我看到題目時最直接的想法，是先將小行星的質量由小到大排序，再依序讀取小行星的質量 a，如果行星質量 mass 大於等於 a，將 mass 加上 a；反之回傳 False。如果測試完所有的小行星質量都不會回傳 False，最後則回傳 True。

後來又想到，既然每次都要取出所有小行星質量之中的最小值，應該也可以用最小優先佇列解題。先將所有的小行星質量存入最小優先佇列 pq 之中，再用 while 迴圈取出 pq 之中的最小值與 mass 比較，但這樣寫多了掃過所有小行星質量花費的時間，反而比直接排序慢。

那如果稍微修改一下寫法，先掃過所有小行星質量一次，如果行星質量 mass 大於等於這個小行星質量 a，將 mass 加上 a；反之將 a 加入最小優先佇列 pq 之中，時間複雜度 $O(n)$。最後再用 while 迴圈取出 pq 之中的最小值與 mass 比較，pq 插入、刪除資料的時間複雜度為 $O(log n)$，由於 pq 之中的資料數量一定小於測資給的小行星數量，速度比前兩種寫法還快。

Python 程式碼

排序。Runtime: 71 ms, beats 73.70%. Memory: 34.01 MB, beats 30.13%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        for a in sorted(asteroids):
            if mass >= a:
                mass += a
            else:
                return False
        return True

heapq。Runtime: 269 ms, beats 5.37%. Memory: 30.22 MB, beats 93.86%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        heapq.heapify(asteroids)
        while asteroids:
            a = heapq.heappop(asteroids)
            if mass >= a:
                mass += a
            else:
                return False
        return True

只存部分資料到 heapq 之中。Runtime: 62 ms, beats 95.20%. Memory: 33.66 MB, beats 90.21%.

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        pq = []
        for a in asteroids:
            if mass >= a:
                mass += a
            else:
                heapq.heappush(pq, a)
        while pq:
            a = heapq.heappop(pq)
            if mass >= a:
                mass += a
            else:
                return False
        return True

ZeroJudge 解題筆記：d282. 11015 - 05-2 Rendezvous

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


ZeroJudge 題目連結：d282. 11015 - 05-2 Rendezvous

解題想法

這題考 Dijkstra's algorithm，先找出以節點 $k$ 為中繼點，從節點 $i$ 走到節點 $j$ 的成本，更新 $i$ 到 $j$ 的最低成本。

Python 程式碼

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

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    ca = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr+1])
        ptr += 2
        if n == 0 and m == 0: break
        ca += 1
        # 讀取名字
        names = []
        for _ in range(n):
            names.append(data[ptr])
            ptr += 1
        # 初始化距離矩陣
        dp = [[float('inf')]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 0
        for _ in range(m):
            u = int(data[ptr])
            v = int(data[ptr+1])
            w = int(data[ptr+2])
            ptr += 3
            u -= 1
            v -= 1
            dp[u][v] = w
            dp[v][u] = w
        # Dijkstra's algorithm
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        # 找最低成本
        ans, imin = 0, float('inf')
        for i in range(n):
            cost = sum(dp[i][j] for j in range(n))
            if cost < imin:
                imin = cost
                ans = i
        result.append(f"Case #{ca:d} : {names[ans]}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d281. 10499 - The Land of Justice

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


ZeroJudge 題目連結：d281. 10499 - The Land of Justice

解題想法

不論切成幾等份，整個球外側的表面積皆為 $4 \pi r^2$。如果切成 $n$ 等份，$n \geq 2$ 才會有新的切面，每一等份會增加表面積 $\pi r^2$，因此答案為 $$ \frac{n \pi r^2}{4 \pi r^2} \times 100\% = 25n \% $$ 題目中的四捨五入根本用不到。

Python 程式碼

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

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d279. 00280 - Vertex

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


ZeroJudge 題目連結：d279. 00280 - Vertex

解題想法

這題有兩個奇怪的地方。 第一個是起點不算可以走到的點，例如範例測資的圖，節點1可以到節點2，節點2只能走到節點2，節點3可以走到節點1、2；輸出節點1無法走到的節點數量及編號才會是 2 1 3。 第二個是實際測資與中文的題目敘述不合，但其實是中文翻譯錯誤，多張圖之間沒有用一行單獨的 0 分隔，只有在全部的測資都結束後才會有一行單獨的 0。英文版題目在此，原題敘述是

If there are no more graphs, the next line of the file will contain only the integer ‘0’.

Python 程式碼

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

import sys

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    """ 讀取測資，建立圖的關係 """
    graph = [[] for _ in range(n+1)]
    for row in sys.stdin:
        if row.strip() == "0": break
        arr = list(map(int, row.split()))
        u = arr[0]
        for v in arr[1:-1]:
            graph[u].append(v)
    """ 讀取要檢查的起點 """
    data = list(map(int, sys.stdin.readline().split()))
    m = data[0]  # 起點數量，用不到
    for start in data[1:]:  # 依序測試每一個起點，用 BFS 找連通的節點
        que = [start]
        head = 0
        visited = [False]*(n+1)
        while head < len(que):
            u = que[head]
            head += 1
            for v in graph[u]:
                if visited[v]: continue
                visited[v] = True
                que.append(v)
        ### End of BFS ###
        ans = [i for i in range(1, n+1) if not visited[i]]  # 無法走到的節點
        result.append(f"{len(ans):d} " + " ".join(map(str, ans)) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：d796. 區域調查

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


ZeroJudge 題目連結：d796. 區域調查

解題想法

這題理論上可以用線段樹解題，但是程式碼非常長，我只寫了二元索引樹版本，0.3 s 過關，Python 會超時。

Python 程式碼

測資 #0 50%，4.7s，90.3 MB。測資 #1 開始超時。如果把二維串列攤平成一維串列，應該還可以再快一點。

class BIT2D:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.arr = [[0]*(m+1) for _ in range(n+1)]
        self.tree = [[0]*(m+1) for _ in range(n+1)]

    def _lowbit(self, x):
        return x & (-x)
    
    def _update(self, x, y, delta):
        i = x
        while i <= self.n:
            j = y
            while j <= self.m:
                self.tree[i][j] += delta
                j += self._lowbit(j)
            i += self._lowbit(i)
    
    def _query(self, x, y):
        total = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                total += self.tree[i][j]
                j -= self._lowbit(j)
            i -= self._lowbit(i)
        return total

    def update_val(self, x, y, val):
        delta = val - self.arr[x][y]
        self._update(x, y, delta)
        self.arr[x][y] = val

    def query_range(self, x1, y1, x2, y2):
        if x1 > x2: x1, x2 = x2, x1
        if y1 > y2: y1, y2 = y2, y1
        return self._query(x2, y2) - self._query(x1 - 1, y2) - self._query(x2, y1 - 1) + self._query(x1 - 1, y1 - 1)

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        N = int(data[ptr])
        Q = int(data[ptr+1])
        ptr += 2
        bit = BIT2D(N, N)
        for i in range(1, N+1):
            for j in range(1, N+1):
                v = int(data[ptr])
                ptr += 1
                bit.update_val(i, j, v)
        for _ in range(Q):
            op = int(data[ptr])
            ptr += 1
            if op == 1:
                x1 = int(data[ptr])
                y1 = int(data[ptr+1])
                x2 = int(data[ptr+2])
                y2 = int(data[ptr+3])
                ptr += 4
                ans = bit.query_range(x1, y1, x2, y2)
                result.append(f"{ans:d}\n")
            else:
                x = int(data[ptr])
                y = int(data[ptr+1])
                v = int(data[ptr+2])
                ptr += 3
                bit.update_val(x, y, v)
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d794. 世界排名

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


ZeroJudge 題目連結：d794. 世界排名

解題想法

d788. 排名順序 的加強版，分數 $M$ 改成 $1 \leq M \leq 2^{64} - 1$。 由於分數差異極大，而且不是每個分數都有人，還要再加上離散化，用分數由小到大的順序當成新的編號，用編號存入線段樹或二元索引樹之中解題。這題理論上可以用線段樹解題，但是 Python 的速度太慢，即使程式碼邏輯正確仍會超時，改用二元索引樹才過關。

Python 程式碼

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

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

    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 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):
        N = int(data[ptr])
        ptr += 1
        scores = list(map(int, data[ptr:ptr+N]))  # 讀取 N 個成績
        ptr += N
        sorted_unique = sorted(set(scores))  # 去重並排序
        rank_map = {val: rank for rank, val in enumerate(sorted_unique, start=1)}
        bit = FenwickTree(N)
        for i in range(1, N+1):
            rank = rank_map[scores[i-1]]  # 分數轉成順序
            bit.update(rank, 1)  # rank 的人數加 1
            result.append(f"{i - bit.query(rank-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d788. 排名順序

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


ZeroJudge 題目連結：d788. 排名順序

解題想法

這題理論上可以用線段樹解題，但是 Python 的速度太慢，即使程式碼邏輯正確仍會超時，改用二元索引樹才過關。用分數當作 tree 的索引值，tree[i] 的值代表這個分數的人數。假設每次加入討論的人分數為 x，先執行 bit.update(x)，再計算 bit.query(x-1)，也就是分數比自己低的人數，則自己的名次 = 總人數 - bit.query(x-1)。

Python 程式碼

線段樹，超時。

# --- 自訂線段樹類別，單點修改 ---
class SegmentTree:
    def __init__(self, n):
        self.n = n
        self.data = [0]*self.n  
        self.tree = [0]*(4*self.n)  # 長度開 4 倍確保不會出界
        # 由於本題一開始 self.data, self.tree 皆為 0，省略 _build

    def _update(self, node, start, end, target, val):
        if start == end:
            self.tree[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)
        self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def _query(self, node, start, end, left, right):
        if end < left or start > right:
            return 0
        if left <= start and right >= end:
            return self.tree[node]
        mid = (end - start) // 2 + start
        lsum = self._query(2*node + 1, start, mid, left, right)
        rsum = self._query(2*node + 2, mid + 1, end, left, right)
        return lsum + rsum

    # --- 外部呼叫函式 ---
    def update(self, target, val):
        self._update(0, 0, self.n - 1, target, val)

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

def solve():
    import sys
    
    maxn = 100001
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        st = SegmentTree(maxn)  # 分數 0 ~ 100000 是否有人
        for i in range(1, n+1):
            m = int(data[ptr])
            ptr += 1
            st.update(m, 1)
            # 分數 m 的名次 = 總人數 - 分數 0 到 m-1 的人數
            result.append(f"{i - st.query(0, m-1):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：e457. 也是 Segment Tree 練習

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


ZeroJudge 題目連結：e457. 也是 Segment Tree 練習

解題想法

單點修改，查詢區間連乘的正負號，不需要真的存數字，如果數字大於 0 存 1，等於 0 存 0，小於 0 存 -1。

Python 程式碼

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

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.data = [0]
        for d in data:
            if d > 0:
                self.data.append(1)
            elif d == 0:
                self.data.append(0)
            else:
                self.data.append(-1)
        self.tree = [0]*(4 * self.n)
        if self.n > 0:
            self._build(0, 1, self.n)
    
    # --- 內部遞迴函式 ---
    def _build(self, node, start, end):
        if start == end:
            if self.data[start] > 0:
                self.tree[node] = 1
            elif self.data[start] == 0:
                self.tree[node] = 0
            else:
                self.tree[node] = -1
            return

        mid = (end - start) // 2 + start
        self._build(2*node + 1, start, mid)
        self._build(2*node + 2, mid + 1, end)
        self.tree[node] = self.tree[2*node + 1] * self.tree[2*node + 2]

    def _update(self, node, start, end, target, val):
        if start == end:
            if val > 0:
                self.tree[node] = 1
                self.data[target] = 1
            elif val == 0:
                self.tree[node] = 0
                self.data[target] = 0
            else:
                self.tree[node] = -1
                self.data[target] = -1
            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)
        self.tree[node] = self.tree[2*node + 1] * self.tree[2*node + 2]

    def _query(self, node, start, end, left, right):
        if end < left or start > right:
            return 1
        if left <= start and right >= end:
            return self.tree[node]
        mid = (end - start) // 2 + start
        lval = self._query(2*node + 1, start, mid, left, right)
        rval = self._query(2*node + 2, mid + 1, end, left, right)
        return lval * rval
    
    # --- 外部呼叫函式 ---
    def update(self, target, val):
        self._update(0, 1, self.n, target, val)

    def query(self, left, right):
        return self._query(0, 1, self.n, left, right)

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        k = int(data[ptr+1])
        ptr += 2
        nums = list(map(int, data[ptr:ptr+n]))
        ptr += n
        st = SegmentTree(nums)
        for i in range(k):
            op = data[ptr]
            x = int(data[ptr+1])
            y = int(data[ptr+2])
            ptr += 3
            if op == "C":
                st.update(x, y)
            else:
                z = st.query(x, y)
                if z == 1:
                    result.append("+")
                elif z == 0:
                    result.append("0")
                else:
                    result.append("-")
        result.append("\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：e437. Segment Tree 練習2 + 區間修改

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


ZeroJudge 題目連結：e437. Segment Tree 練習2 + 區間修改

解題想法

這題我只有寫 C++ 線段樹版本。

C++ 程式碼

線段樹，使用時間約為 80 ms，記憶體約為 45 MB，通過測試。

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
typedef long long LL;
using namespace std;

struct QueryResult {  // 回傳查詢結果用的結構體
    LL sum_val;
    int max_val, min_val;
};

/* 本題重點，自訂線段樹類別，區間更新，記錄區間加總、最大值、最小值 */
class SegmentTree {
private:
    int n, mod;
    vector<int> data, imax, imin, lazy;
    vector<LL> isum;
    vector<bool> has_lazy;
    
    /* 內部遞迴函式 */
    void _push_up(int node) {
        isum[node] = (isum[2*node + 1] + isum[2*node + 2]) % mod;
        imax[node] = max(imax[2*node + 1], imax[2*node + 2]);
        imin[node] = min(imin[2*node + 1], imin[2*node + 2]);
    }

    void _build(int node, int start, int end) {
        // 遞迴出口
        if (start == end) {
            isum[node] = data[start] % mod;
            imax[node] = data[start];
            imin[node] = data[start];
            return;
        }
        // 遞迴，處理左、右半邊
        int mid = (end - start) / 2 + start;
        _build(2*node + 1, start, mid);
        _build(2*node + 2, mid + 1, end);
        _push_up(node);
    }
    
    void _push_down(int node, int start, int end) {
        if (has_lazy[node]) {
            int mid = (end - start) / 2 + start, val = lazy[node];
            // 處理左半邊
            int left_len = mid - start + 1;
            isum[2*node + 1] = (1LL * val * left_len) % mod;
            imax[2*node + 1] = val;
            imin[2*node + 1] = val;
            lazy[2*node + 1] = val;
            has_lazy[2*node + 1] = true;
            // 處理右邊
            int right_len = end - mid;
            isum[2*node + 2] = (1LL * val * right_len) % mod;
            imax[2*node + 2] = val;
            imin[2*node + 2] = val;
            lazy[2*node + 2] = val;
            has_lazy[2*node + 2] = true;
            has_lazy[node] = false;
        }
    }

    void _update(int node, int start, int end, int left, int right, int val) {
        // 遞迴出口，[start, end] 與 [left, right] 沒有交集
        if (end < left || start > right) return;
        // 遞迴出口，[left, right] 包含 [start, end]，更新 node 對應的值及標記
        if (left <= start && right >= end) {
            isum[node] = (1LL * val * (end - start + 1)) % mod;
            imax[node] = val;
            imin[node] = val;
            lazy[node] = val;
            has_lazy[node] = true;
            return;
        }
        // 先呼叫 _push_down，將標記往下傳，再用遞迴處理左、右兩半
        _push_down(node, start, end);
        int mid = (end - start) / 2 + start;
        _update(2*node + 1, start, mid, left, right, val);
        _update(2*node + 2, mid + 1, end, left, right, val);
        // 更新 node 對應的加總、最大值、最小值
        _push_up(node);
    }
    
    // 合併三個查詢功能
    QueryResult _query(int node, int start, int end, int left, int right) {
        // 遞迴出口，[start, end] 與 [left, right] 沒有交集
        if (end < left || start > right) {
            return {0, -2000000000, 2000000000};  // 0 給加總，max 給極小值，min 給極大值
        }
        // 遞迴出口，[left, right] 包含 [start, end]
        if (left <= start && right >= end) {
            return {isum[node], imax[node], imin[node]};
        }
        // 先 _push_down 再遞迴
        _push_down(node, start, end);
        int mid = (end - start) / 2 + start;
        QueryResult L = _query(2*node + 1, start, mid, left, right);
        QueryResult R = _query(2*node + 2, mid + 1, end, left, right);
        QueryResult res;
        res.sum_val = (L.sum_val + R.sum_val) % mod;
        res.max_val = max(L.max_val, R.max_val);
        res.min_val = min(L.min_val, R.min_val);
        return res;
    }

public:
    // 建構子，只計算 A[1] ~ A[N] 的最大值、最小值，不要對建 N 之後的值建立線段樹
    SegmentTree(const vector<int>& input_data, int target_n, int m) {
        data = input_data;
        n = target_n;
        mod = m;
        int tree_size = 4*n + 1;
        has_lazy.assign(tree_size, false);
        lazy.assign(tree_size, 0);
        isum.assign(tree_size, 0);
        imax.assign(tree_size, 0);
        imin.assign(tree_size, 0);
        if (n > 0) {
            _build(0, 1, n);
        }
    }

    /* 外部呼叫函式 */
    void update(int left, int right, int val) {
        _update(0, 1, n, left, right, val);
    }

    pair<int, int> query(int left, int right) {
        QueryResult res = _query(0, 1, n, left, right);
        return make_pair(res.sum_val, res.max_val - res.min_val);
    }
};

int main() {
    // 讀取測資
    int k, m, N, Q;
    scanf("%d %d", &k, &m);
    vector<int> A (k+1, 0);
    for(int i=1; i<=k; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d %d", &N, &Q);
    int limit = max(N, Q);
    A.resize(limit + 1);  // 調整 A 的長度
    // 第1個迴圈，填入 A[k+1] ~ A[limit]
    for(int i=k+1; i<=limit; i++) {
        A[i] = (A[i-2] * 97 + A[i-1] * 3) % m + 1;
    }
    // 第2個迴圈，計算 op, x, y 同時查詢或更新線段樹
    SegmentTree st(A, N, m);
    int j = limit;
    for(int i=1; i<=Q; i++) {
        bool op = A[i] & 1;
        int x = (A[i] + A[j]) % N + 1;
        int y = x + ((A[i] << 3) + (A[j] << 5) + m) % (N - x + 1);
        if (op) {  // 查詢
            auto it = st.query(x, y);
            printf("%d %d\n", it.first, it.second);
        } else {  // 更新
            int z = ((A[i] << 3) + (A[j] << 5)) % m + 1;
            st.update(x, y, z);
            //printf("%d %d %d %d\n", A[i], x, y, z);
        }
        j--;
    }
    return 0;
}

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()

ZeroJudge 解題筆記：d224. 11296 - Counting Solutions to an Integral Equation

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


ZeroJudge 題目連結：d224. 11296 - Counting Solutions to an Integral Equation

解題想法

這題可以用公式解或是動態規畫。 $$ x + 2y + 2z = n ~\Rightarrow~ x = n - 2(y + z) = n - 2k $$ 因為題目要求 $x, y, z$ 為 0 或正整數，因此 $$ y + z = k ~\Rightarrow~ 0 \leq k \leq \left \lfloor \frac{n}{2} \right \rfloor = m $$ 符合條件的 $(y, z)$ 為 $(0, k), (1, k-1), \dots, (k, 0)$，共有 $k + 1$ 組，因此所有的解數量為 $$ \sum_{k=0}^{m} (k+1) = 0 + 1 + 2 + \dots + (m+1) = \frac{(m+1)(m+2)}{2} $$ 如果用 $dp[i]$ 代表 $x + 2y + 2z = i$ 時的解數量，起始條件為 $dp[0] = 1$。$x = 0, 1, 2, \dots, n$，當 $x$ 加 1 時，解的數量會更新為 $$ dp[i] = dp[i] + dp[i-1] $$ $y, z = 0, 1, 2, \dots, \left \lfloor \frac{n}{2} \right \rfloor$，則 $y$ 或 $z$ 加 1 時，解的數量會更新為 $$ dp[i] = dp[i] + dp[i-2] $$

Python 程式碼

公式解，使用時間約為 40 ms，記憶體約為 11.4 MB，通過測試。

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

動態規畫，使用時間約為 0.4 s，記憶體約為 63.6 MB，通過測試。

def solve():
    import sys

    maxn = 1000000
    dp = [0]*(maxn+1)
    dp[0] = 1  # i = 0，1 組解
    for i in range(1, maxn+1):  # 加入 x
        dp[i] += dp[i-1]
    for i in range(2, maxn+1):  # 加入 y
        dp[i] += dp[i-2]
    for i in range(2, maxn+1):  # 加入 z
        dp[i] += dp[i-2]

    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 解題筆記：d018. 字串讀取練習

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


ZeroJudge 題目連結：d018. 字串讀取練習

解題想法

這題的輸出格式對 Python 使用者而言很麻煩，答案如果是小數，輸出的位數不固定，而且要捨去後面的0；如果是整數則連小數點都不能輸出。後來是將相減的結果先轉成字串，再用 rstrip('0') 去除後方的 0，再接著用 rstrip('.') 去除後方的小數點，如果答案是小數，此時字串最後面是數字，小數點不會被刪除。

Python 程式碼

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

def format_float(num):
    return f"{num:.6f}".rstrip('0').rstrip('.')

while True:
    try:
        data = input().split()
        even, odd = 0, 0
        for d in data:
            k, v = d.split(':')
            k = int(k)
            v = float(v)
            if k%2 == 0: even += v
            else: odd += v
        ans = format_float(odd - even)
        print(ans)
    except EOFError:
        break

ZeroJudge 解題筆記：c929. 蝸牛老師的點名單-續

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


ZeroJudge 題目連結：c929. 蝸牛老師的點名單-續

解題想法

這題如果用 Python 解題很快，只要先讀取分割用的字串，再將第二行字串用 split 代入第一行字串分割就好了。如果用 C++ 解題，則要用 getline 讀取整行字串，再依序檢查第二行字串的每個字元，找出分割用字串的索引值，再用 substr 取出子字串。

Python 程式碼

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

s = input()
for t in input().split(s):
    print(t)

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

s = input()  # 分割用的字串
t = input()  # 要被分割的字串
n = len(s)  # 字串長度
pre = 0  # 前一個分割點
idx = t.find(s)  # 從 t 之中找 s 的索引值
while idx != -1:  # -1 代表沒找到
    print(t[pre:idx])  # 印出分割後的子字串
    pre = idx + n  # 更新 pre
    idx = t.find(s, pre)  # 從 s[pre:] 找 t
if pre > 0: print(t[pre:])  # 最後一段
else: print(t)  # 沒有分割

ZeroJudge 解題筆記：b982. YoJudge 預練(空間之章)

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


ZeroJudge 題目連結：b982. YoJudge 預練(空間之章)

解題想法

這題我是用最直接的寫法，先找出字串 s 中 g, m, k, byte, bit, . 的索引值，再寫很多層的 if, else 判斷 s 的格式，依照格式分割字串、換算答案。

Python 程式碼

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

while True:
    try:
        s = input()
        ans = 0
        if "gb" in s:
            i = s.find("gb")
            a = int(s[:i])
            ans = 8*a*10**9
        elif "mb" in s:
            i = s.find("mb")
            a = int(s[:i])
            ans = 8*a*10**6
        elif "kb" in s:
            i = s.find("kb")
            if "." in s:
                j = s.find(".")
                a = int(s[:j])
                b = int(s[j+1:i])
                ans = 8*(a*10**3 + b*100)
            else:
                a = int(s[:i])
                ans = 8*a*10**3
        elif "byte" in s:
            i = s.find("byte")
            if "." in s:
                j = s.find(".")
                a = int(s[:j])
                b = int(s[j+1:i])
                ans = 8*a + b
            else:
                ans = 8*int(s[:i])
        elif "bit" in s:
            i = s.find("bit")
            ans = int(s[:i])
        elif "g" in s and "m" in s and "k" in s:
            i = s.find("g")
            j = s.find("m")
            k = s.find("k")
            a = int(s[:i])
            b = int(s[i+1:j])
            c = int(s[j+1:k])
            ans = 8*(a*10**9 + b*10**6 + c*10**3)
        elif "g" in s and "m" in s:
            i = s.find("g")
            j = s.find("m")
            a = int(s[:i])
            b = int(s[i+1:j])
            ans = 8*(a*10**9 + b*10**6)
        elif "m" in s and "k" in s:
            i = s.find("m")
            j = s.find("k")
            a = int(s[:i])
            b = int(s[i+1:j])
            ans = 8*(a*10**6 + b*10**3)
        print(ans)
    except EOFError:
        break

ZeroJudge 解題筆記：b923. stack 堆疊的模板題

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


ZeroJudge 題目連結：b923. stack 堆疊的模板題

解題想法

單純的 stack 操作，在 Python 解題可以直接用 list 模擬 stack，在 C++ 建議引入 stack 或 deque 函式庫。

Python 程式碼

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

st = []
n = int(input())
for _ in range(n):
    line = input().split()
    if line[0] == '1':
        if st: st.pop()
    elif line[0] == '2':
        if st: print(st[-1])
    elif line[0] == '3':
        st.append(int(line[1]))

C++ 程式碼

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

#include <cstdio>
#include <stack>
using namespace std;

int main() {
    stack<int> st;
    int n, op, x;
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", &op);
        if (op == 1) {
            if (!st.empty()) st.pop();
        } else if (op == 2) {
            if (!st.empty()) printf("%d\n", st.top());
        } else if (op == 3) {
            scanf("%d", &x);
            st.push(x);
        }
    }
    return 0;
}

ZeroJudge 解題筆記：d854. NOIP2001 1.一元三次方程求解

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


ZeroJudge 題目連結：d854. NOIP2001 1.一元三次方程求解

解題想法

先檢查高次項的係數 $a$，如果 $a<0$ 則將所有的係數都乘以 $-1$，確保圖形為最右側朝上。下圖是以範例測資的數據繪製，$f(x) = x^3 - 5 x^2 - 4 x + 20$，可以由兩個極值 $x_1, x_2$ 將曲線分為 $3$ 個區域，左側遞增、中間遞減、右側遞增。接下來分別對 $3$ 個區域求根。 左側的根範圍為 $[-100, x_1]$，對答案二分搜 $100$ 次，將中間值 $mid = (high + low) / 2$ 代入 $f(x) = a x^3 + b x^2 + c x + d$，如果 $f(mid) < 0$ 代表 $mid$ 在根的左側，提高下限 $low = mid$，反之則降低上限 $high = mid$。 中間的根範圍為 $[x_1, x_2]$，對答案二分搜 $100$ 次，將中間值 $mid = (high + low) / 2$ 代入 $f(x) = a x^3 + b x^2 + c x + d$，如果 $f(mid) < 0$ 代表 $mid$ 在根的右側，提高下限 $low = mid$，反之則降低上限 $high = mid$。 右側的根範圍為 $[x_2, 100]$，對答案二分搜 $100$ 次，將中間值 $mid = (high + low) / 2$ 代入 $f(x) = a x^3 + b x^2 + c x + d$，如果 $f(mid) < 0$ 代表 $mid$ 在根的左側，提高下限 $low = mid$，反之則降低上限 $high = mid$。

Python 程式碼

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

def f(a, b, c, d, x):
    return a*x*x*x + b*x*x + c*x + d

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        # 係數，浮點數格式
        a, b, c ,d = map(float, data[ptr:ptr+4])
        ptr += 4
        # 將高次項係數調整成正的
        if a < 0:
            a, b, c, d = -a, -b, -c, -d
        # 找 dx 的根，dx = 3*a x**2 + 2*b x + c
        D = 4*b*b - 12*a*c
        x1 = (-2*b - D**0.5) / (6*a)
        x2 = (-2*b + D**0.5) / (6*a)
        # 區間 [-100, x1] 的根 r1，線段左下、右上
        low, high = -100, x1
        for _ in range(100):
            mid = (low + high) / 2
            y = f(a, b, c, d, mid)
            if y < 0:  # mid 在根的左側
                low = mid
            else:  # mid 在根的右側
                high = mid
        r1 = mid
        # 區間 [x1, x2] 的根 r2，線段左上、右下
        low, high = x1, x2
        for _ in range(100):
            mid = (low + high) / 2
            y = f(a, b, c, d, mid)
            if y > 0:  # mid 在根的右側
                low = mid
            else:  # mid 在根的左側
                high = mid
        r2 = mid
        # 區間 [x2, -100] 的根 r3，線段左下、右上
        low, high = x2, 100
        for _ in range(100):
            mid = (low + high) / 2
            y = f(a, b, c, d, mid)
            if y < 0:  # mid 在根的左側
                low = mid
            else:  # mid 在根的右側
                high = mid
        r3 = mid
        result.append(f"{r1:.2f} {r2:.2f} {r3:.2f}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()