# 367-26蔡尚融高二上自主學習-APCS精進計畫
本自主學習計畫透過研究APCS程式能力檢定實作考古題，增加對APCS題型的熟悉度。針對歷屆實作題進行程式碼編寫，並且附註一點題目與程式碼的解釋，讓自己能夠更加了解如何有效率的解讀題目，知道讓程式碼更高效的方法。希望藉由這些練習使我在之後的APCS檢定獲得比上一次更高的成績。
## 2023年1月第2題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=j606
:::
:::spoiler 解題思路
:::
:::spoiler 程式碼
```cpp=
```
:::
## 2023年6月第2題
:::spoiler 題目
ZERO JUDGE 連結：https://zerojudge.tw/ShowProblem?problemid=k732
:::
:::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
:::
:::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
:::
:::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
:::
:::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
:::
:::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
:::
:::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
:::
:::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;
}
```
:::
Sign in with Wallet
Connect another wallet