---
# System prepended metadata

title: 367-26蔡尚融高二上自主學習-APCS精進計畫

---

# 367-26蔡尚融高二上自主學習-APCS精進計畫
本自主學習計畫透過研究APCS程式能力檢定實作考古題，增加對APCS題型的熟悉度。針對歷屆實作題進行程式碼編寫，並且附註一點題目與程式碼的解釋，讓自己能夠更加了解如何有效率的解讀題目，知道讓程式碼更高效的方法。希望藉由這些練習使我在之後的APCS檢定獲得比上一次更高的成績。
## 2023年1月第2題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=j606
![image](https://hackmd.io/_uploads/rJWvN2NL1x.png)
![image](https://hackmd.io/_uploads/BkfO43EIJl.png)
:::
:::spoiler 解題思路

:::
:::spoiler 程式碼
```cpp=

```
:::
## 2023年6月第2題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=k732
![image](https://hackmd.io/_uploads/rk1yLakNJx.png)
![image](https://hackmd.io/_uploads/SkokU61Vkg.png)
:::
:::spoiler 解題思路
每次直接從頭到尾遍歷找出特殊位置，但因為輸出要先有特殊位置數再有每點座標，所以在過程中記錄數量並持續將座標存入vector中。
:::
:::spoiler 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
	short n, m, ans = 0;    //ans記錄特殊位置數
	vector<short> v;    //v記錄特殊位置座標
	cin >> n >> m;
	short a[n][m];
	for(short i = 0; i < n; i++){
		for(short j = 0; j < m; j++){
			cin >> a[i][j];    //輸入整個矩陣
		}
	}
	for(short i = 0; i < n; i++){
		for(short j = 0; j < m; j++){
			short sum = 0;
			for(short k = 0; k < n; k++){
				for(short l = 0; l < m; l++){
					if(abs(i - k) + abs(j - l) <= a[i][j]) sum += a[k][l];    //曼哈頓距離在a[i][j]內則計入總和
				}
			}
			if(sum % 10 == a[i][j]){    //若總和%10恰為a[i][j]
				ans++;    //特殊位置數+1
				v.push_back(i);
				v.push_back(j);    //將特殊位置座標推入，此處即已按照字典序排列
			}
		}
	}
	cout << ans << '\n';    //輸出特殊位置數
	ans *= 2;
	while(ans--){
		cout << v[v.size() - ans - 1];    //輸出特殊位置座標
		if(ans % 2) cout << ' ';    //若輸入完的是v的第奇數個數(即x座標)則空一格
		else cout << '\n';    //若輸入完的是v的第偶數個數(即y座標)則換行
	}
}
```
:::
## 2023年10月第2題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=m371
![image](https://hackmd.io/_uploads/rJcwYEklkl.png)
![image](https://hackmd.io/_uploads/Bk0OYEJxyx.png)
:::
:::spoiler 解題思路
先遍歷所有橫列，再遍歷所有直行找出可以消除的元素，重複以上動作直到出現遍歷完整個表格都沒有元素可以消除的情況，即能夠完成得分計算。因每種數字恰好出現兩次，所以不會有改變消除順序而導致得分變少的狀況，可以直接遍歷。
:::
:::spoiler 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, m, s = 0;
    cin >> n >> m;
    int a[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];    //輸入整個表格
        }
    }
    bool b = 0;    //b用以檢驗每次的遍歷是否有得分
    do{
        b = 0;
        for(int i = 0; i < n; i++){    //檢查每一橫列是否能夠得分
            for(int j = 0; j < m - 1; j++){
                if(a[i][j] != -1){    //當某一格不為-1代表未配對過，由此尋找配對
                	int l = j;
                    for(; l++ < m - 2;){
                        if(a[i][l] != -1) break;    //跳過已配對過的格子直到出現未配對過者
                    }
                    if(a[i][l] == a[i][j]){    //若找到配對
                        s += a[i][j];
                        a[i][j] = -1;
                        a[i][l] = -1;
                        b = 1;
                    }    //增加得分並將兩格設為-1代表已配對過，將b設為1代表本次遍歷有得分
                }
            }
        }
        for(int j = 0; j < m; j++){    //檢查每一直排是否能夠得分
            for(int i = 0; i < n - 1; i++){
                if(a[i][j] != -1){    //當某一格不為-1代表未配對過，由此尋找配對
                	int l = i;
                    for(; l++ < n - 2;){
                        if(a[l][j] != -1) break;    //跳過已配對過的格子直到出現未配對過者
                    }
                    if(a[l][j] == a[i][j]){    //若找到配對
                        s += a[i][j];
                        a[i][j] = -1;
                        a[l][j] = -1;
                        b = 1;
                    }    //增加得分並將兩格設為-1代表已配對過，將b設為1代表本次遍歷有得分
                }
            }
        }
    }while(b);    //一次遍歷中有得分時b為1，繼續遍歷，b為0則代表找完，結束遍歷
    cout << s;
	return 0;
}
```
:::
## 2023年10月第4題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=m373
![image](https://hackmd.io/_uploads/rJ1qe-tVkl.png)
![image](https://hackmd.io/_uploads/r1u3gbKVkx.png)
:::
:::spoiler 解題思路
先思考 k = 0 (即一般最大區間和) 的解法，再延伸至 k > 0。
### ● k = 0 解法 (40%)
最大區間和有多種解法，此處使用滾動式調整，不開陣列，能節省記憶體。先將最大區間和初始化為0(之後若未找到正的區間和則答案為0，即不取任何一項)。輸入第i項之後檢查第i-1項結尾最大區間和，若第i-1項結尾最大區間和小於0，表示第i項結尾最大區間和即為第i項，反之，第i項結尾最大區間和為第i-1項結尾最大區間和加第i項。每次檢查第i項結尾最大區間和是否大於先前找到的最大區間和，若是則更新最大區間和，最後更新的值即為所求。
### ● k > 0 解法 (100%)

:::
:::spoiler 程式碼
### ● k = 0 解法 (40%)
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, k, val, ps = 0, ans = 0;
    cin >> n >> k >> val;
	for(int i = 1; i < n; i++){
		cin >> val;
		if (ps < 0){
			ps = val;
		}else{
			ps += val;
		}
    	ans = max(ans, ps);
	}
	cout << ans;
}
```
### ● k > 0 解法 (100%)
```cpp=
#include<bits/stdc++.h>
using namespace std;
int val[150000], dp[150000][21];
int main(){
	int n, k, ans = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> val[i];
    dp[0][0] = val[0];
    int t = max(val[0], 0);
    for(int j = 1; j <= k; j++) dp[0][j] = t;
    for(int i = 1; i < n; i++){
    	dp[i][0] = max(dp[i - 1][0], 0) + val[i];
	}
	for(int i = 1; i < n; i++){
		for(int j = 1; j <= k; j++){
			dp[i][j] = max(dp[i - 1][j] + val[i], dp[i - 1][j - 1]);
		}
	}
	for(int i = 0; i < n; i++){
		ans = max(ans, dp[i][k]);
	}
	cout << ans;
}
```
:::
## 2024年1月第2題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=m932
![image](https://hackmd.io/_uploads/B1cVpTD20.png)
![image](https://hackmd.io/_uploads/HyVjT6vnA.png)
:::
:::spoiler 解題思路
題目求的是在以六邊形構成的地圖上記錄蜜蜂的行進路徑，但是六邊形的地圖難以用程式直觀地設計，所以將每一列都往最左邊靠，構成上下對齊的四邊形地圖，如此就可以直觀使用二維陣列儲存。
:::
:::spoiler 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
    int m, n, k, c = 0;	//c為經過字元的種類數
    cin >> m >> n >> k;
    char a[m][n], b[k], d[k];    //a儲存地圖，b儲存行進方向，d儲存經過的字元
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];    //輸入地圖上所有字母
        }
    }
    int x = m - 1, y = 0;	//儲存蜜蜂經過的位置(x為上下，y為左右)，設定初始位置(左下角)
    for(int i = 0; i < k; i++){
    	cin >> b[i];    //輸入每步移動方向
        switch (b[i]){	//將每一種六角形的移動路徑簡化為上下左右的形式
        	case '0':
        		if(x) x--;
        		break;
        	case '1':
        		if(y < n - 1) y++;
        		break;
        	case '2':
        		if(x < m - 1 && y < n - 1){
        		    x++;
        		    y++;
			}
        		break;
        	case '3':
        		if(x < m - 1) x++;
        		break;
        	case '4':
        		if(y) y--;
        		break;
        	case '5':
        		if(x && y){
        		    x--;
        		    y--;
			}
        		break;
		}
		cout << a[x][y];	//輸出這步經過的字元
		d[i] = a[x][y];	//儲存這步經過的字元，以便稍後做搜尋
		char *p = find(d, d + i, a[x][y]);	//以指標p搜尋是否曾經過相同字元
		if(p == d + i) c++;	//若沒有搜尋到則增加一個經過的字元種類
    }
    cout << '\n' << c;
}
```
:::
## 2024年1月第4題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=m934
![image](https://hackmd.io/_uploads/r1CLlY7A0.png)
![image](https://hackmd.io/_uploads/SyUseKmCR.png)
:::
:::spoiler 解題思路
若逐一計算每一段區間的最小花費將會超時，因此使用動態規劃。先計算每一段區間的總和，再以遞迴函式計算區間最小花費，已經計算過者則直接取用數值，節省執行時間。
:::
:::spoiler 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int val[101][101] = {0};    //val[i][j]儲存第i到j格的總和
int ct[101][101] = {0};    //ct[i][j]儲存第i到j格的最小花費
int cost(int l, int r){    //以遞迴函式計算區間最小花費
    if(l == r) return 0;    //當計算的區間只有一個項目即花費為0
    if(ct[l][r] != 0) return ct[l][r];    //最小花費不為0代表極可能已計算過，則直接回傳
    int t = 100000;
    for(int k = l; k < r; k++){
        t = min(t, cost(l, k) + cost(k + 1, r) + abs(val[l][k] - val[k + 1][r]));
        //找出區間中總花費最小的合併方法
    }
    ct[l][r] = t;
    return t;
}
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> val[i][i];    //輸入第1到n格的數值
	}
	for(int k = 1; k <= n - 1; k++){
		for(int i = 1; i <= n - k; i++){
			for(int j = i; j <= i + k; j++) val[i][i + k] += val[j][j];
		}
	}    //先完成所有區間和的計算，以便後續計算花費
	cout << cost(1, n) << '\n';
	return 0;
}
```
:::
## 2024年6月第2題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=o077
![image](https://hackmd.io/_uploads/HkXRuGNG1x.png)
![image](https://hackmd.io/_uploads/ByskYG4Gye.png)
:::
:::spoiler 解題思路

:::
:::spoiler 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
int main(){
	short h, w, n, r, c, t, x;
	cin >> h >> w >> n;
	short a[h][w];
	for(short i = 0; i < h; i++){
		for(short j = 0; j < w; j++){
			a[i][j] = 0;    //初始化整張畫布
		}
	}
	while(n--){
		cin >> r >> c >> t >> x;
		for(short i = 0; i < h; i++){
			for(short j = 0; j < w; j++){
				if(abs(i - r) + abs(j - c) <= t) a[i][j] += x;    //曼哈頓距離<=t則疊加顏色數值x
			}
		}
	}
	for(short i = 0; i < h; i++){
		for(short j = 0; j < w; j++){
			cout << a[i][j] << ' ';    //輸出整張畫布
		}
		cout << '\n';
	}
}
```
:::
## 2024年10月第2題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=o712
![image](https://hackmd.io/_uploads/BJVg0jbbkg.png)
![image](https://hackmd.io/_uploads/rkBzRj--yx.png)
:::
:::spoiler 解題思路
依照題目指示按部就班寫下對應程式即可。行進方向以變數儲存，並使用函式簡化轉彎程序。
:::
:::spoiler 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int dir;    //dir記錄機器人當前朝向的方向，0為向右，1為向下，2為向左，3為向上
void turn(){    //設計右轉的函式
    dir++;
    if (dir == 4) dir = 0;
}
int main(){
	int m, n, k, r, c, score = 0, gems = 0;
    cin >> m >> n >> k >> r >> c;
    int a[m][n];
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];    //輸入整個地圖
        }
    }
    while(1){
        if(!a[r][c]) break;    //若機器人位於的格內寶石數量為0則終止
        score += a[r][c];    //將score加上當前格的寶石數量
        a[r][c]--;
        gems++;    //撿起一顆寶石
        if(score % k == 0) turn();    //若score是k的倍數則向右轉
        bool b = 1;
        while(b){    //檢測前方是否為牆壁，若是牆壁則右轉，非牆壁則跳出迴圈
            if(dir == 0){
                if(c + 1 == n || a[r][c + 1] == -1) turn();
                else b = 0;
            }
            if(dir == 1){
                if(r + 1 == m || a[r + 1][c] == -1) turn();
                else b = 0;
            }
            if(dir == 2){
                if(c == 0 || a[r][c - 1] == -1) turn();
                else b = 0;
            }
            if(dir == 3){
                if(r == 0 || a[r - 1][c] == -1) turn();
                else b = 0;
            }
        }
        if(dir == 0) c++;
        else if(dir == 1) r++;
        else if(dir == 2) c--;
        else if(dir == 3) r--;    //向前移動一步
    }
    cout << gems;
}
```
:::