# APCS 2023/1/8 實作題 解題報告
## 2023/1/31 更
![](https://i.imgur.com/LCUjNrT.png)
兩眼一黑 我的年份竟然打錯了 :skull:
## 第一題
![](https://i.imgur.com/WMsd1zF.png)
### 思路
直接輸入 算一算就好了
### Code
:::spoiler **點我看Code**
```c++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int num;
cin >> num;
int max_score = -99, max_time = 0, bad_count = 0;
int score;
int input_score, input_time;
for (int i = 0; i < num; i++)
{
cin >> input_time >> input_score;
if(input_score > max_score)
{
max_time = input_time;
max_score = input_score;
}
if(input_score == -1)
{
bad_count++;
}
}
score = max_score - num - bad_count * 2;
if(score < 0)
score = 0;
cout << score << " " << max_time;
}
```
:::
## 第二題
![](https://i.imgur.com/uhOGjnx.png)
### 思路
直接輸入 思考一下對應關係
注意輸出是要輸出哪一行,for i {for j} 輸出要array[j][i]
就好了
### Code
:::spoiler **點我看Code**
```c++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int string_len, output_len, output_line;
cin >> string_len >> output_len >> output_line;
vector<string> str(output_len + 1, string(string_len, ' '));
cin >> str[0];
int index;
for (int i = 1; i <= output_len; i++)
{
for (int j = 0; j < string_len; j++)
{
cin >> index;
str[i][index - 1] = str[i - 1][j]; // 將上個字串 j 放到,新的字串 index(輸入) 的位置
}
}
for (int i = 0; i < output_line; i++)
{
for (int j = 1; j <= output_len; j++) // str[0]原始字串不用輸出,注意輸出的排列方向
cout << str[j][i];
cout << "\n";
}
}
```
:::
## 第三題
![](https://i.imgur.com/BFHntvB.png)
我太爛了,現場沒f()來不及寫 :(
### 思路
我用遞迴解,定義兩個函數:
#### parse(string s)
用來解析字串,決定要先用哪個運算符號,將符號左右的數字做 parse(左字串) * or + parse(右字串)
或將判斷字串並將其丟進f(整個字串)運算,或是沒有運算符號則回傳數字。
#### f(string s)
功能如題目中所述,最大-最小,解析`()`及`,`,其中每個參數就丟進去parse()。
### 舉例
input: `12+f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2))*2`
`parse( 12+f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2))*2 )`
`parse( 12+f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2)) ) * parse( 2 )`
`parse( parse( 12 ) + parse( f(13,2+f(8,1+2*3),1+1*f(20,4)*f(2)) ) ) * parse( 2 )`
```
parse( parse( 12 )
+ parse( f( parse( 13 ) ,
parse( 2+f(8,1+2*3) ) ,
parse( 1+1*f(20,4)*f(2))
)
)
) * parse( 2 )
```
```
parse( parse( 12 )
+ parse( f( parse( 13 ) ,
parse( parse( 2 )
+ parse ( f(8,1+2*3) ) ),
parse( parse( 1+1 )
* parse( f(20,4)*f(2)) )
)
)
) * parse( 2 )
```
... 然後繼續套 我懶得寫了 HackMD排版有點困難
### Code
:::spoiler **點我看Code**
```c++
#include <bits/stdc++.h>
using namespace std;
// declaring some function
uint64_t f(const string &s);
uint64_t parse(const string &s);
uint64_t to_ll(const string &s);
// 有種東西叫 std::stoll 可以做一樣的事情
// 考試時code::blocks有InteliSense但幾乎殘廢,我也沒有背太多語法,就手刻一個
uint64_t to_ll(const string &s) // convert string to long long
{
uint64_t out = 0;
for (int i = 0; i < (int)s.size(); i++)
{
out += (s[s.size() - 1 - i] - '0') * pow(10, i);
}
return out;
}
uint64_t parse(const string &s)
{
int type = 0, prev_type = 0;
int index = -1;
int layer;
int len = (int)s.size();
for (int i = 0; i < len; i++)
{
if (s[i] == '*')
type = 3;
else if (s[i] == '+')
type = 2;
else if (s[i] == '(') // f(
{
type = 1;
layer = 0;
for (; i < len; i++) // 1. 解析嵌套的括號 如: ( (左右的括號跳過) ) ,以跳過f()中的+以及*,
{
if (s[i] == '(')
layer++; // starting from 1 here
else if (s[i] == ')')
layer--;
if (layer == 0)
break;
}
}
if (type > prev_type) // 找到的運算符號 優先級更高
{
prev_type = type;
index = i;
}
}
if (prev_type == 0) // 如果沒有運算符號,回傳數字
return to_ll(s);
else if (prev_type == 3) // 切字串,分別計算運算符號前後的兩個字串
return parse(s.substr(0, index)) * parse(s.substr(index + 1));
else if (prev_type == 2)
return parse(s.substr(0, index)) + parse(s.substr(index + 1));
else if (prev_type == 1)
return f(s); // 把整個字串丟給f()處理 這邊字串只會出現 "f(1+2, 3)" 之類的,不用再切
else
return 99999999;
}
uint64_t f(const string &s)
{
uint64_t max_num = 0, min_num = INT64_MAX -1, num;
int index_l = -1, index_r = 1, len = (int)s.size();
int layer = 0;
for (int i = 2; i < len; i++) // 從f( 也就是第3個字元開始。
{
if ((s[i] == ',' || s[i] == ')') && layer == 0) // 對每個以,分隔的參數做運算,取最大最小值
{
index_l = index_r + 1;
index_r = i;
num = parse(s.substr(index_l, index_r - index_l));
max_num = max(max_num, num);
min_num = min(min_num, num);
}
if (s[i] == '(') // 解析嵌套的括號 (())
layer++;
else if (s[i] == ')' && layer != 0)
layer--;
}
return max_num - min_num;
}
int main()
{
string in;
cin >> in;
cout << parse(in);
}
```
:::
### 考試時原本的想法
用stack解,**速度應該會更快**,而且不會有遞迴深度過深的問題。
但我當時沒有想到照正確順序push進stack的方法,就用了遞迴,對我來說比較好實現。
~~之後再來動腦~~
## 第四題
![](https://i.imgur.com/64d7nNW.png)
### 思路
* Greedy
* 將event按照結束時間排序。由小到大。如果結束時間相同,則按照開始時間排序。由小到大。
* 對每一筆event判斷,將event安排給前一個結束時間最大的machine
* 具體上為什麼,可以用測試資料2畫時間線圖(如下圖),就能理解為什麼這樣排。
* 這是我試過幾乎每一種Greedy的方式+~~犧牲一張數學考卷成績以獲得思考~~得出的結論
![](https://i.imgur.com/xcZK6OG.png)
### Code
* format是c++20的東西 拿來debug用的 不用理他
:::spoiler **點我看Code**
```c++
// #define FMT_HEADER_ONLY
// #include <fmt/include/fmt/core.h>
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int num_event, num_machine;
cin >> num_event >> num_machine;
vector<pair<int, int>> event(num_event); // start, end
for (int i = 0; i < num_event; i++)
cin >> event[i].first;
for (int i = 0; i < num_event; i++)
cin >> event[i].second;
sort(event.begin(), event.end(), // sort by end time first, if same sort by start time (small -> large)
[](pair<int, int> a, pair<int, int> b) -> bool
{ if(a.second == b.second) return a.first < b.first;
else return a.second < b.second; });
// for (int i = 0; i < num_event; i++)
// fmt::print("{}: {}, {}\n", i, event[i].first, event[i].second);
int ans = 0, which_machine_max = -10; // index of machine
vector<int> machine_busy(num_machine, -1);
for (int i = 0; i < num_event; i++) // 掃過每個event
{
for (int j = 0; j < num_machine; j++)
{
if (machine_busy[j] < event[i].first && which_machine_max == -10) // if機器可用且沒有其他數字。如果放到下面,machine_busy[which_machine_max] 會超過範圍。
which_machine_max = j; // 存index
else if (machine_busy[j] < event[i].first && machine_busy[j] >= machine_busy[which_machine_max]) // if機器可用且最大
which_machine_max = j; // 存index
}
// fmt::print("\nwhich_machine_max: {}\nmachine busy: {}\nevent: {}\nans: {}\n", which_machine_max, fmt::join(machine_busy, ", "), fmt::join(event[i], ", "), ans);
if (which_machine_max != -10)
{
machine_busy[which_machine_max] = event[i].second;
ans++;
which_machine_max = -10;
}
}
cout << ans << endl;
}
```
:::
---
## 後記
### APCS初體驗
這是我第一次考APCS,之前只有在ZJ上刷了幾題。~~資料結構跟演算法完全沒學,只看過資訊之芽的一點講義,我連BFS怎麼跑都沒有實作過。~~
選擇題部分,我覺得就是在考ability to read bad written code with bugs and without comment,寫起來很令人煩躁且無聊。好幾題都要腦中憑空模擬,或者去猜他背後的數學式子,感覺在寫數學考卷。
上機實作就是熟練度跟速度,我覺得第三題不難但很花時間(與ZJ上的考古題相比)。第四題當時我有想到Greedy,但我覺得總沒那麼簡單,因為考前看了資芽的Greedy,寫說"你覺得Greedy是最佳解很可能只是特例",我就沒寫,專心弄第三題(結果也沒寫完 :( )。
另外 幾個疑問
* 為什麼不能Alt + Tab
* 我都按Alt + Tab
* 隔幾秒發現不能用,只好用滑鼠切換視窗
* 非常影響心情
* 為什麼Terminal沒辦法貼上
* 測資要手打
* 非常影響心情
* 為什麼IDE那麼難用
* Eclipse我根本看不懂怎麼用
* Code::blocks的intellisense大概只有打i會出現int,其他時候都不能用 ~~建議改名idiotsense~~
* Code::blocks沒辦法用GDB Debugger
* 沒有深色模式,我的眼睛:![](https://i.imgur.com/qm5g29h.png)
* 也許是平常VScode/VS2022太好用了,沒intellisense+auto format就要手打/手動排版很多東西,變數名稱不能取太長。
* 鍵盤滑鼠
* 沒有習慣的機械鍵盤跟滑鼠,寫Code的效率低了許多。
### 考完試後一天
學長跟我抱怨他一直95%,為什麼第三題會少五分啦QQ (最後一筆Wrong answer: 153)
我們測了很多資料,都覺得沒問題
後來直接問出題者
看來出題者也累了ww (仍感謝有人花自己的時間搬運題目、生測資)
**~~還我消失的五個小時~~**
![](https://i.imgur.com/aFAMWeb.png)
rejudge中 各位95%可以回去看看
![](https://i.imgur.com/yd0dvYW.png)