Processing math: 100%

熱門文章

2025年7月27日 星期日

ZeroJudge 解題筆記:b558. 求數列第 n 項

作者:王一哲
日期:2025年7月27日


ZeroJudge 題目連結:b558. 求數列第 n 項

解題想法


這題的測資不大,而且遞迴關係也很簡單,可以先用遞迴建表,把 1n500 對應的函數值都算出來,再逐行讀取測資、查表、輸出答案。也可以找一般式,先列出前幾項找規律 f(1)=1f(2)=f(1)+1f(3)=f(2)+2f(4)=f(3)+3f(n)=f(n1)+(n1) 以上的式子相加之後可得 f(n)=1+[1+2+3++(n1)]=1+n(n1)2

Python 程式碼


建表,使用時間約為 19 ms,記憶體約為 3.4 MB,通過測試。
import sys

table = [0]*501
table[1] = 1
for i in range(2, 501): table[i] = table[i-1] + i - 1

for line in sys.stdin:
    print(table[int(line)])

建表,使用時間約為 20 ms,記憶體約為 3.3 MB,通過測試。
table = [0]*501
table[1] = 1
for i in range(2, 501): table[i] = table[i-1] + i - 1
while True:
    try:
        print(table[int(input())])
    except:
        break

2025年7月26日 星期六

ZeroJudge 解題筆記:b557. 直角三角形

作者:王一哲
日期:2025年7月26日


ZeroJudge 題目連結:b557. 直角三角形

解題想法


比較直接的作法是用三層迴圈掃過所有的邊長,找出可以組成直角三角形的邊長組合,這個作法在 C++ 很快,在 Python 會超時。另一種作法是先計算所有的邊長平方各有幾個,再由小到大取出邊長平方,如果兩者相加的值有在邊長平方的計數器之中,再用計數器中的數量相乘、計算直角三角形的數量。

Python 程式碼


使用 dict,使用時間約為 76 ms,記憶體約為 3.3 MB,通過測試。
t = int(input())  # t 組測資
for _ in range(t):
    n = int(input())  # n 個邊長
    edges = sorted(list(map(int, input().split())))
    cnt = dict()  # 邊長平方的計數器
    cand = []  # 邊長平方
    for edge in edges:  # 計算各種邊長平方的數量
        x = edge * edge
        if x not in cnt:
            cnt[x] = 1
            cand.append(x)
        else:
            cnt[x] += 1
    m = len(cnt)  # 邊長平方的數量
    ans = 0  # 答案
    for i in range(m-1):  # 依序讀取由小到大的邊長平方
        for j in range(i+1, m):
            a, b = cand[i], cand[j]  # 邊長平方 a, b
            if a+b in cnt:  # 如果 cnt 之中有 a+b 才會更新 ans
                ans += cnt[a+b]* cnt[a] * cnt[b]
    print(ans)

2025年7月25日 星期五

ZeroJudge 解題筆記:b538. 分數運算-2

作者:王一哲
日期:2025年7月25日


ZeroJudge 題目連結:b538. 分數運算-2

解題想法


這題比b537. 分數運算-1簡單很多,只要按照分數運算的規則,分別寫出加、減、乘、除的計算方式,再用 gcd 將分子、分母約分。輸出時分別三種:0、整除、分數,如果分母是負的,負號要加在分子的前面。

Python 程式碼


使用時間約為 19 ms,記憶體約為 3.4 MB,通過測試。
import sys, math

def fac_cal(a, b, c, d, op):
    num, den = 1, 1  # 計算結果的分子、分母
    if op == "+":  # a/b + c/d = (a*d + c*b) / (b*d)
        num = a*d + c*b 
        den = b*d
    elif op == "-":  # a/b - c/d = (a*d - c*b) / (b*d)
        num = a*d - c*b
        den = b*d
    elif op == "*":  # a/b * c/d = (a*c) / (b*d)
        num = a*c
        den = b*d
    else:  # a/b / c/d = a/b * d/c = (a*d) / (b*c)
        num = a*d
        den = b*c
    if den < 0:  # 如果分母小於 0,將分子、分母的正負號都反過來
       num = -num; den = -den
    g = math.gcd(num, den)  # 取分子、分母最大公因數約分
    num //= g; den //= g
    if num == 0: return "0\n"  # 分子為 0,回傳 0
    elif num%den == 0: return f"{num:d}\n"  # 可以整除,回傳分子
    else: return f"{num:d}/{den:d}\n"  # 不能整除

result = []
lines = sys.stdin.readlines()
for line in lines:
    arr = line.split()
    a, b, c, d = map(int, arr[:4])  # 分割出前 4 個數字
    op = arr[-1]  # 運算符號
    result.append(fac_cal(a, b, c, d, op))
sys.stdout.write("".join(result))

2025年7月24日 星期四

ZeroJudge 解題筆記:b512. 高維度稀疏向量

作者:王一哲
日期:2025年7月24日


ZeroJudge 題目連結:b512. 高維度稀疏向量

解題想法


這題的維度不連續而且範圍很大,用字典儲存維度及對應的值比較方便,如果用陣列儲存值會有很多浪費掉、沒有儲存資料的空間。

