第一次考APCS心得

2025-01-05

摘要

這是我高一去參加APCS的經驗，和一個同班同學去考的，我跟他會去圖書館研究考古題，然後跟他一起去考。那時候還是舊制度，觀念用C語言、實作用Python。

觀念：80分(四級分)
實作：200/400(三級分)

題號	分數
1	100/100
2	100/100
3	0/100
4	0/100

😭 高一那時候對演算法不是很熟，只有寫基礎的兩題。

題解

P1 - 等紅綠燈

link >> https://zerojudge.tw/ShowProblem?problemid=q181
難度：APCS初?

題目敘述

操場起跑線上有一個紅綠燈，綠燈為 $a$ 秒，紅燈為 $b$ 秒，依照綠燈紅燈的順序循環。有 $n$ 個小朋友，從操場的起跑線騎腳踏車一起起跑，他們分別騎完一圈的時間為 $t_1, t_2, t_3, ... t_n$ 。若騎到終點時為紅燈，需要等待紅燈結束變為綠燈才可以停止騎車。求出這 $n$ 個小朋友共需要等待幾秒的紅燈秒數。

想法

cycle_time 決定 $t_i$ 完成一圈後所剩餘的循環秒數，如果不小於 $a$ ，代表當前為紅燈，就要將剩餘的紅燈等待時間加入到 total_time 中。

解答

def solve(a, b, n, T):
    total_time = 0
    cycle_time = a+b

    for t in T:
        arrive = t % cycle_time
        if arrive >= a:
            wait_time = cycle_time-arrive
            total_time += wait_time

    return total_time

a, b = map(int, input().split())
n = int(input())
T = list(map(int, input().split()))
result = solve(a, b, n, T)
print(result)

P2 - 字串操作

link >> https://zerojudge.tw/ShowProblem?problemid=q182
難度：APCS初?

題目敘述

給一個字串 $S$ (長度為偶數)，有三種字串操作，分別如下

1. 兩兩交換：將字串內相鄰兩個字元交換，例如字串 “apcsntnu” 先分組成 (ap)(cs)(nt)(nu)，將會交換為 (pa)(sc)(tn)(un)，即得到 “pasctnun”。
1. 兩兩排序：將字串內相鄰兩個字元按照字典序排序，字元的字典序為 a < b < … < z，例如字串 “family” 先分組成 (fa)(mi)(ly)，將會交換成 (af)(im)(ly)，即得到 “afimly”。
1. 完美重排：假設字串長度為 $n$ ，將字串內的字元編號為 $0,1,2,...,n-1$ ，將字串分成兩半為 $0,1,2,...,\frac{n}{2}-1$ 和 $\frac{n}{2}, \frac{n}{2}+1, ..., n-1$ ，並且組合成 $0,\frac{n}{2},1,\frac{n}{2}+1,...,\frac{n}{2}-1,n-1$ 。例如"apcsntnu"拆成"apcs"和"ntnu"，然後交錯成 “anptcnsu”。

想法

定義三個函式，代表三個操作，只要按照題目要求操作就好，沒有什麼好想的。

解答

def op0(s):
    s = list(s)
    for i in range(2, len(s)+1, 2):
        s[i-2], s[i-1] = s[i-1], s[i-2]
    
    return "".join(s)

def op1(s):
    s = list(s)
    for i in range(2, len(s)+1, 2):
        s[i-2:i] = sorted(s[i-2:i])
    
    return "".join(s)

def op2(s):
    mid = len(s)//2

    result = [""]*len(s)
    left = list(s[:mid])
    right = list(s[mid:])

    for i in range(0, len(s)):
        if i%2 == 0:
            result[i] = left[i//2]
        else:
            result[i] = right[(i-1)//2]
    
    return "".join(result)

s: str = input()
n: int = int(input())
for i in range(n):
    operate = int(input())

    if operate == 0:
        s = op0(s)
    elif operate == 1:
        s = op1(s)
    elif operate == 2:
        s = op2(s)

print(s)

P3 - 重組問題

link >> https://zerojudge.tw/ShowProblem?problemid=q183
難度：APCS中高
從這一題開始後，都是我後來回來看的想法以及題解。

題目敘述

對於一個長度為 $n$ 的陣列 $a_1,a_2,a_3,...,a_n$ ，已知 $a_1=0$ ，定義 $\Delta$ 為陣列中任兩個數字的絕對值差所組成的一群數字。給定 $\Delta$ 的內容，輸出可以生成該 $\Delta$ 的最小與最大字典序陣列。

舉例來說，如果 $n=3$ 且 $\Delta=(3,4,7)$ ，距離最大的是 $7$ ，因為最大距離必定是在最小與最大兩數之間，我們可以推論原序列的最大的數字是 $7$ 。接著，目前已知原序列有 $(0,7)$ ，而距離序列扣除 $7$ 之後剩下 $(3,4)$ ，我們要決定中間點的位置。此時最大的距離是 $4$ ，這個距離必然是該未知點與「最小的0」或與「最大的7」之間的距離，所以這個點可能是 $4$ 或 $3$ ，在檢驗距離序列後，發現兩者皆可能，所以原序列可能是 $(0,3,7)$ 或 $(0,4,7)$ ，其中字典序最小的是 $(0,3,7)$ ，最大的是 $(0,4,7)$ 。

想法

因為那時候的我演算法基礎不佳，我在紙上一直寫，寫到最後也不太知道怎麼辦，最後就只能交出白卷了。

我們可以把一個序列分析他們兩兩之間的距離，距離所組成的序列就叫做 $\Delta$ 。原序列中，最大的元素 $a_n$ 就是 $max(\Delta)-a_1=max(\Delta)$ ，而按照 $\Delta$ 找到字典序小的方法就是依序找到數字最小的元素就好；反過來說，要找到字典序最大的方法就是找到數字元素最大的就好。

在字典序最小的序列中，我可以知道 $a_n$ 一定是 $max(\Delta)$ ，而且為了使 $a_2$ 最小，我一定要將剩下 $\Delta$ 中最大的元素作為 $|a_n-a_2|$ ，就可以確保 $a_2$ 最小；而在字典序最大的序列中，一樣知道 $a_n$ 一定是 $max(\Delta)$ ，而且為了使 $a_2$ 最大，我一定要將剩下 $\Delta$ 中最大的元素作為 $|a_2-a_1|$ ，就可以確保 $a_2$ 最大。而往後我們就依照這個邏輯枚舉，就可以找出原序列了！

我自己舉一個例子 $\Delta=(1,2,2,3,3,5)$ ，接下來我們要透過窮舉、減枝、回溯就可以將所有可能的原序列找出來：
enumerate

解答

from collections import Counter

n = int(input())

if n == 1:
    print(0)
    print(0)
    exit()

delta = [int(i) for i in input().split()]
delta.sort()

max_a = delta.pop()

min_ans = None
max_ans = None

freq = Counter(delta)

A = [0] * n
A[0] = 0
A[-1] = max_a

def try_place(val, placed_points):
    removed = []
    for p in placed_points:
        d = abs(val - p)
        if freq[d] > 0:
            freq[d] -= 1
            removed.append(d)
        else:
            for rd in removed:
                freq[rd] += 1
            return False, []
    return True, removed


def restore(removed):
    for d in removed:
        freq[d] += 1

def dfs_min(left, right, placed):
    global min_ans
    if left > right:
        min_ans = list(A)
        return True

    d = max(k for k, v in freq.items() if v > 0)

    # A[right] = max_a - d
    val_r = max_a - d
    ok, removed = try_place(val_r, placed)
    if ok:
        A[right] = val_r
        if dfs_min(left, right - 1, placed + [val_r]):
            return True
        restore(removed)

    # A[left] = d
    val_l = d
    ok, removed = try_place(val_l, placed)
    if ok:
        A[left] = val_l
        if dfs_min(left + 1, right, placed + [val_l]):
            return True
        restore(removed)

    return False

def dfs_max(left, right, placed):
    global max_ans
    if left > right:
        max_ans = list(A)
        return True

    d = max(k for k, v in freq.items() if v > 0)

    # A[left] = d
    val_l = d
    ok, removed = try_place(val_l, placed)
    if ok:
        A[left] = val_l
        if dfs_max(left + 1, right, placed + [val_l]):
            return True
        restore(removed)

    # A[right] = max_a - d
    val_r = max_a - d
    ok, removed = try_place(val_r, placed)
    if ok:
        A[right] = val_r
        if dfs_max(left, right - 1, placed + [val_r]):
            return True
        restore(removed)

    return False

placed_init = [0, max_a]

dfs_min(1, n - 2, placed_init)

freq = Counter(delta)
dfs_max(1, n - 2, placed_init)

if min_ans and max_ans:
    print(*sorted(min_ans))
    print(*sorted(max_ans))
else:
    print("Not found")

P4 - 分組開會

link >> https://zerojudge.tw/ShowProblem?problemid=q184
難度：應該是現在的APCS高級

題目敘述

在 $n$ 人在一個數線上，他們的位置座標分別為 $x_1,x_2,...,x_n$ 。今天要從 $n$ 個人中挑 $2k$ 的人開兩場會議，每一場會議要恰好 $k$ 個人參與，並且每一個人最多只能參與一個會議。若一個人位在 $x$ ，欲前往 $y$ 開會需要移動 $|x-y|$ 。請求出安排這兩場會議，使得參與會議的人移動距離總和最小值為何。