歡迎加入我的 Discord 群組與我討論程式相關的問題!

Posted on 

 by 

 in 

2022 年 6 月 APCS 題解

1. 數字遊戲

這題可以利用陣列來記錄每個數字出現的次數,並且將他們從大到小輸出出來。
也有不用陣列的做法,只是陣列會可以避免掉很多 bug ,例如重複輸出,或是比大小。
因此,這題強烈推薦使用陣列。

複雜度: O(1)

主要知識: 陣列與結構 (arrays and structures)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    vector <int> cnt(10);
    cnt[a] ++;
    cnt[b] ++;
    cnt[c] ++;
    cout << max({cnt[a], cnt[b], cnt[c]});
    for(int i = 9;i >= 1;i--) {
        if(cnt[i]) cout << ' ' << i;
    }
    cout << '\n';
}

2. 字串解碼

這題一如往常需要用到二維陣列,因為我們操作字串時要從最後往前,所以一定要存起來。
注意題目給的輸入是加密過後的字串,我們要輸出的是原本的字串。因此所有操作都要反著處理!

  • 從最後一個字串往回推
  • 每個字串都是從最後面開始判斷
    • 0 的話放在原本字串的前面
    • 1 的話放在原本字串的後面
    • 可以用 deque 實作 push_front, push_back
    • 如果是 1 的數量是奇數要重新排列 (要在 01 序列之後做) 因為我們要反著做
    • 翻轉字串時可以用到 substr 函式

其他細節的部份就請看code。

複雜度: O(nm)

主要知識: 陣列與結構 (arrays and structures)條件判斷與迴路 (conditional expressions and loop)字元 (character)字串 (string)

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

int main(){
    int n, m;
    cin >> n >> m;
    vector <string> s(n);
    for(int i = 0;i < n;i++) {
	cin >> s[i];
    }
    string t;
    cin >> t;
    for(int i = n-1;i >= 0;i--){
        int one = 0;
        for(int j = 0;j < m;j++){
            if(s[i][j] == '1') one++;
        }

   
        deque <char> dq;
        for(int j = m-1;j >= 0;j--){
	    if(s[i][j] == '0') dq.push_front(t[j]);
	    else dq.push_back(t[j]);
        }
		
        t = "";
        for(char c : dq) t += c; // 把 t 更新

        if(one % 2 == 1) { // 翻轉字串
            if(m % 2){
	        string f = t.substr(0, m/2); 
                string s = t.substr(m/2+1, m/2);
	        string mid = t.substr(m/2, 1); // 奇數要特別處理中間
	        t = s + mid + f;
	    } else {
	        string f = t.substr(0, m/2);
	        string s = t.substr(m/2, m/2);
	        t = s + f;
	    }
        }
    }
    cout << t << '\n';
}

3. 雷射測試

這題的核心概念是要利用二分搜來找到下一個鏡子的位置。如果每次依照方向一格一格的跑的話複雜度最差會到 O(ny),也就是 250000 * 30000 。這個量級會超時,因此,我們要利用二分搜在 O(log n) 的時間快速找到下一個鏡子。

我們對於每個 x, y 都開一個陣列紀錄上面有哪些鏡子。之後,我們將每個陣列排序好,就可以在模擬雷射的時候在對應的 x, y 陣列二分搜。

一些注意事項:

  • 因為題目的 y 可能是負的,然後我們不能開 index 是負的陣列,所以我們把所有的 y 座標加上 30000。
  • 這樣可以把所有 y 變成正的,也不影響鏡子間的相對位置!
  • upper_bound 可以找到第一個比他大的鏡子 (不能用 lower_bound 要不然會找到自己)
  • –lower_bound 可以找到第一個比較小的鏡子
  • 如果沒有找到的話,就可以結束了
  • 其他的部分就是轉彎的細節,這部分就是要一個一個打出來 (詳情看code)

複雜度: O(nlogn)

主要知識:排序 (sorting),搜尋 (searching),陣列與結構 (arrays and structures)

