# 01/08 APCS參考題解
這份題解以簡單的語法、新手看得懂為主 >_<
[全部的code](https://github.com/temmie-950807/code/tree/main/%E6%AF%94%E8%B3%BD/APCS/APCS%202023-01-08)
## pA
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j605)
額外用變數紀錄**最大的分數**、**有最大分數的時間點**、**嚴重錯誤的次數**來完成題目
:::spoiler code
```cpp!
#include <bits/stdc++.h>
using namespace std;
// 宣告變數
int k;
int t[10], s[10];
int max_score=-1, max_time=-1, cnt=0; // 嚴重錯誤的次數
int main(){
// 輸入所有變數
cin >> k;
for (int i=0 ; i<10 ; i++){
cin >> t[i] >> s[i];
}
// 檢查所有提交紀錄
for (int i=0 ; i<k ; i++){
if (s[i]==-1){
// 如果是嚴重錯誤的話，就將次數+1
cnt=cnt+1;
}else if (s[i]>max_score){
// 如果現在的分數比之前紀錄的高的話，就更新最大值
max_score=s[i];
max_time=t[i];
}
}
// 輸出
if (max_score-k-(2*cnt)<0){
// 如果計算的結果小於0的話就輸出總分為0
cout << 0 << " " << max_time << endl;
}else{
cout << max_score-k-(2*cnt) << " " << max_time << endl;
}
}
```
:::
## pB
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j606)
用兩個字串，每次操作就將字串一丟進字串二，最後互換，同時用一個陣列儲存所有的操作結果
:::spoiler code
```cpp!
#include <bits/stdc++.h>
using namespace std;
// declare
int n, q, k, tmp;
string s1, s2; // s1是目前的字串，s2是即將操作的字串
char arr[1000][1000]; // 用來儲存每一次操作的結果，第arr[i][j]為第i次操作後中第j個字元
int main(){
cin >> n >> q >> k >> s1;
s2=s1;
// 執行操作
for (int i=1 ; i<=q ; i++){
// 移動所有字元
for (int j=0 ; j<n ; j++){
cin >> tmp;
s2[tmp-1]=s1[j]; // 題目給的是從1開始編號，而字串的索引值是從0開始編號
}
// 紀錄所有字元
for (int j=0 ; j<n ; j++){
arr[i][j]=s2[j];
}
// 把「現在的字串」替換成「移動完的字串」
s1=s2;
}
// 輸出結果
for (int i=0 ; i<k ; i++){
for (int j=1 ; j<=q ; j++){
cout << arr[j][i]; // 由於是從上到下 從左到右輸出，i和j的位子會不同
}
}
}
```
:::
## pC
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j607)
透過 stack 去維護最近的數字和符號，並在每次插入的時候控制優先度（如果插入優先度較低的，就將前面優先度較高的處理掉）
詳細的模擬可以在[這部影片](https://youtu.be/ljsvgloMNVs)看到
可以用遞迴實做，但我覺得會比較麻煩一點
:::spoiler code
```cpp!
#include <bits/stdc++.h>
using namespace std;
// debug 工具
template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
string s; // 題目的輸入
stack<int> A; // 維護最近的數字
stack<char> B; // 維護最近的操作
// 將之前為+的所有數值計算起來，並重新丟回A裡面
void add(){
if (B.size() && B.top()=='+'){
// 如果最前面的是 + 的話，就先紀錄第一個值
int total=A.top();
A.pop();
while (B.size() && B.top()=='+'){
// 接著不斷的把所有是 + 的值都加在 total 裡面
total+=A.top();
A.pop();
B.pop();
}
// 紀錄該值
A.push(total);
}
}
// 將之前前為*的所有數值計算起來，並重新丟回A裡面
void multi(){
if (B.size() && B.top()=='*'){
int total=A.top();
A.pop();
while (B.size() && B.top()=='*'){
total*=A.top();
A.pop();
B.pop();
}
A.push(total);
}
}
// 將之前為 f() 內的數值計算出來，並重新丟回A裡面
void f(){
int mi=A.top(), ma=A.top();
A.pop();
if (B.size() && B.top()==','){
while (B.size() && B.top()==','){
mi=min(mi, A.top());
ma=max(ma, A.top());
A.pop();
B.pop();
}
}
A.push(ma-mi);
}
int main(){
// 宣告 & 初始化
int now=0; // 目前的數字總和，以儲存在字串裡找到的數字
bool flag=0; // 如果 now 裡面有儲存數字的話就計為 1，否則為 0
// 輸入
cin >> s;
// 一一解析所有字元，其中'f'字元不會被使用
for (int i=0 ; i<s.size() ; i++){
if ('0'<=s[i] && s[i]<='9'){
// 如果 s[i] 是數字，就更新 now 和 flag
now=10*now+s[i]-'0';
flag=1;
}else{
// 如果 flag 等於 1 就代表數字已經被紀錄完畢，因此丟進 A 裡面
if (flag==1){
A.push(now);
flag=0;
now=0;
}
// + 是最高優先級的符號，直接丟進 B 裡面就好
if (s[i]=='+'){
B.push('+');
}
// * 是次高優先級的符號，因此先把先前所有 + 處理完畢後再丟進去
//（也就是說前面的數字不會再有任何需要 + 的運算，可以直接和後面的數字做相乘）
if (s[i]=='*'){
add();
B.push('*');
}
// , 是用來分隔 f() 裡的所有數字，因此把先前所有的 + * 處理完畢就可以得到可以作為後續比較的數字
if (s[i]==','){
add();
multi();
B.push(',');
}
// 將 ( 紀錄，以免多個 , 被混在一起
// ex: f(1, 2, f(4, 5, 6))
// 不加上這段：不知道哪個數字在哪個區段
// A: 1 2 4 5 6
// B: , , , ,
// 加上這段：可以知道 4 5 6 是一起的
// A: 1 2 4 5 6
// B: , , ( , ,
if (s[i]=='('){
B.push('(');
}
// 求得最後沒有被處理的數字，最後求得 f() 的結果
if (s[i]==')'){
add();
multi();
f();
// 因為前面用了 ( 分隔其他符號，所以這裡要 pop 掉
B.pop();
}
}
// 你可以在這裡取消註解觀察 stack 的數值
// debug(A);
// debug(B);
}
// 求得最後沒有被處理的數字
if (flag==1){
A.push(now);
now=0;
flag=0;
}
add();
multi();
// 輸出
cout << A.top() << endl;
return 0;
}
```
:::
:::spoiler python code 一行版
```python!
# 這是python的一行解，主要是透過()約束運算符號的優先級，不過似乎會有遞迴過深的問題，在zj上不可用
print(eval("(" + input().replace("(", "([(").replace(")", ")])").replace(",", "),(").replace("*", ")*(") + ")", {"f": (lambda l : max(l)-min(l))}))
```
:::
## pD
[題目連結](https://zerojudge.tw/ShowProblem?problemid=j608)
[其實和這題一模一樣](https://cses.fi/problemset/task/1632)
結合掃描線和貪心的概念，我們可以先以結束時間從小到大排序（如果相同則以開始時間由小到大排序）
每次都從左掃到右邊並且用貪心可以得知**如果目前借出的機器都有重疊，則不放入**，因為選擇較為前面（結束時間較小的機器）肯定較佳，並且**如果有多個機器可以使用，則使用結束時間最靠近的**，因為有可能後面的活動需要用到更早結束的機器，因此能省則省
因為我們需要知道每個機器的結束時間，並且是保持排序的，所以可以用 multiset 維護所有正在使用的機器的結束時間
:::spoiler
```cpp!
// 這題我實在不知道怎麼用簡單的語法寫 包欠 :<
#include <bits/stdc++.h>
using namespace std;
template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
// 宣告
int n, k;
int l[100005], r[100005];
int ans; // 儲存
vector<pair<int, int>> v; // 每個時間段，用 <結束時間, 開始時間> 儲存
multiset<int> s;
int main(){
// 輸入
cin >> n >> k;
for (int i=0 ; i<n ; i++){
cin >> l[i];
}
for (int i=0 ; i<n ; i++){
cin >> r[i];
}
// 將每個活動的時間存進 v 裡面，並且排序
for (int i=0 ; i<n ; i++){
v.push_back(make_pair(r[i], l[i]));
}
sort(v.begin(), v.end());
// 用 multiset 維護目前借出機器的結束時間
for (int i=0 ; i<k ; i++){
s.insert(0);
}
for (int i=0 ; i<n ; i++){
auto it=s.lower_bound(v[i].second); // 搜尋開始時間
if (it==s.begin()){ // 最早的結束時間和現在的開始時間重疊，因此不能放入（放入一定更糟，必定會影響更多活動）
continue;
}
// 可以借出機器，並且是最近剛使用完的，因為影響最小（其他活動可能會需要更早結束的）
s.erase(prev(it));
s.insert(v[i].first);
ans++;
}
// 輸出
cout << ans << endl;
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet