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

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

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

題目說明：

$n$ 棟高樓，樓高為 $h_n$ ，會從某棟高樓上向右滑翔，要找到一組遞減序列，使序列長度達最長。

解題思路：

1. 開一個 vector h，並多一個元素，做邊界檢查。
2. 令這個邊界是 h 的上限最大值+1（題目的 h 是 $1 \leq h \leq 1000$ ），所以 h[n] = 1001。
3. 設兩個變數 maxLen 紀錄序列最大長度，len 紀錄目前長度。
4. 迴圈+判斷 h[i] > h[i+1]，達成條件就 len++，否則更新最大長度 maxLen = max(maxLen, len + 1)，並重置 len = 0。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector <int> h(n + 1);
    h[n] = 1001;
    int maxLen = 0, len = 0;
    for (int i = 0; i < n; i++){
        cin >> h[i];
    }
    for (int i = 0; i < n; i++){
        if (h[i] > h[i + 1]){
            len ++;
        }
        else{
            maxLen = max(maxLen, len + 1); 
            len = 0;
        }
    }
    cout << maxLen;
    return 0;
}

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

題目說明：

• 畫布為 $H \times W$，初始為 $0$。
• 每次操作定義為：
  • 起點 $(r, c)$ 。
  • 停留時間 $t$：會影響曼哈頓距離 $\leq t$ 的所有點。
  • 顏色值 $x$：將影響區塊累加顏色值。

曼哈頓距離：

對任意兩點 $(x_1, y_1)$ 和 $(x_2, y_2)$，曼哈頓距離為 $|x_1 - x_2| + |y_1 - y_2|$ 。

解題思路：

1. 初始化一個二維 vector canvas[H][W] 為 $0$ 。

2. 對於每次操作 $(r, c, t, x)$ ：

   • 遍歷整個畫布的每個座標 $(i, j)$
   • 計算曼哈頓距離：$|i - r| + |j - c|$
   • 若距離 $\leq t$，則將 canvas[i][j] += x。

這題可以用 BFS 優化，但畢竟還是第二題，大概 APCS 也不想要這麼狠心，所以這測資範圍直接暴力解是可 AC 的。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int H, W, N;
    cin >> H >> W >> N;

    vector<vector<int>> canvas(H, vector<int>(W, 0));

    for (int i = 0; i < N; ++i) {
        int r, c, t, x;
        cin >> r >> c >> t >> x; // 讀入本次操作的座標 (r, c)、停留時間 t、顏色值 x

        // 遍歷畫布上的所有位置
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                // 計算此位置與操作點的曼哈頓距離
                int d = abs(i - r) + abs(j - c);
                
                // 若距離 <= t，代表這格會被影響，加上顏色值 x
                if (d <= t) {
                    canvas[i][j] += x;
                }
            }
        }
    }

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cout << canvas[i][j];
            if (j < W - 1) cout << " ";
        }
        cout << "\n";
    }

    return 0;
}