HackMD
01/08 APCS參考題解
這份題解以簡單的語法、新手看得懂為主 >_<
pA
額外用變數紀錄最大的分數、有最大分數的時間點、嚴重錯誤的次數來完成題目
code
#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
用兩個字串，每次操作就將字串一丟進字串二，最後互換，同時用一個陣列儲存所有的操作結果
code
#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
透過 stack 去維護最近的數字和符號，並在每次插入的時候控制優先度（如果插入優先度較低的，就將前面優先度較高的處理掉）
詳細的模擬可以在這部影片看到
可以用遞迴實做，但我覺得會比較麻煩一點
code
#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;
}
python code 一行版
# 這是python的一行解，主要是透過()約束運算符號的優先級，不過似乎會有遞迴過深的問題，在zj上不可用
print(eval("(" + input().replace("(", "([(").replace(")", ")])").replace(",", "),(").replace("*", ")*(") + ")", {"f": (lambda l : max(l)-min(l))}))
pD
結合掃描線和貪心的概念，我們可以先以結束時間從小到大排序（如果相同則以開始時間由小到大排序）
每次都從左掃到右邊並且用貪心可以得知如果目前借出的機器都有重疊，則不放入，因為選擇較為前面（結束時間較小的機器）肯定較佳，並且如果有多個機器可以使用，則使用結束時間最靠近的，因為有可能後面的活動需要用到更早結束的機器，因此能省則省
因為我們需要知道每個機器的結束時間，並且是保持排序的，所以可以用 multiset 維護所有正在使用的機器的結束時間
// 這題我實在不知道怎麼用簡單的語法寫 包欠 :<
#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;
}
