APCS 2025/10 解題紀錄(C++)

2025 年 10 月 APCS 檢定中級三題完整解析:彗星撞擊、航空拍照圖、商品包裝地,每題附解題思路與 C++ 程式碼。

發布
字數
1,296
閱讀
約 3 分鐘
瀏覽
1,551
本頁目錄
  1. 中級
  2. 彗星撞擊
  3. 航空拍照圖
  4. 商品包裝地

中級

彗星撞擊

題目連結

思路

模擬並逐格更新。初始化 v 為大小 n×m、每格值為 x,並用 have 標記先給定的目標格。對每一個操作(程式中第二個 k 讀入的那批查詢,參數為 a,b,s,d),計算正方形區域

i∈[a−s−12,a+s−12],j∈[b−s−12,b+s−12], i\in\left[a-\frac{s-1}{2},a+\frac{s-1}{2}\right],\qquad j\in\left[b-\frac{s-1}{2},b+\frac{s-1}{2}\right],

(程式以 0-based 索引,遇到超出邊界的 (i,j)(i,j) 則跳過)。對這個區域做一次掃描:若存在任一格 have[i][j] == 1,則將該區域內所有 have[i][j] 設為 0(表示被移除);否則對區域內每格執行 v[i][j] -= d(扣除耐久)。此策略嚴格按照題意的「若區域內有目標則移除,否則造成傷害」執行,故最後統計最大值 mx = max(v[i][j])、最小值 mn = min(v[i][j]) 與剩餘目標數 cnt = sum(have[i][j]) 能正確反映最終狀態。

時間/空間複雜度(令第二個輸入的查詢數為 QQ,單次查詢最大正方形邊長為 smax⁡s_{\max}:

初始化與最後統計=O(n⋅m),每次查詢掃描=O(min⁡(smax⁡2,n⋅m)), \text{初始化與最後統計} = O(n\cdot m),\qquad \text{每次查詢掃描} = O(\min(s_{\max}^2,n\cdot m)),

因此總時間複雜度為

O(nm+Q⋅smax⁡2). O\big(nm + Q\cdot s_{\max}^2\big).

空間複雜度為

O(n⋅m) O(n\cdot m)

程式碼

C++
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
	int n, m, x;
	cin >> n >> m >> x;
	vector<vector<int>> v(n, vector<int>(m, x));
	vector<vector<int>> have(n, vector<int>(m));
	int k;
	cin >> k;
	while (k--) {
		int a, b;
		cin >> a >> b;
		have[a][b]++;
	}
	cin >> k;
	while (k--) {
		int a, b, s, d;
		cin >> a >> b >> s >> d;
		bool flag = 0;
		for (int i = a - (s - 1) / 2;i <= a + (s - 1) / 2;i++) {
			for (int j = b - (s - 1) / 2;j <= b + (s - 1) / 2;j++) {
				if (i < 0 or i >= n or j < 0 or j >= m) continue;
				if (have[i][j]) {
					have[i][j] = 0;
					flag = 1;
				}
			}
		}
		if (!flag) {
			for (int i = a - (s - 1) / 2;i <= a + (s - 1) / 2;i++) {
				for (int j = b - (s - 1) / 2;j <= b + (s - 1) / 2;j++) {
					if (i < 0 or i >= n or j < 0 or j >= m) continue;
					v[i][j] -= d;
				}
			}
		}
	}
	int mx = 0, mn = INF, cnt = 0;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cnt += have[i][j];
			mx = max(mx, v[i][j]);
			mn = min(mn, v[i][j]);
		}
	}
	cout << mx << ' ' << mn << ' ' << cnt;
}

航空拍照圖

題目連結

思路

以「對矩陣 (a) 做 90° 旋轉並比對」的思路。定義旋轉函數 (f)(將 (a) 順時針旋轉 90°):

f(a)i,j=an−1−j,i, f(a)_{i,j} = a_{n-1-j,i},

