APCS 2023/1月題解

# APCS 2023/1月題解 ## ==程式考試== ### 敘述 給 n 個提交紀錄，第 i 個提交紀錄有兩個整數 ti 和 si 代表上傳時間和該次上傳的分數，若第 i 次的提交結果為嚴重錯誤，則 si 為 -1。計算總分的公式為提交紀錄中的最高分 - 總提交次數 - 總嚴重錯誤次數 * 2，若計算出來的分數為負數則計為 0 。請輸出總分和第一次獲得最高分的時間點。 ### 輸入說明 第一行有一個正整數 K (1<=K<=6) 代表提交的次數，接下來有 K 行，第 i 行有兩個整數 ti 和 si (1<=ti,si<=100) 。保證提交紀錄按照時間點嚴格遞增排序，並且第一個提交紀錄不會是嚴重錯誤。 ### 輸出說明 輸出兩個整數，代表總分和第一次獲得最高分的時間點。 ### 核心 條件判斷 ### 思路 很簡單，只是變數會設比較多。 ```c++= #include<bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); int time,score; int maxScoreTime=0,maxScore=-2,badtime=0; for(int i=0;i<n;i++) { scanf("%d%d",&time,&score); if(score>maxScore) maxScoreTime=time,maxScore=score; if(score==-1) badtime++; } maxScore-=(n+badtime*2); maxScore=max(0,maxScore); printf("%d %d\n",maxScore,maxScoreTime); } ``` ## ==造字程式== ### 敘述 有一個長度 K 的初始字串 S ，每個字元都是小寫的英文字母。接下來有 Q 次的修改，每次的修改會把舊的字串重新排列成一個新的字串。更具體來講，每次修改時會給一個 1 ~ K 的排列 P=[P1,P2,...,Pk] ，要將舊字串的第 i 的字元複製到新字串的第 Pi 個字元。在 Q 的修改中，每次修改出來的新字串會被當成下一次修改中的舊字串，而第一次修改時使用的舊字串就是初始字串。題目另外會給一個數字 R ，請依照下面定義的順序輸出 R 行，每行 Q 個字元 - 輸出操作 1 ~ Q 的新字串的第 1 個字元 - 輸出操作 1 ~ Q 的新字串的第 2 個字元 - ... - 輸出操作 1 ~ Q 的新字串的第 Q 個字元 ### 輸入說明 第一行有三個整數 K,Q,R 第二行是長度 K 的初始字串接下來有 Q 行，每行有是一個 1 ~ K 的排列 ### 輸出說明 請依照題目敘述輸出 RxQ 個字元 ### 核心 二維陣列、模擬 ### 思路 設二維陣列，列向下模擬。 ```c++= #include<bits/stdc++.h> using namespace std; int main() { int K,Q,R; char str[25][25]; scanf("%d%d%d%s",&K,&Q,&R,str[0]); int locate; for(int i=1;i<=Q;i++) { for(int j=0;j<K;j++) { scanf("%d",&locate); str[i][locate-1]=str[i-1][j]; } } for(int j=0;j<R;j++) { for(int i=1;i<=Q;i++) printf("%c",str[i][j]); printf("\n"); } } ``` ## ==先加後乘與函數== ### 敘述 給一個運算式，運算式的內容由數字、+、* 和某個函式 f() 所組成，除了函式以外不會有額外的括號。請將此運算式依照先加後乘的方式運算。函式 f(x1,x2,x3,...) 定義為從這個不定長度的參數中的最大值扣掉最小值。 ### 輸入說明 輸入一個運算式，保證長度不超過 500 ，出現在運算式內的數字介於 0 到 200 之間，除了函式 f() 之外不會出現多餘的括號，並且運算式一定合法。 ### 輸出說明 輸出運算式的計算結果，此題運算過程和答案可能超過 2^31^ 但不超過 10^17^。 ### 核心 遞迴 ### 思路 這題我卡很久，困在f嵌套的處理以及運算的不當，最後參考別的大佬的解法才頓悟。 [大神解法](https://hackmd.io/@QWERTYPIG/SJG4_ztoo#APCS-2023%E5%B9%B401%E6%9C%88%E9%A1%8C%E8%A7%A3) ## ==機器出租== ### 敘述 有 N 個活動，舉辦每個活動都要租借一台機器，若要舉辦第 i 個活動，就需要在時間段 [Li,Ri] 租借用一台機器。已知 N 個活動的需要使用的時間段，並且有 K 台機器可以開放租借，且一台機器同時間只能借給一個活動，請問最多可以成功舉辦多少場活動？ ### 輸入說明 第一行有兩個正整數 N 和 K 第二行有 N 個正整數，第 i 個正整數是活動 i 的開始時間第三行有 N 個正整數，第 i 個正整數是活動 i 的結束時間 ### 輸出說明 輸出一個整數表示最多可以舉辦多少活動。 ### 核心 貪心法 ### 思路 要如何在O(n)時間內，資料從頭掃到尾解決? 先用struct記錄活動開始時間和結束時間，接著建一個陣列。貪心嘛，故我希望結束時間越快越好，機器才能給下一場活動使用，所以我對結束時間大小進行排序(需用到比較函數)。若K=1: endtime記錄結束時間，若下一場活動開始時間<endtime，則很高興，我可以租借給此活動，再把endtime更新為下場活動的結束時間。以此概念走訪一次陣列，答案必定包含在最佳解內。若K=N 以set記錄目前租借活動的結束時間，每次取最快結束時間出來做比較，若下一場開始時間小於此結束時間，則K不動，機器輪替就好，若大於的話，則租借一台新的機器給它。很直觀，狀態會一直保持所有機器都租出去，機器不可能回來了哈哈哈。 ```c++= #include<bits/stdc++.h> using namespace std; #define N 100005 struct Time { int start,finish; }; bool cmp(Time x, Time y) { return x.finish<y.finish; } int main() { int n,k; Time activity[N]; scanf("%d%d",&n,&k); for(int i=0;i<n;i++) scanf("%d",&activity[i].start); for(int i=0;i<n;i++) scanf("%d",&activity[i].finish); sort(activity,activity+n,cmp); multiset<int> endtime; endtime.insert(-1),k--; int num=0; for(int i=0;i<n;i++) { auto it=endtime.lower_bound(activity[i].start); if(it!=endtime.begin()) { it--; num++; endtime.erase(it); endtime.insert(activity[i].finish); } else if(k>0) { k--; num++; endtime.insert(activity[i].finish); } } printf("%d\n",num); } ```