想知道2022年10月解題可以點此連結 10月份解題
寫完APCS題目後的碎碎念
本次APCS題目有點令人感到意外，相較於之前的題目考的觀念有點略為不同。
第一題是為迭代的基本題，只須看清題目即可簡單地利用迴圈計算出答案。
第二題是雖然是字串處理，但個人認為比較偏向矩陣，利用矩陣可以快速地解出此題答案。
第三題考驗也是字串處理，但結合了遞迴或者是stack的概念，但就算是不熟悉遞迴以及stack依然可以使用普通方法獲得30分，算是良心題。特別用Python寫可以用特殊方法解答，方便很多
第四題就是使用貪婪演算法，只要有想到兩個解題重點：1.依結束時間排序 2. 富有操死機器的精神，有學過基本語法的人應該都可以簡單地寫出這一題。
這四題寫完的話，個人認為拿到四級分是比以前輕鬆的，只要好好地把前幾子題回答出來即可。但是要獲得五級分的話就要答對全部題目。這次五級分的人數應該會比上次少吧？
ZeroJudge 題目
程式考試
直接連TimeStamp
題目簡述：
首先我們知道輸入總共有K筆資料，每筆資料會有兩個元素分別是時間(t)跟分數(s)，然後題目要求我們要找到最高分的時間以及計算最終的成績，這邊要注意最終成績不完全是最高分成績喔！還需要經過一些函式運算才可以，否則這一題就太簡單了。
看向上面的圖，你會看到t跟s。那題目裡面有提到，t是嚴格遞增，所以一定會按照順序排好(但老實說這題跟t的大小順序也無關就是了)，而s會是-1~100之間的數字，在這例子你會看到，最高的分數是60分，而且犯嚴重錯兩次。那接下來我們就要套用題目所提到的公式囉，公式這邊寫到，最終我們要給予的答案為maxScore – totalSubmit(也就是K)– error*2。那這邊計算完畢後會得到51，這就會是這例子的答案。
有了以上的概念後我大概上一下解題流程
輸入：
1. 正整數K
2. K行，t(提交時間) 和 s(分數)
邏輯：
1. 記錄高光時刻 -> maxScore
2. 紀錄Error次數 -> error
輸出 ：
1. maxScore – totalSubmit (K) – error*2
2. 若分數小於0則以0計算
K = int(input())# 1. 正整數K
# 2. K行，t(提交時間) 和 s(分數)
maxScore,time,error = -1,0,0
for i in range(K):
t,s = [int(i) for i in input().split()]
if s>maxScore:#記錄高光時刻 -> maxScore
maxScore = s
time = t
if s == -1:#紀錄Error次數 -> error
error += 1
ans = maxScore - K - 2*error#maxScore - totalSubmit (K) – error*2
if ans < 0:#若分數小於0則以0計算
ans = 0
print(ans,time)
以上為解題過程，若有任何意見歡迎留言。
CodingBar Python基礎班開跑中~有興趣可以點擊連結
造字程式
直接連TimeStamp
題目簡述：
首先我們知道會先輸入 K、Q、R 三筆資料，其中K代表字串S的長度。
Q是代表了字串修改的次數，R是代表前R行的字串要進行輸出，也就是現在紅色框起來的部分。當R等於1時輸出第一行，等於2時輸出第二行，以此類推。那這邊給一個很簡單的範例輸入，讓我們來觀察一下這東西是如何進行資料交換的。對此不熟悉的同學，可以學習這樣的技巧幫助自己整理思緒。
它代表了A要被交換到第四個格子，P要被交換到第一個格子，C要被交換到第三個格子，S要被交換到第二個格子，也就是被交換一次後會變成PSCA。也就是被交換一次後會變成PSCA這樣子的狀況，那我這邊大致上也寫了一個若以list形式考量的話，此字串會是如何變化的示意圖。這很重要，等等寫程式會用到，千萬不要忘記了。後面皆以相同的格式進行。
有了以上的概念後我大概上一下解題流程
輸入：
1. 正整數K、Q、R
2. 字串S
3. Q行，1~K不重複的數字 -> nums
邏輯：
1. 需要記錄新字串 -> newS
2. 透過for迴圈讀取nums，將s字串存入newS
3. 需要紀錄每種型態的newS -> sList
4. 調整sList格式，使之行列顛倒
輸出：
1. 透過for迴圈將第R行的字母進行輸出。
k,q,r = [int(i) for i in input().split()]
s = list(input())
sList = []
for _ in range(q):
nums = [int(i) for i in input().split()]
newS = [""]*k
for i in range(len(nums)):
newS[nums[i] - 1] = s[i]
s = newS
sList.append(s)
newSList = list(zip(*sList))
for i in range(r):
print("".join(newSList[i]),end="")
以上為解題過程，若有任何意見歡迎留言。
先加後乘與函數
直接連TimeStamp：
題目簡述：
首先我們知道會先輸入字串S，裡面只會含有數字、+號、*乘號跟f()
那這一題有很多種作法舉凡遞迴或者是stack，那我這邊會用stack的方式來進行。
接著把加號計算完畢再把乘號丟回去，最後再計算一次就可以得到答案囉~
當我找到f時，其實就代表他右邊一定會有左括弧跟右括弧。但這邊要注意喔，f裡面可能再包著一層f，所以我在查找的時候，會直接查到最深層的f，然後開始計算括弧裡面的數字。那由於這邊的括弧必定會成對，所以不用擔心往右找找不到右括弧，直接把括弧裡面的數字抓出來運算，所以f(3,2)就變成1了。
接著回到剛剛也有碰到f的地方，然後往右找與他成對的右括弧，但這邊在運算時可能會出現小問題，
那就是還有加號與乘號沒有計算，因此我不能夠直接求f()，所以其實這邊在運算前，要先把被逗點分隔的數字們進行判斷，看是否需要計算乘號或者是加號。所以就變成了f(8,9,1)，那f(8,9,1)會再被計算8，最後就可以直接求出答案囉！但別忘記+號優先於乘號唷！
有了以上的概念後我大概上一下解題流程
輸入：
1. s字串
邏輯：
1. s字串不含f的狀況 -> nof()
2. s字串含f的狀況 -> 尋找成對的括弧們(直接找最內層的)
3. 找到成對括弧 -> 逗點與逗點間的是否含”+”或”*”
3-1.是 -> nof()
3-2.不是 -> f()
4. 計算完的結果取代原本位置上的文字，方便下次運算
5. 2~4循環
輸出：
1. 輸出計算結果
以下有可愛的程式碼，首先如果你只要30%的話
def noF(s):
temp = s.split('*')
for i in range(len(temp)):
temp[i] = eval(temp[i])
result = "*".join(map(str,temp))
return eval(result)
s = input()
if "f" not in s:
ans = noF(s)
print(ans)
如果你想要全對的話~
def noF(s):
temp = s.split('*')
for i in range(len(temp)):
temp[i] = eval(temp[i])
result = "*".join(map(str,temp))
return eval(result)
def f(*args):
a,b = max(args),min(args)
return a-b
s = input()
if "f" not in s:
ans = noF(s)
print(ans)
else:
leftPar = [i for i,v in enumerate(s) if v == 'f']
while leftPar:
leftIndex = leftPar.pop()
i = leftIndex
while 1:
if s[i] == ")":
rightIndex = i
break
i+=1
temp = s[leftIndex:rightIndex+1].split(',')
for i in range(len(temp)):
if 'f(' in temp[i] and ')' in temp[i]:
temp[i] = str(eval(temp[i]))
elif "+" in temp[i] or "*" in temp[i]:
if 'f(' in temp[i]:
temp[i] = 'f(' + str(noF(temp[i][2:]))
elif ')' in temp[i]:
temp[i] = str(noF(temp[i][:-1])) + ')'
else:
temp[i] = str(noF(temp[i]))
temp = ",".join(temp)
if 'f' in temp:
temp = str(eval(temp))
s = s[:leftIndex] + temp + s[rightIndex+1:]
ans = noF(s)
print(ans)
以上為解題過程，若有任何意見歡迎留言。
機器出租
直接連TimeStamp：
題目簡述：
目有提到會有K台機器以及N個活動，每台機器在一個時間點只能參與一個活動，求可以參與的最大活動數。
因此我先畫這樣的圖出來，K那邊的-1代表機器未被使用，N那邊的數字代表活動時間
首先遇到活動[0,3]，先把一台機器紀錄結束時間，接著遇到活動[1,4]，由於另外一台機器使用中，因此把它讓給另外一台機器使用，我這邊偷偷switch機器的排列順序，這等等寫程式時會用到相同概念。接著遇到活動[5,6]，這邊就要注意了，我們應該選擇結束時間為4的機器，而不能選擇為3的，要不然下個活動時會直接少一台機器使用，這邊要好好思考一下，要怎麼用程式處理這件事情。接著遇到活動[4,6]
使用另外一台機器。最後就是7。因此，此範例可以五個活動都跑到。
有了以上的概念後我大概上一下解題流程
輸入：
1. N個活動、K台機器
2. 第二行為開始時間、第三行為結束時間
邏輯：
1. 合併開始與結束時間
2. 優先尋找最先結束的時間
3. 把機器操死的精神 -> 在可以的機器中永遠找最晚結束的機器
輸出：
就輸出可以參與的活動數量
以下是40%的程式碼~
N,K = [int(i) for i in input().split()]
start = [int(i) for i in input().split()]
end = [int(i) for i in input().split()]
timeS = [[start[i],end[i]] for i in range(N)]
timeS.sort(key = lambda x:(x[1]))
endTime = -1
ans = 0
for start,end in timeS:
if start > endTime:
ans+=1
endTime = end
print(ans)
以下是100%的程式碼~
# 流程：
# 輸入：
import bisect
N,K = [int(i) for i in input().split()]# 1. N個活動、K台機器
start = [int(i) for i in input().split()]# 2. 第二行為開始時間、第三行為結束時間
end = [int(i) for i in input().split()]
timeS = [[start[i],end[i]] for i in range(N)]# 1. 合併開始與結束時間
timeS.sort(key = lambda x:(x[1]))
endTime = [-1]*K
ans = 0
for start,end in timeS:
if min(endTime)>= start:#如果沒有閒置的機器
continue
index = bisect.bisect_left(endTime,start)-1
del endTime[index]
endTime.append(end)# 3. 把機器操死的精神 -> 在可以的機器中永遠找最晚結束的機器
# 2. 優先尋找最先結束的時間
ans+=1
print(ans)
以上為解題過程，若有任何意見歡迎留言。