其中原矩陣 (a) 的大小為 (n×m)(n\times m),則 (f(a)) 的大小為 (m×n)(m\times n)。演算法依序對 (k=0,1,2,3) 做 90° 旋轉(即反覆套用 (f));對於每個旋轉後的矩陣 (a'),若其大小與目標矩陣 (b) 相同,則計算重合且值相等的格子數:

now=∑i=0n−1∑j=0m−11(ai,j′=bi,j), \text{now} = \sum_{i=0}^{n-1}\sum_{j=0}^{m-1} \mathbf{1}\big(a'_{i,j}=b_{i,j}\big),

維護最大重合數 s=max⁡(s,now)s=\max(s,\text{now})。最終輸出百分比為整數(向下取整):

ans=⌊100⋅sn⋅m⌋ \text{ans} = \left\lfloor\frac{100\cdot s}{n\cdot m}\right\rfloor%\ .

時間 / 空間複雜度(以原始 n×mn\times m 為基準):

  • 每次旋轉 (f) 建構新矩陣需 O(nm)O(nm),每次相等性檢查需 O(nm)O(nm)。總共最多做 4 次,故時間複雜度為
O(4⋅n⋅m)=O(nm). O(4\cdot n\cdot m)=O(nm).
  • 額外空間用於儲存旋轉後的矩陣與原矩陣,空間複雜度為
O(nm). O(nm).

程式碼

C++
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
vector<vector<int>> f(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	vector<vector<int>> t(m, vector<int>(n));
	for (int i = 0;i < m;i++) {
		for (int j = 0;j < n;j++) {
			t[i][j] = a[n - 1 - j][i];
		}
	}
	return t;
}
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m)), b(n, vector<int>(m));
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> b[i][j];
		}
	}
	int s = 0;
	for (int k = 0;k < 4;k++) {
		if (a.size() == b.size() and a[0].size() == b[0].size()) {
			int now = 0;
			for (int i = 0;i < n;i++) {
				for (int j = 0;j < m;j++) {
					if (a[i][j] == b[i][j]) now++;
				}
			}
			s = max(s, now);
		}
		a = f(a);
	}
	cout << (100 * s) / (n * m) << '%';
}

商品包裝地

題目連結

思路

逐筆讀入長度為 13 的字串 x,將前 12 位分成「奇數位」與「偶數位」兩組(程式以 0-based 索引,條件為 (i+1)%2 判斷奇偶),計算

s1=∑0≤i≤11 i≡0(mod2)(x[i]−′0′),s2=∑0≤i≤11 i≡1(mod2)(x[i]−′0′). s_1=\sum_{\substack{0\le i\le 11\ i\equiv 0\pmod{2}}}\big(x[i]-'0'\big),\qquad s_2=\sum_{\substack{0\le i\le 11\ i\equiv 1\pmod{2}}}\big(x[i]-'0'\big).

將第 13 位記作 d13=x[12]−′0′d_{13}=x[12]-'0'。題目程式中以

k=(s1+3s2) mod 10+d13 k=(s_1+3s_2)\bmod 10 + d_{13}

判定合法條件 if (k == 0 or k == 10),其數學意義等價於

(s1+3s2+d13)≡0(mod10), (s_1+3s_2+d_{13})\equiv 0\pmod{10},

也就是「前 12 位按奇偶位加權求和,再加上第 13 位,模 10 等於 0」時視為一筆合法資料(符合 ISBN/檢查碼類似的檢核邏輯)。當該筆合法時,把該字串的前三個字元 x.substr(0,3) 當作 key 在 map<string,int> cnt 中計數,並更新 ans = max(ans, cnt[prefix]) 作為目前觀察到的最大頻次。讀完所有輸入後,按 map 的鍵序(由小到大)掃描,遇到 y == ans 即輸出該 prefix 與 ans(程式以第一個符合者輸出,對應於字典序最小的前綴)。

時間 / 空間複雜度:

  • 每筆字串固定做 (12) 次位元相加與常數次數的字串切片/ map 操作:單筆時間為 O(log⁡M)O(\log M)(M 為目前不同前綴數,因 map 為平衡樹),整體時間為
O(nlog⁡M)⊆O(nlog⁡n). O\big(n\log M\big)\subseteq O(n\log n).
  • 空間用於 map 儲存至多 (M≤n)(M\le n) 個不同前綴,為 O(M)O(M)。

程式碼

C++
#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const long long INF = numeric_limits<int>::max();
int main() {
	int n;
	cin >> n;
	map<string, int> cnt;
	int ans = 0;
	while (n--) {
		string x;
		cin >> x;
		int s1 = 0, s2 = 0;
		for (int i = 0;i < 12;i++) {
			if ((i + 1) % 2) s1 += x[i] - '0';
			else s2 += x[i] - '0';
		}
		int k = (s1 + 3 * s2) % 10 + (x[12] - '0');
		if (k == 0 or k == 10) {
			cnt[x.substr(0, 3)]++;
			ans = max(ans, cnt[x.substr(0, 3)]);
		}
	}
	for (auto [x, y] : cnt) {
		if (y == ans) {
			cout << x << ' ' << ans;
			return 0;
		}
	}
}
最後更新 2025.10.19

Comments

留言

支援 Markdown、程式碼高亮(```cpp)與 LaTeX($E=mc^2$),Ctrl + Enter 送出。頭像會用你的 e-mail 去 Gravatar 找,e-mail 本身不會公開。

載入留言中…

Esc

輸入關鍵字,例如「線段樹」「Makefile」「面試」。

↑ ↓ 選擇Enter 開啟