kindle1126
首頁
部落格
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; } ``` ---