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

ZeroJudge 解題筆記：b537. 分數運算-1

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


ZeroJudge 題目連結：b537. 分數運算-1

解題想法

規則1，$f(1) = 1$，此時 $a = 1, b = 1$。 規則2，若 $k$ 為偶數，則 $$ f(k) = 1 + f(k/2) = \frac{a}{b} > 1 ~\Rightarrow~ f(k/2) = \frac{a - b}{b}, ~ a > b $$ 規則3，若 $k$ 為奇數，則 $$ f(k) = \frac{1}{f(k-1)} = \frac{a}{b} < 1 ~\Rightarrow~ f(k-1) = \frac{b}{a}, ~ a < b $$ 根據以上的3條規則寫自訂函式 find_k，呼叫時代入 a, b。由規則1寫遞迴出口，當 $a == b$ 時回傳 $1$。接下來依照 $a, b$ 的大小決定遞迴的方式，若 $a > b$，依照規則2，回傳 2*find_k(a-b, b)；若 $a < b$，依照規則3，回傳 find_k(b, a) + 1。

Python 程式碼

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

def find_k(a, b):
    if a == b:
        return 1
    if a > b:
        return 2 * find_k(a-b, b)
    else:
        return find_k(b, a) + 1

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        x = int(data[ptr])
        y = int(data[ptr+1])
        ptr += 2
        result.append(f"{find_k(x, y):d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

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

def find_k(a, b):
    if a == b:
        return 1
    if a > b:
        return 2 * find_k(a-b, b)
    else:
        return find_k(b, a) + 1

def solve():
    import sys
    
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        x = int(data[ptr])
        y = int(data[ptr+1])
        ptr += 2
        print(find_k(x, y))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：a271. 彩色蘿蔔

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


ZeroJudge 題目連結：a271. 彩色蘿蔔

解題想法

首先要排除特例，也就是進食資料是空行的狀況，直接輸出原體重就好。接下來依序讀取每天的進食資料，要先結算中毒造成的效果，由於題目有說毒素會累積，假設目前累積的毒素為 $p$，則每天會使體重減少 $n \times p$，再檢查此時體重 $m$ 是否已經歸零，如果歸零則印出 bye~Rabbit 並中止迴圈。接下來結算進食的效果，依照蘿蔔的種類更新體重，如果吃到黃、黑蘿蔔會減少體重，要再檢查體重 $m$ 是否已經歸零，如果歸零則印出 bye~Rabbit 並中止迴圈。更新完每天的體重之後，如果 $m$ 還沒有歸零，則印出 $m$。

Python 程式碼

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

T = int(input())
for _ in range(T):
    # 前 4 項為紅、白、黃、黑蘿蔔對應的體重變化
    # n 為中毒狀態每天減少的體重，m 為體重初始值
    x, y, z, w, n, m = map(int, input().split())
    line = input()  # 每天吃的蘿蔔
    if not line:  # 特例，沒有吃蘿蔔，直接輸出原體重
        print(f"{m:d}g")
        continue
    
    p = 0  # 累積的毒素
    for v in map(int, line.split()):  # 每天吃的蘿蔔種類
        # 要先結算中毒造成的效果
        if p > 0:
            m -= n*p
            if m <= 0:
                print("bye~Rabbit")
                break
        # 再結算進食的效果
        if v == 0:  # 沒吃
            pass
        elif v == 1:  # 紅色
            m += x
        elif v == 2:  # 白色
            m += y
        elif v == 3:  # 黃色
            m -= z
            if m <= 0:
                print("bye~Rabbit")
                break
        elif v == 4:  # 黑色
            m -= w
            p += 1  # 毒素加 1
            if m <= 0:
                print("bye~Rabbit")
                break
    # 如果 m 沒有歸零，輸出 m 的值
    if m > 0:
        print(f"{m:d}g")

ZeroJudge 解題筆記：d221. 10954 - Add All

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


ZeroJudge 題目連結：d221. 10954 - Add All

解題想法

用最小優先佇列 pq 儲存數字，每次取出其中最小的兩個數字 a、b，a、b 相加為 c，更新成本 cost 之後再將 c 存回 pq，直到 pq 之中只剩下一個數字為止。如果用 C++ 解題要用 long long 儲存答案，用 int 會溢位。

Python 程式碼

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

def solve():
    import sys, heapq

    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if n == 0: break
        pq = []
        for _ in range(n):
            x = int(data[ptr])
            ptr += 1
            heapq.heappush(pq, x)
        
        cost = 0
        while len(pq) >= 2:
            a = heapq.heappop(pq)
            b = heapq.heappop(pq)
            c = a + b
            cost += c
            heapq.heappush(pq, c)
        result.append(f"{cost:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d219. 00374 - Big Mod

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


ZeroJudge 題目連結：d219. 00374 - Big Mod

解題想法

這題的題目敘述有問題，實際上要求的是 $$ R = B^P \pmod M $$ 這題的範例測資是 b、p、m 分成 3 行，但實際的測資是 3 個數在同一行並用空格分隔，用 Python 解題的話建議用 data = sys.stdin.read().split() 一次讀取所有測資並分割，再用索引值從 data 讀取資料會比較方便。 這題想要考快速冪，並在計算次方時取模。由於 Python 的 pow 內建這樣的功能，可以直接使用，語法為

pow(底數, 次方, 模數)

如果用 C++ 解題的話要自己寫。

Python 程式碼

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

def solve():
    import sys

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

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d217. 00489 - Hangman Judge

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


ZeroJudge 題目連結：d217. 00489 - Hangman Judge

解題想法

用字典 $state$ 記錄答案中每個字元是否被猜中，為了在檢查時比較好寫，我將還沒有被猜中的字元狀態標記成 True。再用另一個字典 $used$ 記錄已經猜過的字元。接下來依序讀取猜測字串的每個字元，檢查這個字元是否是答案、是否已經猜過，計算猜對的字元數量及猜錯的次數。最後依照猜對的字元數量及猜錯的次數輸出對應的答案。

Python 程式碼

使用時間約為 16 ms，記憶體約為 8.6 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 == -1: break  # 中止迴圈
        result.append(f"Round {n:d}\n")
        ans = data[ptr]  # 答案
        ptr += 1
        state = {c: True for c in ans}  # 答案中各字母狀態，True 為還沒有猜中
        guess = data[ptr]  # 猜測的字串
        ptr += 1
        m, cnt, fails = len(state), 0, 0  # 答案共有 m 個相異字母，猜中 cnt 個，猜錯 fails 次
        used = dict()  # 已經猜過的字母
        """ 檢查是否過關 """
        for c in guess:  # 依序由 guess 讀取字母 c
            if c not in state:  # 如果 c 不在 state 之中
                if c not in used:  # 如果 c 不在 used 之中
                    fails += 1  # 新的猜錯字母，fails 加 1
                    if fails == 7:  break  # 猜錯 7 次，失敗，中止迴圈
            elif state[c]:  # 如果 c 在 state 之中而且 c 還沒有被猜中
                state[c] = False  # 設定為 False
                cnt += 1  # 猜中數量加 1
                if cnt == m: break  # 全部猜中，過關，中止迴圈
            used[c] = True  # c 加入 used
        """ 判斷答案 """
        if fails == 7:  # 失敗
            result.append("You lose.\n")
        else:
            if cnt == m:  # 過關
                result.append("You win.\n")
            else:  # 中離
                result.append("You chickened out.\n")
    """ 輸出答案 """
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d194. 11572 - Unique Snowflakes

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


ZeroJudge 題目連結：d194. 11572 - Unique Snowflakes、d716. Unique Snowflakes(強化版)

解題想法

用滑動視窗解題，用字典 $last$ 記錄每一個編號的雪花上次出現的索引值，視窗左端點為 $left$。接下來依序讀取目前的雪花編號為 $snow$、視窗右端點為 $right$，如果 $last$ 之中有 $snow$ 而且上一次出現的索引值大於等於 $left$，要更新視窗範圍，將 $left$ 改成 $last[snow] + 1$，再將 $last[snow]$ 更新為 $right$；最後更新最大值 $imax$，取 $imax$ 及 $right - left + 1$ 較大者。

Python 程式碼

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

t = int(input())  # t 筆測資
for _ in range(t):  # 執行 t 次
    n = int(input())  # n 片雪花
    snowflake = [int(input()) for _ in range(n)]  # 讀取雪花編號
    last = dict()  # 每一個編號的雪花上次出現的索引值
    imax = 0  # 不同編號雪花數量最大值
    left = 0  # 滑動視窗左端點
    for right, snow in enumerate(snowflake):  # 依序讀取雪花編號
        if snow in last and last[snow] >= left:  # 如果 snow 在 last 之中，而且索引值大於等於左端點
            left = last[snow] + 1  # 更新左端點為目前雪花編號前一次出現的索引值加 1
        last[snow] = right  # 更新目前雪花編號出現的索引值為 right
        imax = max(imax, right - left + 1)  # 更新最大值
    print(imax)

使用時間約為 55 ms，記憶體約為 37.7 MB，通過測試。如果更新 $imax$ 時不呼叫 $max$，速度會更快，使用時間約為 45 ms，記憶體約為 34.9 MB，通過測試。

def solve():
    import sys

    result = []
    data = sys.stdin.read().split()
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])  # n 片雪花
        ptr += 1
        last = dict()  # 每一個編號的雪花上次出現的索引值
        imax = 0  # 不同編號雪花數量最大值
        left = 0  # 滑動視窗左端點
        for right in range(n):  # 依序讀取雪花編號
            snow = data[ptr]
            ptr += 1
            if snow in last and last[snow] >= left:  # 如果 snow 在 last 之中，而且索引值大於等於左端點
                left = last[snow] + 1  # 更新左端點為目前雪花編號前一次出現的索引值加 1
            last[snow] = right  # 更新目前雪花編號出現的索引值為 right
            val = right - left + 1  # 更新最大值
            if val > imax: imax = val
            #imax = max(imax, right - left + 1)  
        result.append(f"{imax:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

ZeroJudge 解題筆記：d192. 11351 - Last Man Standing

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


ZeroJudge 題目連結：d192. 11351 - Last Man Standing

解題想法

輸入的測資範圍應該是 $0 < n \leq 10^5$ 及 $0 < k < 10^9$，如果模擬整個淘汰的過程會超時。 從最後的贏家逆推𠩤來的編號。

1. 為了方便運算，成員的編號由0開始，最後輸出結果時再加1。
2. 先假設幸運者的編號 $idx_{0} = 0$，最後剩下 1 個人。
3. 第 $n-1$ 次（最後1次）運作時，參與的人數為 $2$，幸運者原來的編號為 $idx_{n-2} = k \% 2$。
4. 第 $n-2$ 次（倒數第2次）運作時，參與的人數為 $3$，幸運者原來的編號為 $idx_{n-3} = (idx_{n-2} + k) \% 3$。
5. 第 $n-3$ 次（倒數第3次）運作時，參與的人數為 $4$，幸運者原來的編號為 $idx_{n-4} = (idx_{n-3} + k) \% 4$。
6. 若 $i = 1、2、\dots、n$，則第 $n-i$ 次（倒數第 $i$ 次）運作時，參與的人數為 $1 + i$，幸運者原來的編號為 $idx_{i} = (idx_{i-1} + k) \% (1+ i)$。
7. 輸出幸運者的編號，由於題目的編號從 $1$ 開始，需要將 $idx$ 加 $1$。

Python 程式碼

模擬過程，超時。

t = int(input())
for i in range(1, t+1):
    n, k = map(int, input().split())
    arr = list(range(1, n+1))  # 目前還存活的人
    idx = 0  # 從 1 號、索引值 0 開始
    while n > 1:  # 人數大於 1 繼續執行
        idx = (idx+k-1) % n  # 更新淘汰者的索引值
        del arr[idx]  # 移除 arr[idx]
        n -= 1  # 人數減 1
        idx %= n  # 更新 idx，有可能歸零
    print(f"Case {i:d}: {arr[0]:d}")  # 印出答案

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

t = int(input())
for i in range(1, t+1):
    n, k = map(int, input().split())
    idx = 0  # 最後剩下的人，索引值 0
    for j in range(1, n):  # 1 到 n-1
        idx = (idx + k) % (1+j)
    print(f"Case {i:d}: {idx+1:d}")  # 印出答案

ZeroJudge 解題筆記：d191. 11352 - Crazy King

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


ZeroJudge 題目連結：d191. 11352 - Crazy King

解題想法

因為我不想要在檢查騎士可以走到的位置時，需要先檢查這一步是不會出界，我會在地圖的周圍加上兩層 $-1$ 當作哨兵，用 $-1$ 標示邊界及不能走到的格子，假設地圖尺寸原為 $m \times n$，如果用 Python 解題會改成尺寸為 $(m+2) \times (n+2)$ 的二維串列，如果用 C++ 解題會改成尺寸為 $(m+4) \times (n+4)$ 的二維陣列。地圖 $grid$ 之中實際上儲存的是步數，用 $0$ 代表起點，$-2$ 代表終點，$-3$ 代表空格及未走過的格子，$-1$ 代表邊界及不能走的格子。讀取地圖資料，依照字元標示 $grid$ 的數字，再檢查騎士的位置，將騎士可以一步走到的格子也標示成 $-1$。最後再用 BFS，找出國王從 $A$ 點走到 $B$ 點的最少步數。BFS 結束之後，如果終點對應的格子仍為 $-2$，代表無法走到終點。

Python 程式碼

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

from collections import deque

t = int(input())
for _ in range(t):
    """ 讀取地圖資料 """
    m, n = map(int, input().split())  # 棋盤 m*n，實際上儲存的是步數
    grid = [[-1]*(n+2) for _ in range(m+2)]  # 最右側、最下方加上兩層 -1 當作哨兵
    knight = []  # 騎士的位置
    sr, sc, er, ec = 0, 0, 0, 0  # 起點、終點
    for r in range(m):  # 讀取 m 行資料
        line = input()
        for c, ch in enumerate(line):  # 依序讀取 line 的字元
            if ch == 'Z': knight.append((r, c))  # 騎士
            elif ch == 'A':  # 起點
                grid[r][c] = 0; sr = r; sc = c;
            elif ch == 'B':  # 終點
                grid[r][c] = -2; er = r; ec = c;
            elif ch == '.':  # 空格
                grid[r][c] = -3
    for r, c in knight:  # 依序讀取騎士所在的位置
        # 依序檢查右上、右、右下、下、左下、左、左上、上
        for dr, dc in ((-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)):
            nr, nc = r+dr, c+dc  # 檢查 (nr, nc)
            if grid[nr][nc] == -3:  # 空格
                grid[nr][nc] = -1  # 設定成 -1，不能走
    """ BFS 找最短路徑 """
    que = deque([(sr, sc)])  # 待走訪佇列
    end = False
    while que and not end:  # 如果 que 還有資料而且還沒有走到終點，繼續執行
        r, c = que.popleft()  # 取出 que 最前面的資料
        # 依序檢查右上、右、右下、下、左下、左、左上、上
        for dr, dc in ((-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0)):
            nr, nc = r+dr, c+dc  # 檢查 (nr, nc)
            if grid[nr][nc] == -3:  # 走到空格
                grid[nr][nc] = grid[r][c] + 1  # 更新步數
                que.append((nr, nc))  # (nr, nc) 加到 que
            elif grid[nr][nc] == -2:  # 走到終點
                grid[nr][nc] = grid[r][c] + 1  # 更新步數
                end = True; break  # 走到終點，中止迴圈
    """ 印出答案 """
    if grid[er][ec] == -2:  # 無法走到終點
        print("King Peter, you can't go now!")
    else:  # 走到終點
        print(f"Minimal possible length of a trip is {grid[er][ec]:d}")