#include <bits/stdc++.h>
using namespace std;
const int mxn = 30005;
vector <int> mx[mxn], my[mxn*2];
map <pair<int,int>, int> mp;
int turn(int dir, int t){
    if(t == 0){
        if(dir == 0) return 1;
	if(dir == 1) return 0;
	if(dir == 2) return 3;
	if(dir == 3) return 2;
    } else {
	if(dir == 0) return 3;
	if(dir == 1) return 2;
	if(dir == 2) return 1;
	if(dir == 3) return 0;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        int x, y, t;
        cin >> x >> y >> t;
	y += 30000;
	mx[x].push_back(y);
	my[y].push_back(x);
	mp[{x, y}] = t;
    }
    for(int i = 0;i < mxn;i++){
	sort(mx[i].begin(), mx[i].end());
    }
    for(int i = 0;i < mxn*2;i++){
	sort(my[i].begin(), my[i].end());
    }
    int cnt = 0;
    int x = 0, y = 30000, dir = 0; // 0:¥k 1:?W 2:¥a 3:?U 
    while(true){
        if(dir == 0){
	    if(upper_bound(my[y].begin(), my[y].end(), x) == my[y].end()) break;
		x = *upper_bound(my[y].begin(), my[y].end(), x);
	} else if(dir == 1){
	    if(upper_bound(mx[x].begin(), mx[x].end(), y) == mx[x].end()) break;
		y = *upper_bound(mx[x].begin(), mx[x].end(), y);
        } else if(dir == 2){
	    if(lower_bound(my[y].begin(), my[y].end(), x) == my[y].begin()) break;
		x = *(--lower_bound(my[y].begin(), my[y].end(), x));
	} else {
	    if(lower_bound(mx[x].begin(), mx[x].end(), y) == mx[x].begin()) break;
		y = *(--lower_bound(mx[x].begin(), mx[x].end(), y));
	}
	dir = turn(dir, mp[{x, y}]);
	cnt ++;
    }
    cout << cnt << '\n';
}

4. 內積

這題我們用動態規劃的概念來實作。

我們先定義 dp[i][j] 為 a[i] 結尾 b[j] 結尾的最大內積。
接著,想想要怎麼轉移。因為選的位置要是連續的,而且a, b的長度要一樣,
所以我們可以轉移過來的狀態只有 dp[i-1][j-1],也就是前一個地方結尾的最大內積。

現在我們想要求一段連續的元素的最大和。
如果前一項大於 0 的話,會讓答案比較好的話,我們就從前一項轉移過來。反之加上前面的答案會讓這個更小的話,我們就放棄前面的答案,從這個重新開始。
所以我們可以推出轉移式

dp[i][j] = max(dp[i-1][j-1] + a[i] * b[j], a[i] * b[j]);

做完一輪之後,再把 b 陣列反轉就可以算出反轉的答案了!最後最大的 dp[i][j] 就是我們要的答案。

複雜度: O(nm)

主要知識:動態規劃 (dynamic programming)

類似題目:Maximum Subarray Sum

#include <bits/stdc++.h>
using namespace std;
int a[1005], b[1005], dp[1005][1005];
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= m;i++) cin >> b[i];
	
    int ans = INT_MIN;
    for(int i = 1;i <= n;i++){
	for(int j = 1;j <= m;j++){
	    dp[i][j] = max(dp[i-1][j-1] + a[i] * b[j], a[i] * b[j]);
		ans = max(ans, dp[i][j]);
	    }
    }
	
    reverse(b+1, b+1+m); //反轉
    memset(dp, 0, sizeof(dp));
    for(int i = 1;i <= n;i++){
	for(int j = 1;j <= m;j++){
	    dp[i][j] = max(dp[i-1][j-1] + a[i] * b[j], a[i] * b[j]);
	    ans = max(ans, dp[i][j]);
	}
    }
	
    cout << ans << '\n';
}

發表迴響

Blog at WordPress.com.

%d 位部落客按了讚: