# APCS 心得 + 記得的題目 + 廢廢題解

## 心得

P1 差點忘記要判斷算出的分數是不是負的，還好檢查了\
P2 讀懂題目在說什麼讀了一段時間，但寫起來算輕鬆的\
P3 一開始想用 C++ 跟 類別寫，後來改用 python 加遞迴，希望不要 TLE\
P4 有想到不知道對不對的解法，最後沒寫完QQ

這次是筆電考場但其實沒什麼差，桌面環境還是很難用，一直想用快捷鍵都沒反應...\
沒有常用的文字編輯器(vs code)其實還好，用 vim 打其實很舒服，只是 terminal emulator 也有點不習慣

## 題目

### P1

輸入第一行給定 $K$\
輸入接下來$K$行中\
第$i$行 ($1\leq i \leq K$)\
包含 $s_i$ 和 $t_i$\

$bad = $ 符合 $s_i$ == -1 的 i 的總數\
$maxt = t_i$，其中 i 為最小的整數 $1\leq i \leq K$ 使得 $s_i = \max(s)$\
$score = \max(\max(s) - K - 2 * bad, 0)$\
輸出一行 `score maxt`

### P2

輸入一行給定 $k$ $q$ $r$\
輸入一行長$k$的字串$s$\
輸入接下來的$q$行中\
第$i$行包含 $k$ 個整數 $p_{i,j}$ ($1\leq j \leq k$)

排列 $per_1$ 的第 $p_{1,i}$ 個字元 \($1\leq i \leq k$) 為 $s$的第 i 個字元
排列 $per_j$ 的第 $p_{j,i}$ 個字元 \($2\leq j \leq q$, $1\leq i \leq k$)
為上一個排列 $per_{j-1}$ 的第 i 個字元

例子\
$s$ = A P C S\
$p_1$ = 4 1 3 2\
$per_1$ = P S C A

最後輸出 r 個單字\
第 i 個單字是由每個 per_j 的第 i 個字元組成

### P3

給定一個算式 s 中包含 0~9 的正整數，以及字元 `f(),+*`\
試計算 s，印出算得的值

計算方式：先加後乘，f(...) ... 中可以有數個被逗號分格的合法算式，f(...) 的值為每個算式所算得的值中的最大值減去最小值\
例如 f(6)=0 f(1,5,6,10)=9

### P4

第一行給定 n 及 k\
第二行給定 n 個整數，每個整數代表第 i 個區間的開頭 $s_i$\
第三行給定 n 個整數，每個整數代表第 i 個區間的結尾 $f_i$\
輸出最大的數字 m ，使得存在至少一個所給區間集合的子集合，\
此子集合有 m 個區間，其中每個位置至多有 k 個區間重疊。

## 題解

### P1 解

一邊讀數字就可以一邊紀錄最大值跟發生時間了\
資料是按時間順序給的，所以不用另外排序

另外要注意算出來成績是負的要輸出 0

### P2 解

因為最後輸出時是類似橫過來輸出的，所以還是要存每個排列或是每個輸出才夠

我的解法是開一個 `k*q` 的陣列 `per` 存排列的字元，在讀入 `p` 的時候就一個一個把 `per` 的值填進去

因為每個排列是用上一個排列的字元，只有第一個是用讀進來的字串 s ，所以我在實作時用了一個指標`last` 代表要從哪裡拿字元，讀完一行順序再把 `last` 改成寫完的那一行

最後再橫著輸出 `per` 的內容就可以了

### P3 正常解

這題在賽中我是用遞迴解的\
就是寫一個函數計算一段算式的值\
如果在算式最外層有 `*` 就拆成左右兩個算，
算好再相乘\
否則若有 `+` 就拆成左右兩個算，算好相加\
最後若有 `f(` 跟 `)` 就把裡面的根據外層的逗點分開，
分開計算完再取最大最小相減
如果上面都沒有的話，就一定是一個整數了
你可以自己寫個函數處理或是用 python 的 `int`

有個小小的實作細節是在分東西的時候要注意順序，
判斷的順序決定你到底是相加後乘還是先乘後加。
另外還有是要判斷的是跟你同一層的東西，例如如果有`f(1, 1+3)`
雖然式子裡面有 `+`，但它在一層括號裡面，你應該優先處理掉外層的 `f`，但如果是 `f(1,1)+3` ，你就該優先拆成 `f(1,1)` 還有 `3` 再相加了

### P3 eval 奇怪解

在考試時這題我花了一點時間想有沒有什麼神奇的解法，
感覺這題就可以用 eval 跟一些很黑科技的手段解決掉，
但因為跟 python 的語法不夠熟就沒在考試中用這個方法寫。

後來跟 Cro 討論了一點後，又查了一些 python 語法，就寫出來了。\
以下寫這個解法時要注意的一些事情:

- eval 的意思就是把一個字串當成一個 python 運算式來執行，並會回傳運算的結果（這東西有點危險，用起來要小心）
- python 中可以定義型別，並進行運算子多載
- 運算子多載不會改變運算子的優先順序
- python 是動態型別的，有些函數只要型別定義了運算就自動可以用

::: spoiler 解法打開收

# 因為好像不能直接覆蓋int的加法跟減法
# 所以定義一個型別來處理
# 注意加法跟乘法的定義是反過來的
# return 的東西也要用 A() 包住，型別才不會跑掉
# 會需要定義 gt 是因為 max 跟 min 需要
class A:
    def __init__(self, n):
        self.n = n
    def __add__(self, b):
        return A(self.n * b.n)
    def __sub__(self, b):
        return A(self.n - b.n)
    def __mul__(self, b):
        return A(self.n + b.n)
    def __gt__(self, b):
        return self.n>b.n

# 用 *args 就可以讀很多個數字了
# 這邊有用到 - ，所以還是要定義一下 A 的減法
# 或是也可以拿出來減再包回去
def f(*args):
    return max(args)-min(args)

# 把 + 跟 * 反過來，這樣運算順序就會對了
s = input().replace('*', '.').replace('+', '*').replace('.', '+')
# 讓每個數字 a 都變成 A[a]，再多的 ]A[ 刪掉
# 最後再把 [ ] 換回括號
# 其實直接用 ( ) 應該也可以
s = ''.join(map(lambda a: 'A['+a+']'if a.isnumeric() else a, s))
s = s.replace(']A[','').replace('[', '(').replace(']', ')')
# 可以算了，好欸
# 算出來也是一個 A 物件，要把 n 拿出來
print(eval(s).n)

:::

### P4 解法？

感覺可以排序每一組 s跟f 之後用 dp[剩下的機器數量] = 完成了幾單 ，來作，但需要另外存機器用完的時間

我不確定這個作法是不是好的，也沒寫出來

有人知道作法可以告訴我，我會很快樂（？