2025/10/19 APCS測驗中級題解

發布日期：2025-10-19

分類：程式

## 非常不專業ww
### 想獲得更專業的題目解析，歡迎參加 [APCSS Camp](https://apcss.camp/ ) !!
---

# 第一題：[彗星撞擊](https://zerojudge.tw/ShowProblem?problemid=r488 )

## 題目說明

給定一個 R×C 的地形格子，每格初始高度為 D，並可能有恐龍存在。
接下來有 K 筆資料表示某格子有恐龍，之後有 M 次彗星撞擊事件，每次彗星撞擊事件給定一個中心點 (a, b)、撞擊邊長s與高度變化 h(原題目是d，我用h)。

* 若影響範圍內有恐龍，則清除範圍內所有恐龍；
* 若無，則將範圍內所有格子的高度減少 h。

最後輸出地形高度的最大值、最小值，以及剩餘恐龍的總數。

---

## 解題思路

1. **輸入處理**

* 讀入 R, C, D
   * 建立高度陣列 g（初始為 D）
   * 建立恐龍陣列 d（初始為 0）
   * 讀入 K 筆恐龍座標，標記在 d

2. **操作處理**

* 每次操作輸入 a, b, s, h
   * 影響範圍：

* t = (s / 2)
     * r1 = max(0, a - t)
     * r2 = min(R - 1, a + t)
     * c1 = max(0, b - t)
     * c2 = min(C - 1, b + t)
   * 若範圍內存在恐龍：清空恐龍；
   * 否則：範圍內高度減 h。

3. **輸出結果**

* 求出高度最大值、最小值。
   * 統計剩餘恐龍數。
   * 輸出三個值。

---

## 程式碼

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int R, C, D;
    cin >> R >> C >> D;
    vector<vector<int>> g(R, vector<int>(C, D));
    int K;
    cin >> K;
    vector<vector<int>> d(R, vector<int>(C, 0));
    while (K--) {
        int r, c;
        cin >> r >> c;
        d[r][c]++;
    }
    int M;
    cin >> M;
    while (M--) {
        int a, b, s, h;
        cin >> a >> b >> s >> h;
        int t = s / 2;
        int r1 = max(0, a - t), r2 = min(R - 1, a + t);
        int c1 = max(0, b - t), c2 = min(C - 1, b + t);
        bool f = 0;
        for (int i = r1; i <= r2 && !f; i++)
            for (int j = c1; j <= c2; j++)
                if (d[i][j]) {
                    f = 1;
                    break;
                }
        if (f)
            for (int i = r1; i <= r2; i++)
                for (int j = c1; j <= c2; j++)
                    d[i][j] = 0;
        else
            for (int i = r1; i <= r2; i++)
                for (int j = c1; j <= c2; j++)
                    g[i][j] -= h;
    }
    int mx = INT_MIN, mn = INT_MAX, k = 0;
    for (int i = 0; i < R; i++)
        for (int j = 0; j < C; j++) {
            mx = max(mx, g[i][j]);
            mn = min(mn, g[i][j]);
            k += d[i][j];
        }
    cout << mx << " " << mn << " " << k << endl;
    return 0;
}
```

---

# 第二題：[航空拍照圖](https://zerojudge.tw/ShowProblem?problemid=r489 )

## 題目說明

給定一個 R×C 的整數陣列 a，以及另一個 R×C 的整數序列 b。
需計算 a 在 0°、180°（若 R=C 再加上 90° 與 270°）旋轉後與 b 的對應格子相符數量，並輸出最大相符比例（取整數百分比）。

---

## 解題思路

1. **輸入處理**

* 讀入 R, C
   * 讀入陣列 a
   * 讀入陣列 b

2. **旋轉比對**

* 0°：a[i][j] == b[i][j]
   * 180°：a[R-1-i][C-1-j] == b[i][j]
   * 若 R = C：

* 90°：a[R-1-j][i] == b[i][j]
     * 270°：a[j][C-1-i] == b[i][j]

3. **輸出結果**

* 取最大相符數 m
   * 計算比例 m * 100 / (R * C)
   * 輸出結果（整數百分比）

---

## 程式碼

```cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    int r, c, m = 0, s = 0, ss = 0, sss = 0, ssss = 0;
    cin >> r >> c;
    int a[210][210], b;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> a[i][j];
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> b;
            if(a[i][j] == b) s++; // 0°
            if(a[r-1-i][c-1-j] == b) ss++; // 180°
            if(r == c){
                if(a[r-1-j][i] == b) sss++; // 90°
                if(a[j][c-1-i] == b) ssss++; // 270°
            }
        }
    }
    m = max({s, ss, sss, ssss});
    cout << m * 100 / (r * c) << '%' << endl;
    return 0;
}
```

---

# 第三題：[商品包裝地](https://zerojudge.tw/ShowProblem?problemid=r490 )

## 題目說明

給定 n 組 13 位數條碼，需驗證是否符合規則：

1. 前 12 位：

* 奇數位數字直接加總；
   * 偶數位數字乘 3 再加總。
2. 驗證碼（第 13 位）需滿足：

* (s % 10 + c) 為 0 或 10。
3. 驗證成功後，記錄前三位，計算出現次數。
4. 輸出出現次數最多的前三位及其次數。

---

## 解題思路

1. **輸入處理**

* 讀入 n
   * 逐筆讀入字串 a

2. **驗證條碼**

* 計算總和 s
   * 若驗證通過，取前三位 a.substr(0, 3) 並計數

3. **輸出結果**

* 找出出現次數最多的前三位字串與其數量

---

## 程式碼

```cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    unordered_map<string, int> mp;
    while(n--){
        string a;
        cin >> a;
        int s = 0;
        for(int i = 0; i < 12; i++){
            if(i % 2 == 0){
                s += a[i] - '0';
            } else {
                s += (a[i] - '0') * 3;
            }
        }
        int c = a[12] - '0';
        if(s % 10 + c == 0 || s % 10 + c == 10){
            string w = a.substr(0, 3);
            mp[w]++;
        }
    }
    int m = 0;
    string t;
    for(auto p : mp){
        if(p.second > m){
            t = p.first;
            m = p.second;
        }
    }
    cout << t << " " << m << endl;
    return 0;
}
```

---

2025/10/19 APCS測驗 中級題解

2025/10/19 APCS測驗中級題解