ZeroJudge 解題筆記：a225. 明明愛排列

作者：王一哲
日期：2025年7月4日


ZeroJudge 題目連結：a225. 明明愛排列

解題想法

這題在 Python 可以用內建的排序工具 sort，搭配 functools.cmp_to_key 與自訂比較式；在 C++ 可以用 algorithm 函式庫的 sort，搭配 lambda function 自訂比較式，寫起來會快很多。

Python 程式碼

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

import sys
from functools import cmp_to_key

def mycmp(a, b):
    if a%10 == b%10:
        if a > b: return -1
        elif a < b: return 1
        else: return 0
    elif a%10 < b%10: return -1
    else: return 1

for line in sys.stdin:
    n = int(line)
    arr = list(map(int, sys.stdin.readline().split()))
    arr.sort(key = cmp_to_key(mycmp))
    print(*arr)

ZeroJudge 解題筆記：a224. 明明愛明明

作者：王一哲
日期：2025年7月3日


ZeroJudge 題目連結：a224. 明明愛明明

解題想法

先將所有字母轉成小寫，再用字典或表格計數，計算每個字母出現的次數，同時計算所有字母的數量 n。如果 n 是奇數，只能有一個字母的數量是奇數；如果 n 是偶數，所有的字母數量都必須是偶數。

Python 程式碼

寫法1，字典計數，使用時間約為 22 ms，記憶體約為 3.6 MB，通過測試。

import sys
from collections import defaultdict

def check(s):
    n = 0
    cnt = defaultdict(int)
    for c in s.lower():
        n += 1
        if c.isalpha():
            cnt[c] += 1
    even = sum(v%2 for v in cnt.values())
    if n%2 == 1:
        return even <= 1
    else:
        return even == 0

for line in sys.stdin:
    print("yes !" if check(line.rstrip()) else "no...")

ZeroJudge 解題筆記：a216. 數數愛明明

作者：王一哲
日期：2025年7月2日


ZeroJudge 題目連結：a216. 數數愛明明

解題想法

方法1，使用函式遞迴，但是可能會因為遞迴次數太多而超時。方法2，找一般式，例如 $$ \begin{align*} f(1) &= 1\\ f(2) &= 2 + f(1)\\ f(3) &= 3 + f(3)\\ & \vdots \\ f(n) &= n + f(n-1) \end{align*} $$ 將以上式子相加可得 $$ f(n) = 1 + 2 + 3 + \dots + n = \frac{1}{2} \cdot n(n+1) $$ 接下來求 $g(n)$，先列出幾行 $$ \begin{align*} g(1) &= 1\\ g(2) &= f(2) + g(1)\\ g(3) &= f(3) + g(2)\\ & \vdots \\ g(n) &= f(n) + g(n-1) \end{align*} $$ 將以上式子相加可得 \begin{align*} g(n) &= f(1) + f(2) + f(3) + \dots + f(n)\\ &= \frac{1}{2} \sum_{i=1}^n (i^2 + i)\\ &= \frac{1}{2} \cdot \left [ \frac{1}{6} \cdot n(n+1)(2n+1) + \frac{1}{2} \cdot n(n+1) \right ]\\ &= \frac{1}{12} \cdot n(n+1) \left [ (2n+1) + 3 \right ] \\ &= \frac{1}{6} \cdot n(n+1)(n+2)\\ \end{align*}

Python 程式碼

方法1，使用函式遞迴，果然不意外地在測試題會超時。

import sys

def f(n):
    if n == 1: return 1
    else: return n + f(n-1)

def g(n):
    if n == 1: return 1
    else: return f(n) + g(n-1)

for line in sys.stdin:
    n = int(line)
    print("{:d} {:d}".format(f(n), g(n)))

方法2，找出一般式直接代入 n 求答案，使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def f(n):
    return int(n*(n+1)/2)

def g(n):
    return int(n*(n+1)*(n+2)/6)

for line in sys.stdin:
    n = int(line)
    print("{:d} {:d}".format(f(n), g(n)))

ZeroJudge 解題筆記：a054. 電話客服中心

作者：王一哲
日期：2025年7月1日


ZeroJudge 題目連結：a054. 電話客服中心

解題想法

先取英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起，存到一個對應的陣列之中。依照規則計算數字部分的編碼 code，加上英文字母對應的值要能被 10 整除，因此答案就是 (10 - code%10) % 10 對應的字母。

Python 程式碼

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

# 英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起
letters = ("BNZ", "AMW", "KLY", "JVX", "HU", "GT", "FS", "ER", "DOQ", "CIP")
s = input()  # 身分證字號
# 依照規則計算數字部分的編碼，加上英文字母對應的值要能被 10 整除
code = sum(int(c)*(8-i) for i, c in enumerate(s[:9])) + int(s[-1])
print(letters[(10 - code%10) % 10])

C++ 程式碼

使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    // 英文字母對應的兩位數字，第1位加上第2位乘以9，再取個位數相同的放一起
    string letters[10] = {"BNZ", "AMW", "KLY", "JVX", "HU", 
                          "GT", "FS", "ER", "DOQ", "CIP"};
    string s; cin >> s;  // 身分證字號
    // 依照規則計算數字部分的編碼，加上英文字母對應的值要能被 10 整除
    int code = 0;
    for(int i=0; i<9; i++) code += (s[i]-'0')*(8-i);
    code += s.back() - '0';
    cout << letters[(10 - code%10) % 10] << "\n";
    return 0;
}