Python 程式碼


先儲存兩個向量的資料,再計算相乘的結果。使用時間約為 43 ms,記憶體約為 6.1 MB,通過測試。
A, B = dict(), dict()
for sub in input().split():  # 不需要略過 0:0,不影響答案
    k, v = map(int, sub.split(":"))
    A[k] = v
for sub in input().split():  # 不需要略過 0:0,不影響答案
    k, v = map(int, sub.split(":"))
    B[k] = v
ans = 0
for k, v in A.items():
    ans += v * B.get(k, 0)
    if a in B: ans += n*B[a]  # 也可以這樣寫
print(ans)

只儲存第一個向量的資料,讀取第二個向量資料同時計算相乘的結果。使用時間約為 45 ms,記憶體約為 4.5 MB,通過測試。
A, B = dict(), dict()
for sub in input().split():  # 不需要略過 0:0,不影響答案
    k, v = map(int, sub.split(":"))
    A[k] = v
ans = 0
for sub in input().split():  # 不需要略過 0:0,不影響答案
    k, v = map(int, sub.split(":"))
    ans += v*A.get(k, 0)
print(ans)


2025年7月23日 星期三

ZeroJudge 解題筆記:b511. 換銅板

作者:王一哲
日期:2025年7月23日


ZeroJudge 題目連結:b511. 換銅板

解題想法


這題我用函式遞迴窮舉所有面額硬幣、數量、總金額的組合,如果遇到總金額符合題目要求的組合就輸出答案。

Python 程式碼


使用時間約為 19 ms,記憶體約為 3.3 MB,通過測試。
def solve():
    import sys
    n = int(sys.stdin.readline())  # n 種面額
    coins = sorted(list(map(int, sys.stdin.readline().split())))  # 硬幣面額,由小到大排序
    target = int(sys.stdin.readline())  # 目標
    ### 主要的解題過程 ###
    def backtrack(curr, nums, total):
        if total == target:  # 遞迴出口,符合目標
            s = "(" + ",".join(map(str, nums)) + ")"  # 要輸出的字串
            sys.stdout.write(f"{s}\n")
            return
        if curr == n or total > target:  # 遞迴出口,已經到最後一種面額或超過目標
            return
        maxn = (target-total) // coins[curr]  # 這個面額可用的最大數量
        for i in range(maxn+1):  # 依序測試 0 ~ maxn 個
            nums[curr] = i  # 設定這個面額的數量
            backtrack(curr+1, nums, total + coins[curr]*i)  # 遞迴
    ### End of backtrack ###
    backtrack(0, [0]*n, 0)  # 從索引值 0、個數 0、加總 0 開始測試
### End of solve ###

if __name__ == "__main__":
    solve()

2025年7月22日 星期二

ZeroJudge 解題筆記:b373. [福州19中]车厢重组

作者:王一哲
日期:2025年7月22日


ZeroJudge 題目連結:b373. [福州19中]车厢重组

解題想法


這題實際上就是考氣泡排序法的交互次數。據說第二筆測資車廂編號的資料有問題,可能被空行分隔,不是只有一行,用 Python 解題時,需要加上一些濾掉空行的工具。

Python 程式碼


使用時間約為 0.2 s,記憶體約為 3.3 MB,通過測試。
import sys

n = int(sys.stdin.readline())  # n 節車廂
arr = []  # 車廂編號
for line in sys.stdin:  # 讀取多行測資
    if not line.strip(): continue  # 如果是空行,讀下一行
    arr += list(map(int, line.split()))  # 如果不是空行,轉成串列接到 arr
### 氣泡排序法,找交換次數 ###
cnt = 0
for i in range(n-1):
    for j in range(i+1, n):
        if arr[i] > arr[j]:
            arr[i], arr[j] = arr[j], arr[i]
            cnt += 1
sys.stdout.write(f"{cnt:d}\n")


2025年7月21日 星期一

ZeroJudge 解題筆記:b367. 翻轉世界

作者:王一哲
日期:2025年7月21日


ZeroJudge 題目連結:b367. 翻轉世界

解題想法


可以用二維串列儲存圖的內容,再從上下兩端逐行檢查,下方的列前後順序對調之後內容是否與上方的列相同;如果共有奇數列,還要再單獨檢查中間的列。也可以將圖的內容接成很長的一維串列,只要從兩端往中間依序檢查數字是否相同,寫起來比較簡單。

Python 程式碼


