【APCS】2023年1月實作題 C++ 解題筆記（前兩題）

此筆記僅供個人學習用途，內容僅供參考。

---

1. https://zerojudge.tw/ShowProblem?problemid=j605

題目說明：

有 $K$ 個提交紀錄，第 $i$ 個提交紀錄有兩整數 $t_i, s_i$ ，分別為上傳時間跟提交分數，若第 $i$ 次的提交結果為嚴重錯誤，則 $s_i = -1$ 。

計算總分公式：提交紀錄最高分 $-$ 總提交次數 $-$ 總嚴重次數 $\times 2$。

若總分算出來 $< 0$ ，則計為 $0$ 。

輸出一行，總分和第一次最高分的時間點。

解題思路：

1. 宣告兩變數 ans, sum_s，分別用來計算總分跟總嚴重錯誤次數
2. 輸入的時候就可以先判斷是否有 s[i] == -1 的情形。
3. max_element(s.begin(), s.end()); 計算值最大的元素，但記得這回傳結果會是迭代器，要加上 * 解參考運算子（Dereference）。
4. 用 find(s.begin(), s.end(), max_score); 跟 distance 去算第一次出現最高分的 index。
5. 最後就套題目給的公式去解，還有固定的輸出格式。

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    int K;
    cin >> K;
    
    vector <int> t(K);
    vector <int> s(K);
    
    int ans = 0; // 計算總分
    int sum_s = 0; // 總嚴重錯誤次數
    
    for (int i = 0; i < K; i++){
        cin >> t[i] >> s[i];
        if (s[i] == -1) sum_s++;
    }
    
    int max_score = *max_element(s.begin(), s.end()); // 找提交紀錄最高分
    
    // 以下兩行為尋找第一次最高分的時間點 index
    auto it = find(s.begin(), s.end(), max_score);
    int index = distance(s.begin(), it);
    
    ans = max_score - K - sum_s * 2;
    
    // 輸出記得不要只寫 index, 題目要求的是最高分的提交時間 t[index]
    cout << (ans > 0 ? ans : 0) << " " << t[index];
    // 三元運算子省掉 if else
    
    return 0;
}

---

2. https://zerojudge.tw/ShowProblem?problemid=j606

題目說明：

有個初始字串 $S$ ，長度為 $K$ ，每字元皆為小寫的英文字母。

接下來 $Q$ 次修改，會給 $Q$ 行 $1 \sim K$ 數字，這些數字可以使 $S$ 重新排列，這些數字都是以 $1$ 為起始點的 index。

如： "abac" ， $P = [4, 1, 3, 2]$ ，可得到新字串 "bcaa"。

輸出這樣操作完後字串的第 $1 \sim R$ 個字元，並輸出 $R$ 行。

如範例輸入 1：

5 4 1
abcde
2 1 3 5 4
5 1 2 4 3
4 1 2 3 5
3 1 4 5 2

範例輸出 1：

bacd

bacd 是從這四次的新字串中，都取每個新字串的第一個字元出來的。

解題思路：

1. 用 C++ 內建 string，以 getline 輸入，記得前面要加上 cin.ignore()，因為前面有 K, Q, R 的 cin 輸入。
2. vector <string> pS(Q) 表示每次做排列操作的字串，有 $Q$ 個。
3. 雙層 for 迴圈中，外層做一個 temp string 讓他先 $= S$ 。
   • 再設一個 array 叫 int P[K];，也是一個 temp，用來暫時存數字排列的陣列。
   • 內層迴圈輸入 P[j];，並同時做排列操作 new_S[P[j] - 1] = S[j];。記得 P[j]-1 因為題目是以 1 為起始的索引。
   • 結束後又回到外層迴圈，更新 S = new_S，並將操作完的字串加入 pS。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int K, Q, R;
    cin >> K >> Q >> R;
    
    cin.ignore();
    
    string S;
    getline(cin, S);
    
    vector <string> pS(Q);
    
    for (int i = 0; i < Q; i++){
        
        string new_S = S;
        int P[K];
        
        for (int j = 0; j < K; j++){
            cin >> P[j];
            new_S[P[j] - 1] = S[j];
        }
        
        S = new_S;
        pS[i] = new_S;
    }
    
    for (int i = 0; i < R; i++){
        string ans;
        for (int j = 0; j < Q; j++){
            ans += pS[j][i];
        }
        cout << ans << '\n';
    }
    return 0;
}