# APCS 2023年01月題解
## 第一題 程式考試
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=j605
### 解套
N/A(抱歉我真的不知道要寫甚麼)
### 題目分析
維護三個變數$mx$、$mxtime$、$errors$存最高分、最高分發生時間與嚴重錯誤次數
接下來就一一讀入測資並依題目敘述處理，時間複雜度$O(K)$
### 解題流程
讀入測資$→$更新變數$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
int k,s,t,mx=-1,mxtime,errors=0;
```
#### 輸入與處理
```cpp=5
cin>>k;
for(int i=0;i<k;i++){
cin>>t>>s;
if(s==-1)errors++;
else if(s>mx){
mx=s;
mxtime=t;
}
}
```
得到時間與分數後，若為嚴重錯誤則將$errors$加一，
不然判斷該分數是否為目前最高的，若是則更新$mx$與$mxtime$
#### 輸出
```cpp=14
cout<<(mx-k-errors*2>0?mx-k-errors*2:0)<<" "<<mxtime;
```
分數部分按照題意計算後，若為負數輸出$-1$
※三元運算子：
```cpp
if(mx-k-errors*2>0)cout<<mx-k-errors*2;
else cout<<0;
//等價於
cout<<(mx-k-errors*2>0?mx-k-errors*2:0);
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
int k,s,t,mx=-1,mxtime,errors=0;
int main(){
cin>>k;
for(int i=0;i<k;i++){
cin>>t>>s;
if(s==-1)errors++;
else if(s>mx){
mx=s;
mxtime=t;
}
}
cout<<(mx-k-errors*2>0?mx-k-errors*2:0)<<" "<<mxtime;
}
```
## 第二題 造字程式
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=j606
### 解套
裸的字串處理，唯一需要注意的是輸出需求
### 題目分析
按照題目需求照做就好，並在每個操作後把會用到的字元存起來，最後再輸出。
實作上採用比較直觀但稍微沒有效率的做法(反正這是APCS第二題複雜度不是重點)，就是每次操作直接原地複製一個新字串，並以其為操作基準
每次操作完再將新字串第$0～r-1$個字元存起來，時間複雜度$O(Q(R+K))$
### 解題流程
輸入$→$$($輸入操作$→$處理、儲存$)_{循環}$$→$輸出
### 解題過程
#### 變數宣告
```cpp=3
string s;
int k,q,r,p[20];
```
變數名稱與題目描述相同
```cpp=7
vector<vector<char>>ans(r,vector<char>(q,' '));
```
儲存答案的陣列，大小為$r*q$
#### 操作處理
```cpp=8
for(int i=0;i<q;i++){
for(int j=0;j<k;j++)cin>>p[j];
string tmp=s;
for(int j=0;j<k;j++)s[p[j]-1]=tmp[j];
for(int j=0;j<r;j++)ans[j][i]=s[j];
}
```
先讀入操作陣列 $p$，再複製一個跟$s$一樣的$tmp$當做操作時的參考
接下來(第11行)就是按照$tmp$ 與 $p$把新字串複製到$s$ 裡
最後(第12行)將操作後的字串存到答案陣列裡
#### 輸出
```cpp=14
for(int i=0;i<r;i++){
for(int j=0;j<q;j++)cout<<ans[i][j];
cout<<"\n";
}
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
using namespace std;
string s;
int k,q,r,p[20];
int main(){
cin>>k>>q>>r>>s;
vector<vector<char>>ans(r,vector<char>(q,' '));
for(int i=0;i<q;i++){
for(int j=0;j<k;j++)cin>>p[j];
string tmp=s;
for(int j=0;j<k;j++)s[p[j]-1]=tmp[j];
for(int j=0;j<r;j++)ans[j][i]=s[j];
}
for(int i=0;i<r;i++){
for(int j=0;j<q;j++)cout<<ans[i][j];
cout<<"\n";
}
}
```
## 第三題 先加後乘與函數
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=j607
### 解套
計算一式子，但是先加減後乘，並且有一神秘函數$f$，會回傳參數內的最大值減最小值
### 題目分析
基本上跟經典的「計算式子」題目相似，只是少了除法，以及多了$f$函數
就我所知一般會用遞迴或是stack寫，我個人是偏好遞迴的寫法
實作上我寫了三個函式，分別是獲取數字的getnum、一般計算的cal以及算$f$函式的fcal
在一開始先讀入整個字串，並用全域變數id紀錄目前處理到哪一個位置
時間複雜度$O(N)$，其中$N$為字串長度
### 解題流程
呼叫cal函式$→$輸出答案
### 解題過程
#### 開 long long
```cpp=2
#define int long long
```
因為到最後才發現，而且懶得把每個int都改成long long
不過int main()要改成signed main()，因為main函式不能是 long long
#### 變數宣告
```cpp=4
string s;
int id=0;
```
id紀錄處理到字串的第幾個位置
#### 函式宣告
**1.getnum 函式**
```cpp=6
int getnum(){
int ans=0;
while(id<s.size()&&'0'<=s[id]&&s[id]<='9'){
ans=ans*10+s[id]-'0';
id++;
}
return ans;
}
```
跟一般字串轉數字的方法差不多，好像可以用stoi，但我不太會用
**2.cal、fcal函式**
```cpp=14
int cal(bool cmp);
int fcal();
```
因為他們會互相調用，所以先宣告，到main函式後再定義
**3.cal函式**
```cpp=33
int cal(bool cmp){
int n;
if('0'<=s[id]&&s[id]<='9')n=getnum();
else n=fcal();
if(cmp||s[id]==','||s[id]==')')return n;
while(id<s.size()){
if(s[id]=='+'){
id++;
int b=cal(1);
n+=b;
}
else if(s[id]=='-'){
id++;
int b=cal(1);
n-=b;
}
else if(s[id]=='*'){
id++;
int b=cal(0);
n*=b;
}
if(s[id]==','||s[id]==')')return n;
}
return n;
}
```
cal的參數cmp是決定「要不要馬上回傳」
因為本題先加減後乘，如果遇到加或減需要先運算，乘則不用，在後面會有詳細解釋
一開始先宣告一個變數n來運算與當作回傳的答案
因為呼叫cal時第一個不是數字就是f，故依此決定n的數值(第34~36行)
此時若cmp為1(須馬上回傳)、碰到「,」或「)」(代表在f函式內)，則直接回傳n(第37行)
接下來就是不斷向後運算(第38~55行)，此時分做4種狀況
* 遇到加號
1.將id加一，移到下一個數字
2.呼叫cal(1)並將其值存在變數b裡
3.把n加上b
* 遇到減號
1.將id加一，移到下一個數字
2.呼叫cal(1)並將其值存在變數b裡
3.把n減掉b
* 遇到乘號
1.將id加一，移到下一個數字
2.呼叫cal(0)並將其值存在變數b裡
3.把n除上b
* 遇到「,」或「)」
直接回傳數字
在這邊解釋一下cmp的運作：
假設有一式子$5+2*3+1$，依照這題的規則會得到28(7*4)
當我算到5後面的加號時，因為先加減後乘除，我希望這個加號會**馬上算到**，因此cmp設為1，
這樣算到2時2就會直接回傳，而非繼續往後算$*$的部分
同理算到$*$時，會希望後面的3+1先算完再一起乘，所以cmp設為0，
這樣算到3時就會繼續往後算，最後再回傳
函式最後回傳n(第57行)
**4.fcal函式**
```cpp=20
int fcal(){
id+=2;
int mx=cal(0),mn=mx;
while(s[id]!=')'){
id++;
int tmp=cal(0);
mx=max(mx,tmp);
mn=min(mn,tmp);
}
id++;
return mx-mn;
}
```
一開始先把id加二以跳過$"f("$(第21行)
因為f函式內至少有一個數，故將此數以cal(0)取得後同時設為最大與最小值
接下來就是不斷地將id加一、用cal(0)取得f裡的數字、與更新最大最小值
這個步驟重複到遇到「)」為止(f函式的結束)(第23~29行)
最後將id加一以跳過「)」，並回傳最大值減最小值
#### main函式
```cpp=16
signed main(){
cin>>s;
cout<<cal(0);
}
```
輸入字串後輸出cal(0)的值
其中signed跟int同義，用signed是避免被define轉成long long
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int id=0;
int getnum(){
int ans=0;
while(id<s.size()&&'0'<=s[id]&&s[id]<='9'){
ans=ans*10+s[id]-'0';
id++;
}
return ans;
}
int cal(bool cmp);
int fcal();
signed main(){
cin>>s;
cout<<cal(0);
}
int fcal(){
id+=2;
int mx=cal(0),mn=mx;
while(s[id]!=')'){
id++;
int tmp=cal(0);
mx=max(mx,tmp);
mn=min(mn,tmp);
}
id++;
return mx-mn;
}
int cal(bool cmp){
int n;
if('0'<=s[id]&&s[id]<='9')n=getnum();
else n=fcal();
if(cmp||s[id]==','||s[id]==')')return n;
while(id<s.size()){
if(s[id]=='+'){
id++;
int b=cal(1);
n+=b;
}
else if(s[id]=='-'){
id++;
int b=cal(1);
n-=b;
}
else if(s[id]=='*'){
id++;
int b=cal(0);
n*=b;
}
if(s[id]==','||s[id]==')')return n;
}
return n;
}
```
## 第四題 機器出租
### 題目敘述
https://zerojudge.tw/ShowProblem?problemid=j608
### 解套
很像是經典的排程問題，只是有不只一個機器
### 題目分析
這題如果只看前兩組測資，會發現機器的數量$K$都是一，也就是一般常見的排程問題
這時常用的貪心解是將所有時間區段按照結束時間由小到大排序，若相同再按開始時間由大到小排序，最後再從頭遍歷，遇到能執行的活動就執行
~~唬爛的~~理由是因為工作越早結束代表越能趕快做下一個所以排前面，
而同樣結束時間下時間越短的(開頭越大)越可能讓前一項工作完成，故排前面
這時我們再考慮滿分解，也就是機器數$K$大於一的情況
原本的排序方式可以照用，但需要多考慮的是要怎麼安排不同機器的使用時間
這時我們發現，若考慮我們的排序方式，在所有能用的機器當中，用「上一次結束時間最接近的」不會比較差，畢竟更早結束的搞不好能處理後面更早開始的
實作上我們用C++內建的multiset，但考慮到要找「小於」的元素只能用「大於等於」的lower_bound找等於再往前推，感覺會出事，所以把它做一下轉換
因為題目說時間最大只有$10^8$，所以用$10^8$減每個數字就變成找「大於」的，就能用upper_bound了！
這樣時間複雜度$O(NlogN+NlogK)$
(後來看別人的題解才發現可以用lower_bound再把指標往前移，多判指標是不是開頭就好，但感覺有點麻煩，我也沒想到)
### 解題流程
讀入測資$→$排序$→$一次遍歷、處理$→$輸出
### 解題過程
#### define
```cpp=2
#define F first
#define S second
```
為了少打一些字
#### 變數宣告
```cpp=4
int n,k;
vector<pair<int,int>>v;
```
n,k與題目定義一樣，v儲存各活動的開始與結束時間
#### 自定義排序
```cpp=7
bool cmp(pair<int,int>a,pair<int,int>b){
if(a.S!=b.S)return a.S<b.S;
else return a.F>b.F;
}
```
按照前述條件進行排序
#### 輸入
```cpp=12
cin>>n>>k;
v.assign(n,{0,0});
for(int i=0;i<n;i++)cin>>v[i].F;
for(int i=0;i<n;i++)cin>>v[i].S;
```
其中第13行讓v大小變成n，且每個元素都是{0,0}
#### 排序
```cpp=16
sort(v.begin(),v.end(),cmp);
```
#### 遍歷、處理
```cpp=17
int ans=0;
multiset<int>st;
for(int i=0;i<k;i++)st.insert(1e8+1);
for(auto i:v){
auto it=st.upper_bound(1e8-i.F);
if(it!=st.end()){
ans++;
st.erase(it);
st.insert(1e8-i.S);
}
}
```
一開始先在multiset放k個$10^8-(-1)$，代表尚未執行任務的機器(上一次結束時間-1)
接下來遍歷(第20～27行)，每次用$10^8$減開始時間找upper_bound，若upper_bound存在代表任務可以執行，於是把答案加一，並用新的結束時間取代舊的結束時間(第24、25行)
#### 輸出
```cpp=28
cout<<ans;
```
### 完整程式碼
```cpp=1
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
int n,k;
vector<pair<int,int>>v;
bool cmp(pair<int,int>a,pair<int,int>b){
if(a.S!=b.S)return a.S<b.S;
else return a.F>b.F;
}
int main(){
cin>>n>>k;
v.assign(n,{0,0});
for(int i=0;i<n;i++)cin>>v[i].F;
for(int i=0;i<n;i++)cin>>v[i].S;
sort(v.begin(),v.end(),cmp);
int ans=0;
multiset<int>st;
for(int i=0;i<k;i++)st.insert(1e8+1);
for(auto i:v){
auto it=st.upper_bound(1e8-i.F);
if(it!=st.end()){
ans++;
st.erase(it);
st.insert(1e8-i.S);
}
}
cout<<ans;
}
```
## 心得
這次APCS因為有事所以也沒有考，原本有點懊悔，但因為那陣子剛好在段考前，過得十分忙碌，所以後來想想沒去考或許就結果來說是比較好的
後來聽有去考的同學的說法，有的說這次「很簡單，跟送分一樣」，也有的說自己「死定了」，所以結論就是沒有結論...(可能就只是跟題目種類擅不擅長有關吧)
---
個人認為第一題的難度跟之前差不多，但第二題明顯感覺比之前簡單(除了輸出稍微複雜一點點以外沒有甚麼複雜的操作)，或許也能因此增加考試中想第三、四題的時間(我猜的)，這兩題基本上都蠻快寫出來的，也不需要甚麼特殊技巧
第三題時間主要是花在想$f$函數的處理方式，試了幾次才想到用逗點和右括弧當額外的中止條件，id的控制也花了一點時間思考。
個人還是習慣用遞迴，但聽說用stack好像可能比較有效率？(但我這題排行榜第一所以...我也不知道)
(更新：被擠下去了，但還在排行榜裡)
第四題一開始根本沒想法。
後來想了一下之後想起來$K=1$的Greedy解法，但機器多於一台還是不知道怎麼處理
後來只好去看別人的題解，知道了要找能用的機器中上一次結束時間最接近的
後來自己想到用$10^8$減活動時間來換成用upper_bound，也成功AC，但後來看別人的code才發現直接把指標往前移就好了，不過個人認為兩種做法都行
---
這次APCS讓我發現我Greedy還需要加強，畢竟只想得到以前寫過的題目的寫法。
雖然DP和Greedy某種程度上或許比較靠天分一點才能推(通)論(靈)出解法，但多練習應該能培養出解題的感覺，讓自己更快想出關鍵的步驟
而且它們都是APCS第四題很容易出的範圍，如果要拿五級分不弄懂不行
Sign in with Wallet
Connect another wallet