用二維串列儲存圖的內容,使用時間約為 18 ms,記憶體約為 3.3 MB,通過測試。
def check(grid):  # 輸入圖,判斷是否轉 180 度之後對稱
    n, m = len(grid), len(grid[0])  # 圖的尺寸
    for i in range(n//2):  # 從上下兩端往中間檢查
        if grid[i] != grid[n-i-1][::-1]:  # 如果將底下的列翻轉之後不相等
            return False  # 回傳 False
    if n%2 == 1:  # 如果為奇數列,再檢查中間的列
        if grid[n//2] != grid[n//2][::-1]:
            return False
    return True  # 最後回傳 True

t = int(input())  # t 張圖
for _ in range(t):  # 執行 t 次
    n, m = map(int, input().split())  # 圖的尺寸 n*m
    grid = [list(map(int, input().split())) for _ in range(n)]  # 讀取圖
    print("go forward" if check(grid) else "keep defending")

2025年7月20日 星期日

ZeroJudge 解題筆記:b265. Q11286 - Conformity

作者:王一哲
日期:2025年7月20日


ZeroJudge 題目連結:b265. Q11286 - Conformity

解題想法


這個題目的中文敘述很奇怪。題目的意思應該是要統計各種課程組合的選課人數,例如
3
100 101 102 103 488
100 200 300 101 102
103 102 101 488 100
第 2、4 列是一樣的課程組合,因此答案為 2。另一筆範例測資
3
200 202 204 206 208
123 234 345 456 321
100 200 300 400 444
因為 2、3、4 列是不一樣的課程組合,各有 1 個人選擇這個組合,題目是將所有最多選課人數的課程組合都加起來,所以答案為 3。

Python 程式碼


使用時間約為 0.5 s,記憶體約為 10.1 MB,通過測試。
import sys
from collections import defaultdict

result = []
for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    cnt = defaultdict(int)
    for _ in range(n):
        course = tuple(sorted(list(map(int, sys.stdin.readline().split()))))
        cnt[course] += 1
    ans = imax = 0
    for v in cnt.values():
        if v > imax:
            ans = v; imax = v
        elif v == imax:
            ans += v
    result.append(f"{ans:d}\n")
sys.stdout.write("".join(result))


2025年7月19日 星期六

ZeroJudge 解題筆記:a982. 迷宮問題#1

作者:王一哲
日期:2025年7月19日


ZeroJudge 題目連結:a982. 迷宮問題#1

解題想法


這題我用 BFS 解題。可以用兩個二維串列分別儲存地圖及步數,也可以用一個二維串列儲存步數,-1 代表邊界。

Python 程式碼


用兩個二維串列,分別儲存地圖及步數。使用時間約為 33 ms,記憶體約為 3.9 MB,通過測試。
from collections import deque

n = int(input())  # 地圖 n*n
grid = [list(input()) for _ in range(n)]  # 地圖資料
steps = [[0]*n for _ in range(n)]  # 步數資料
steps[1][1] = 1  # 起點為 (1, 1),步數 1
que = deque([(1, 1)])  # 待走訪佇列,先放入 (1, 1)
while que:  # BFS
    r, c = que.popleft()  # 目前的座標 (r, c)
    for dr, dc in ((0, 1), (-1, 0), (0, -1), (1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要測試的點 (nr, nc)
        if grid[nr][nc] == '#' or steps[nr][nc] != 0:  # 如果是邊界或已走過
            continue  # 找下一個點
        steps[nr][nc] = steps[r][c] + 1  # 更新 (nr, nc) 的步數
        que.append((nr, nc))  # (nr, nc) 加到 que
### End of BFS ###
# 如果 (n-2, n-2) 此格不是 0,有解;反之無解
print(steps[n-2][n-2] if steps[n-2][n-2] != 0 else "No solution!")

2025年7月18日 星期五

ZeroJudge 解題筆記:a981. 求和問題

作者:王一哲
日期:2025年7月18日


ZeroJudge 題目連結:a981. 求和問題

解題想法


這題要用遞迴窮舉所有的組合,輸出其中符合條件的組合,並且要適當地剪枝,節省運算時間。不過我在 Python 一直沒有寫出能夠過關的程式碼,最後一筆測資超時。

Python 程式碼


最後一筆測資超時。
def solve():
    import sys
    lines = sys.stdin.readlines()
    head = 0
    while head < len(lines):
        n, m = map(int, lines[head].split())  # 讀取數量 n,要找的加總 m
        nums = sorted(list(map(int, lines[head+1].split())))  # 讀取候選的數值
        head += 2  # 從 lines 讀取資料的索引值
        choice = [False]*n  # 是否選這個數字
        have_ans = False  # 是否有解
        ### 主要的解題過程,輸入目前檢測的 nums 索引值,加總 ###
        def backtrack(curr, total):
            nonlocal have_ans  # 這樣才能改變外層 have_ans 的值
            if total == m:  # 有解,印出選擇的數字,結束遞迴
                have_ans = True
                solution = " ".join([str(num) for i, num in enumerate(nums) if choice[i]])
                sys.stdout.write(f"{solution}\n")
                return
            if curr == n or total > m: return # 已出界或是目標為負值,結束遞迴
            choice[curr] = True  # 選此項
            backtrack(curr + 1, total + nums[curr])  # 遞迴,索引值加 1,total 加上此項的值
            choice[curr] = False  # 回溯,不選此項
            backtrack(curr + 1, total)  # 遞迴,索引值加 1,total 不變
        ### End of backtrack ###
        backtrack(0, 0)  # 從索引值 0、加總 0 開始
        if not have_ans: sys.stdout.write("-1\n")  # 如果無解,印出 -1
        
if __name__ == "__main__":
    solve()