ZeroJudge 解題筆記：a130. 12015 - Google is Feeling Lucky

作者：王一哲
日期：2025年12月17日


ZeroJudge 題目連結：a130. 12015 - Google is Feeling Lucky

解題想法

這題考排序，網站相關度高排前面，如果相關度相同，先讀到的放前面。如果用 Python 解題，可以將網站相關度 val、讀取資料的索引值 idx、網址 url 組成 tuple 再存入串列，排序時用 lambda function 寫比較式 (-x[0], x[1])。如果用 C++ 解題，可以自訂結構體儲存網站相關度 val、讀取資料的索引值 idx、網址 url，資料存入 vector，排序時用 lambda function 寫比較式。

Python 程式碼

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

T = int(input())
for t in range(1, T+1):
    print(f"Case #{t:d}:")
    data = []
    for i in range(10):
        url, v = input().split()
        data.append((int(v), i, url))
    # 排序，相關度高排前面，如果相關度相同，先讀到的放前面
    data.sort(key = lambda x : (-x[0], x[1]))
    vmax = data[0][0]
    for d in data:
        if d[0] < vmax: break
        print(d[2])

ZeroJudge 解題筆記：a111. 12149 - Feynman

作者：王一哲
日期：2025年12月16日


ZeroJudge 題目連結：a111. 12149 - Feynman

解題想法

如果 $n = 1$ 答案為 $1$；如果 $n = 2$，答案為 $1 + 4 = 1 + 2^2 = 5$；如果 $n = 3$，答案有邊長 3 的正方形 1 個，邊長 2 的正方形 4 個，邊長 1 的正方形 9 個，也就是 $1 + 4 + 9 = 1 + 2^2 + 3^2 = 14$。解題時可以建表或是代公式 $$ ans = \sum_{i = 1}^n i^2 = \frac{n(n+1)(2n+1)}{6} $$

Python 程式碼

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

import sys

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

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(dp[n])

