APCS

中級

彗星撞擊

題目連結

思路

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

$$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)$ 則跳過）。對這個區域做一次掃描：若存在任一格 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]) 能正確反映最終狀態。

時間/空間複雜度（令第二個輸入的查詢數為 $Q$，單次查詢最大正方形邊長為 $s_{\max}$：

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

因此總時間複雜度為

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

空間複雜度為

$$O(n\cdot m) $$

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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} = a_{n-1-j,i}, $$

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

$$\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,\text{now})$。最終輸出百分比為整數（向下取整）：

$$\text{ans} = \left\lfloor\frac{100\cdot s}{n\cdot m}\right\rfloor%\ . $$

時間 / 空間複雜度（以原始 $n\times m$ 為基準）：

  • 每次旋轉 (f) 建構新矩陣需 $O(nm)$，每次相等性檢查需 $O(nm)$。總共最多做 4 次，故時間複雜度為

$$O(4\cdot n\cdot m)=O(nm). $$

  • 額外空間用於儲存旋轉後的矩陣與原矩陣，空間複雜度為

$$O(nm). $$

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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 判斷奇偶），計算

$$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 位記作 $d_{13}=x[12]-'0'$。題目程式中以

$$k=(s_1+3s_2)\bmod 10 + d_{13} $$

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

$$(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)$（M 為目前不同前綴數，因 map 為平衡樹），整體時間為

$$O\big(n\log M\big)\subseteq O(n\log n). $$

  • 空間用於 map 儲存至多 $(M\le n)$ 個不同前綴，為 $O(M)$。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
		}
	}
}

說些什麼吧！

waline