一個地球人在臺北

2026年5月13日星期三

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

2026年5月12日星期二

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

2026年5月11日星期一

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

2026年5月10日星期日

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)  # 沒有分割

2026年5月9日星期六

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

2026年5月8日星期五

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;
}

2026年5月7日星期四

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

2026年5月6日星期三

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

2026年5月5日星期二

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

2026年5月4日星期一

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

訂閱：文章 (Atom)

熱門文章

2026年5月13日 星期三

解題想法

Python 程式碼

2026年5月12日 星期二

解題想法

Python 程式碼

2026年5月11日 星期一

解題想法

Python 程式碼

2026年5月10日 星期日

解題想法

Python 程式碼

2026年5月9日 星期六

解題想法

Python 程式碼

2026年5月8日 星期五

解題想法

Python 程式碼

C++ 程式碼

2026年5月7日 星期四

解題想法

Python 程式碼

2026年5月6日 星期三

解題想法

Python 程式碼

2026年5月5日 星期二

解題想法

Python 程式碼

2026年5月4日 星期一

解題想法

Python 程式碼

2026年5月13日星期三

2026年5月12日星期二

2026年5月11日星期一

2026年5月10日星期日

2026年5月9日星期六

2026年5月8日星期五

2026年5月7日星期四

2026年5月6日星期三

2026年5月5日星期二

2026年5月4日星期一