代公式，使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    if n == 0: continue
    print(n*(n+1)*(2*n + 1)//6)

ZeroJudge 解題筆記：a011. 00494 - Kindergarten Counting Game

作者：王一哲
日期：2025年12月15日


ZeroJudge 題目連結：a011. 00494 - Kindergarten Counting Game

解題想法

這題要讀取整行字串之後依序讀取每個字元，用變數 last 記錄目前連續出現的字母數量，如果這個字元是字母則 last 加 1； 反之，前一個單字結束了，如果 last 大於 0，單字數量 cnt 加 1，再將 last 歸零。檢查完整行字串之後，記得要再結算一次，才不會漏掉最後一個單字。

Python 程式碼

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

import sys

for line in sys.stdin:
    last, cnt = 0, 0
    for c in line.strip():
        if c.isalpha(): last += 1
        else:
            if last > 0: cnt += 1
            last = 0
    if last > 0: cnt += 1
    print(cnt)

ZeroJudge 解題筆記：o087. 王子的名字

作者：王一哲
日期：2025年12月14日


ZeroJudge 題目連結：o087. 王子的名字

解題想法

先檢查讀取到的名字是否都是字母，如果有任何一個字元不是字母，分數為 -1；如果所有字元都是字母，按照題目給的規則計分。將分數、索引、名字組成 tuple 或是自訂的 struct ，存入陣列之中，最後按照分數、索引值由小到大排序。

Python 程式碼

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

def Evaluate(Name: str):
    if(type(Name) != str): return -1                              
    Score = 0
    NameLen = len(Name)
    for i in range(NameLen):
        CharCode = ord(Name[i])
        Score += ((CharCode * 1123) % 1002)
        while (CharCode > 0):
            Score += (CharCode % 10)
            CharCode = (CharCode // 10)
    return (Score % 101)

n = int(input())
names = []
for i in range(n):
    name = input()
    score = Evaluate(name)
    names.append((score, i, name))
names.sort()
for score, _, name in names:
    print(f"{name:s} {score:d}")

ZeroJudge 解題筆記：o067. 柯尼斯堡七橋問題

作者：王一哲
日期：2025年12月13日


ZeroJudge 題目連結：o067. 柯尼斯堡七橋問題

解題想法

有奇數條邊的節點數量必須小於等於 2 才有解，可以真的存圖再計算有奇數條邊的節點數量，也可以不存圖、只儲存每個節點是否有奇數條邊。不要真的模擬走訪過程。

Python 程式碼

真的存圖，使用時間約為 0.4 s，記憶體約為 12.7 MB，通過測試。

n, m = map(int, input().split())
graph = dict()
for _ in range(m):
    u, v = map(int, input().split())
    if u not in graph: graph[u] = [v]
    else: graph[u].append(v)
    if v not in graph: graph[v] = [u]
    else: graph[v].append(u)
cnt = 0
flag = True
for v in graph.values():
    if len(v)%2 == 1: cnt += 1
    if cnt > 2:
        flag = False
        break
print("YES" if flag else "NO")

只存每個節點是否有奇數條邊，使用時間約為 0.4 s，記憶體約為 3.4 MB，通過測試。

n, m = map(int, input().split())
vertice = [False]*(n+1)
for _ in range(m):
    u, v = map(int, input().split())
    vertice[u] = not vertice[u]
    vertice[v] = not vertice[v]
cnt = sum(vertice)
print("YES" if cnt <= 2 else "NO")

ZeroJudge 解題筆記：n700. 蝸牛的踩地雷攻略 3 (點方塊)

作者：王一哲
日期：2025年12月12日


ZeroJudge 題目連結：n700. 蝸牛的踩地雷攻略 3 (點方塊)

解題想法

為了不要檢查是否出界，我習慣在地圖的最右側、最下方加上用不到的符號當作哨兵。用自訂函式 count 計算周圍 8 格的地雷數量，再用另一個自訂函式 reveal 翻開格子，reveal 之中是用 BFS 找出所有可以翻開的格子，同時將翻開後的地圖儲存到另一個二維串列之中。

Python 程式碼

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

from collections import deque

def count(grid, r, c):  # 計算周圍 8 格的地雷數量
    cnt = 0  # 地雷數量
    for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
        nr, nc = r+dr, c+dc
        if grid[nr][nc] == '*': cnt += 1
    return cnt

def reveal(grid, result, ri, ci, n, m):  # 翻開格子，代入地圖 grid，結果 result，位置 (ri, ci)，維度 n*m
    visited = [[False]*(m+1) for _ in range(n+1)]  # 是否已走訪
    que = deque([(ri, ci)])  # 待走訪的位置
    visited[ri][ci] = True  # (ri, ci) 已走訪
    while que:  # 如果 que 還有資料繼續執行
        r, c = que.popleft()  # 從 que 開頭讀取並移除資料
        cnt = count(grid, r, c)  # 計算 (r, c) 周圍的地雷數量
        if cnt == 0:  # 如果周圍沒有地雷
            result[r][c] = '_'  # 翻開，是空地
            # 檢查周圍 8 格，如果還沒有出界、沒有走訪、是未翻開的格子
            for dr, dc in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
                nr, nc = r+dr, c+dc
                if grid[nr][nc] != '@' and not visited[nr][nc] and grid[nr][nc] == '#':
                    visited[nr][nc] = True  # (nr, nc) 已走訪
                    que.append((nr, nc))  # (nr, nc) 加入 que
        else: result[r][c] = str(cnt)  # 周圍有地雷，填入地雷的數量

def main():  # 主程式
    n, m, ri, ci = map(int, input().split())  # 地圖維度 n*m，起點 (ri, ci)
    grid = [list(input().strip() + '@') for _ in range(n)]  # 最右側加上 @ 作為哨兵
    grid.append(['@']*(m+1))  # 最下方加 m+1 個 @ 作為哨兵
    result = [['#']*m for _ in range(n)]  # 儲存結果用的 n*m 二維串列
    ri -= 1; ci -= 1  # 配合索引值，ri, ci 減 1
    reveal(grid, result, ri, ci, n, m)  # 呼叫 reveal 求解
    for row in result: print("".join(row))  # 印出答案

if __name__ == '__main__':
    main()

ZeroJudge 解題筆記：n689. pD. 技能點數

作者：王一哲
日期：2025年12月11日


ZeroJudge 題目連結：n689. pD. 技能點數

解題想法

我用接鄰矩陣 graph 儲存有向圖，用串列 need 儲存學習各技能所需的前置技能，用集合 learn 儲存學到的技能。將一開始拿到的技能書 book 存入待走訪佇列 que，用 BFS 找出所有可以學到的技能。

Python 程式碼

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

from collections import deque

n, m, k = map(int, input().split())
book = list(map(int, input().split()))
graph = [[] for _ in range(n)]
need = [set() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    need[v].add(u)
for b in book: need[b].clear()
learn = set(book)
que = deque(book)
while que:
    u = que.popleft()
    for v in graph[u]:
        if u in need[v]:
            need[v].remove(u)
        if not need[v]:
            que.append(v)
            learn.add(v)
print(len(learn))

ZeroJudge 解題筆記：n688. pC. 卡牌遊戲

作者：王一哲
日期：2025年12月10日


ZeroJudge 題目連結：n688. pC. 卡牌遊戲

解題想法

先將卡牌分別正值、負值兩堆，為了將卡牌總和最大化，策略是將負值牌堆中最小的牌，也就是負值、量值最大的牌取出、轉為正值、存入正值牌堆，如果負值牌堆沒有資料了，就反過來將正值牌堆中最小的牌取出、轉為負值、存入負值牌堆。為了達成這個目標，用最小優先佇列儲存牌堆是最方便的。

Python 程式碼

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

import heapq

n, k = map(int, input().split())
positive, negative = [], []
for x in map(int, input().split()):
    if x >= 0: heapq.heappush(positive, x)
    else: heapq.heappush(negative, x)
for _ in range(k):
    if negative:
        heapq.heappush(positive, -heapq.heappop(negative))
    elif positive:
        heapq.heappush(negative, -heapq.heappop(positive))
print(sum(positive) + sum(negative))

ZeroJudge 解題筆記：n083. 數字序號轉換

作者：王一哲
日期：2025年12月9日


ZeroJudge 題目連結：n083. 數字序號轉換

解題想法

假設計算結果儲存在變數 m，m 的初始值為 0。將讀到的字串從索引值 0 開始，每次取長度為 3 的子字串，並用一個布林值記錄這次是否需要將子字串反序。m 加上子字串轉成 int 之後的值，再對 997 取餘數。

Python 程式碼

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

import sys

MOD = 997
result = []
lines = sys.stdin.readlines()
for line in lines:
    line = line.strip()
    n = len(line)
    m = 0
    rev = False
    for i in range(0, n, 3):
        s = line[i:i+3]
        if rev: s = s[::-1]
        rev = not rev
        m = (m + int(s))%MOD
    result.append(str(m) + "\n")
sys.stdout.write("".join(result))

ZeroJudge 解題筆記：b181. 2. 網路設計

作者：王一哲
日期：2025年12月8日


ZeroJudge 題目連結：b181. 2. 網路設計

解題想法

這題用自訂的併查集類別建立物件，依序從成本最低的邊開始測試，如果這條邊加上去之後，能夠使兩個節點所在的區塊連通，就要選用這條邊，記錄節點編號並更新總成本。 題目沒有說清楚的地方有三點：

1. 這題是多筆測資
2. n 只是節點編號的最大值，不見得有 n 個節點。
3. 節點的排序方式，讀取測資儲存邊的成本、節點時要按照測資的順序。輸出節點時要按照節點的編號由小到大排序，轉換成整數再比大小，不用管開頭的 W，兩個節點一組，先比較第一個節點，再比較第二個節點。輸出時如果按照字典序排序會出錯

   WA (line:3)
   您的答案為: (W10 W2) (W2 W3) (W3 W4) (W3 W5) (W3 W6)
   正確答案為: (W2 W3) (W3 W4) (W3 W5) (W3 W6) (W10 W2)
   

   如果按照第一個節點的編號數字排序也會出錯

   WA (line:3)
   您的答案為: (W2 W3) (W3 W5) (W3 W4) (W3 W6) (W10 W2)
   正確答案為: (W2 W3) (W3 W4) (W3 W5) (W3 W6) (W10 W2)
   

Python 程式碼

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

import sys
from functools import cmp_to_key

class DisjointSetUnion:
    def __init__(self, nodes):
        self.parent = {node: node for node in nodes}
        self.rank = {node: 0 for node in nodes}

    def rfind(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.rfind(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_v] > self.rank[root_u]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
            return True
        return False

def mycmp(a, b):
    """ 為了輸出節點定義的比較式 """
    if int(a[0][1:]) == int(b[0][1:]):  # 如果第一個節點的編號相同
        if int(a[1][1:]) < int(b[1][1:]): return -1  # 第二個節點編號小的放前面
        elif int(a[1][1:]) > int(b[1][1:]): return 1
        else: return 0
    if int(a[0][1:]) < int(b[0][1:]): return -1  # 第一個節點編號小的放前面
    else: return 1

""" 處理多筆測資 """
result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    """ 讀取測資 """
    n, m = map(int, lines[idx].split())  # 題目敘率不清，n 是可能的節點編號最大值，m 條邊
    idx += 1
    nodes = set()  # 所有節點，不見得有 n 個節點，要從邊的資料找節點
    edges = []  # 所有的邊
    for _ in range(m):  # 讀取 m 條邊
        line = lines[idx].split()
        idx += 1
        u, v = line[0], line[1]  # 節點 u, v 相連
        w = int(line[2])  # 邊的成本
        edges.append((w, u, v))  # (成本, 節點1, 節點2)，節點要按照測資的順序
        nodes.add(u)
        nodes.add(v)

    """ 用併查集找最低合併成本 """
    dsu = DisjointSetUnion(nodes)  # 建立併查集物件
    edges.sort()  # 依照成本由小到大排序
    cost = 0  # 總成本
    choose = []  # 選取的節點
    for w, u, v in edges:  # 依序讀取邊
        if dsu.union(u, v):  # 如果 u, v 可以合併
            cost += w  # 更新成本
            choose.append((u, v))  # 更新選取的節點
    """ 輸出答案 """
    choose.sort(key = cmp_to_key(mycmp))  # 輸出節點時，要按照節點編號大小排序，比數字
    res = []
    for u, v in choose:
        res.append(f"({u} {v})")
    result.append(" ".join(res) + "\n" + f"{cost:d}\n")
""" 一次輸出所有答案 """
sys.stdout.write("".join(result))