# APCS 2023 10月 心得和簡易程式

### **觀念題心得**
上午觀念題的題目比起之前比較少有超出範圍的感覺，但還是有一些莫名其妙的程式追蹤題，就是只能慢慢推也抓不出考點的題目，不知道是不是故意出出來拖時間的，整體計算量也偏多，還有一題變形到超奇怪的stack題沒抓到考點也推不出來Q，很多題目都是倒著問的，像是輸出為X程式碼為?，程式碼為X什麼測資會有bug?，這類題目不好推只能靠平常累積經驗，不寫程式也絕對吃虧。

## 實作題

### [P1機械鼠](https://zerojudge.tw/ShowProblem?problemid=m370)
將輸入位置分成左邊和右邊，會求最大最小值就能拿分。

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

int main() 
{
    int x, n; cin >> x >> n;
    int mx = -101;
    int mn = 101;
    
    int l = 0, r = 0;
    
    int p;
    for(int i=0;i<n;i++){
      cin >> p;
      if(p > x){
        r++;
        mx = max(mx, p);
      }else{
        l++;
        mn = min(mn, p);
      }
    }
    
    if(l > r) cout << l << " " << mn;
    else cout << r << " " << mx;
    return 0;
}

### [P2卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371) 二維陣列
APCS的第二題大多是二維陣列模擬類型的題目，這題也不例外，算是其中較為簡單的，思考方式是先比較列再比較行，能夠配對(combo)就刪除(改為-1)然後繼續，看了一下測試資料的大小稍微計算時間複雜度就知道這題不會超時，再思考一下更簡單聰明的方法也不是不行，但既然都不用管時間了，當然就用能穩穩拿分，想法簡單不容易出錯的方式。檢查時發現同一行或列有兩組以上同時combo時會有bug，所以就加上break了(一列配對一組就離開)，反正不管時間。

#include <bits/stdc++.h>
using namespace std;
int p[22][42];

int main() 
{
    int n, m; cin >> n >> m;
    int ans = 0;
    
    for(int i=1;i<=n;i++){
      for(int j=1;j<=m;j++){
        cin >> p[i][j];
      }
    }
    
    while(1){
      bool combo = 0;
      int pre;
      //check row
      for(int i=1;i<=n;i++){
        pre = 0;
        p[i][0] = -2;
        for(int j=1;j<=m;j++){
          if(p[i][j] == p[i][pre]){
            ans += p[i][j];
            p[i][j] = -1;
            p[i][pre] = -1;
            combo = 1;
            break;
          }else if(p[i][j] != -1){
            pre = j;
          }
        }
      }
      
      //check column
      for(int i=1;i<=m;i++){
        pre = 0;
        p[0][i] = -2;
        for(int j=1;j<=n;j++){
          if(p[j][i] == p[pre][i]){
            ans += p[j][i];
            p[j][i] = -1;
            p[pre][i] = -1;
            combo = 1;
            break;
          }else if(p[j][i] != -1){
            pre = j;
          }
        }
      }
      
      if(combo == 0) break;
    }
    cout << ans;
    return 0;
}

### [P3搬家](https://zerojudge.tw/ShowProblem?problemid=m372) DFS
看題目時邊看邊笑，笑的原因是這題出的很有趣，而且馬上就能想到是圖遍歷+條件判斷的題目，之後就開始動手實作，考試時的程式也幾乎是直接爆破，不像現在有稍微簡化過，沒用BFS是因為DFS對我來說較為直觀，BFS也沒有明顯的優點，但在Zerojudge上就有一條測試資料沒過:(，希望到時候成績出來，有人能解答這題用DFS能否拿到滿分？我自己是沒辦法驗證了，原因在後記。

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

int n, m;
char p[505][505];
bool vis[505][505];

int dis, ans;

void dfs(int x, int y){
  dis++;
  int nx, ny;
  // have way top
  if(p[x][y] == 'X' || p[x][y] == 'I' || p[x][y] == 'L' || p[x][y] == 'J'){
    nx = x - 1;
    ny = y;
    if(nx >= 0 && !vis[nx][ny]){
      // down open
      if(p[nx][ny] == 'X' || p[nx][ny] == 'I' || p[nx][ny] == '7' || p[nx][ny] == 'F'){
        vis[nx][ny] = 1;
        dfs(nx, ny);
      }
    }
  }
  // have way down
  if(p[x][y] == 'X' || p[x][y] == 'I' || p[x][y] == '7' || p[x][y] == 'F'){
    nx = x + 1;
    ny = y;
    if(nx < n && !vis[nx][ny]){
      // top open
      if(p[nx][ny] == 'X' || p[nx][ny] == 'I' || p[nx][ny] == 'L' || p[nx][ny] == 'J'){
        vis[nx][ny] = 1;
        dfs(nx, ny);
      }
    }
  }
  // have way left
  if(p[x][y] == 'X' || p[x][y] == 'H' || p[x][y] == '7' || p[x][y] == 'J'){
    nx = x;
    ny = y - 1;
    if(ny >= 0 && !vis[nx][ny]){
      // right open
      if(p[nx][ny] == 'X' || p[nx][ny] == 'H' || p[nx][ny] == 'L' || p[nx][ny] == 'F'){
        vis[nx][ny] = 1;
        dfs(nx, ny);
      }
    }
  }
  // have way right
  if(p[x][y] == 'X' || p[x][y] == 'H' || p[x][y] == 'L' || p[x][y] == 'F'){
    nx = x;
    ny = y + 1;
    if(ny < m && !vis[nx][ny]){
      // left open
      if(p[nx][ny] == 'X' || p[nx][ny] == 'H' || p[nx][ny] == '7' || p[nx][ny] == 'J'){
        vis[nx][ny] = 1;
        dfs(nx, ny);
      }
    }
  }
}




int main() 
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        cin >> p[i][j];
      }
    }
    ans = 0;
    for(int i=0;i<n;i++){ 
      for(int j=0;j<m;j++){
        if(p[i][j] != '0' && !vis[i][j]){
          dis = 0;
          memset(vis, 0, 505*505);
          vis[i][j] = 1;
          dfs(i, j);
        }
        ans = max(ans, dis);
      }
    }
    cout << ans;
    return 0;
}

### [P4投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373) 動態規劃
大概帶著80分鐘進入第四題，第四題也是以往思考上最花時間的一題(對於我這菜鳥來說)，看完題目看了一下子題配分，ok 40+60，直接考慮滿分作法沒有在客氣，畢竟寫完前三題了，思考了五分鐘大概確定就是DP題開始推轉移式，從最簡易的DP類型開始，就是設dp[i][j]，為第i天使用了j個金牌的最大總收益，對於第i天來說只有兩種可能，就是用金牌和沒用金牌，假設用了並且是第k個，那麼前一天一定只能用k-1個，如果沒用前一天維持k個，兩者取最大值，轉移式推完後丟到寫好的二維迴圈裡嘗試跑測資，咦，好像對了，之後由於不太相信又多嘗試幾個自訂測資，試到想不出其它極端情況才放心，回去檢查前三題。

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

int main() 
{
    int n, k; cin >> n >> k;
    vector<vector<int>> dp = vector<vector<int>>(n+1, vector<int>(k+1));
    
    int ans = 0;
    int p;
    for(int i=1;i<=n;i++){
      cin >> p;
      dp[i][0] = 0;
      for(int j=0;j<=k;j++){
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j] + p);
        ans = max(dp[i][j], ans);
      }
    }
    
    cout << ans;
    return 0;
}

如果k=0的話就是最大連續區間合了，可以參考[這裡](https://hackmd.io/@CLKO/rkhigGlTG?type=view#%E7%B6%93%E5%85%B8%E5%95%8F%E9%A1%8C%EF%BC%9A%E6%9C%80%E5%A4%A7%E9%80%A3%E7%BA%8C%E5%85%83%E7%B4%A0%E5%92%8C)，我從中獲益許多。

### 後記
這次考APCS是感覺與五級分最接近的一次，回去檢查時發現第三題有一個bug，而且多數情況下不會出現，還記得那時用來測試的圖形是

F 7 I
L X 7
I L J

時間越來越接近，好在有找到錯的地方，其中一個方向的程式碼沒有加上!vis，改完程式測試成功後還剩下兩分鐘，但還要去複製程式碼和提交，結果提交後測資結果錯誤，我超級緊張，只能選擇原本的程式再提交一次，等判定時，時間就結束了，回到家才驚覺，我把第三題的程式拿去交第四題xd。

### 心得和建議
給在奮鬥的高中生，學習程式的阻礙和挫折滿大的，你會寫一題題目花了半天時間，去看解答還看不懂，或是這題題目的想法竟然是這樣，給我一天我都想不到，然後覺得自己好爛，這裡提供四個建議，1.持續練習，花半天寫程式可能沒什麼感覺，甚至覺得這半天沒學到什麼，浪費了，但持續練習，有一天你會發現，"X我好強"，然後繼續循環。2.考古題刷爛，這應該是取得成績最快的方式，說真的，不可能每次考試都生一個新的考點出來，能考的就那些，換湯不換藥，考前針對目標把考古題都做過絕對是CP值最高的方式。 3.針對練習，基礎語法不熟，好好把一套教程上完，二維迴圈不熟，就多做考古題第二題，像這次考試前也是狂練了動態規劃題，機會就剛好來了:)。4. 120%的準備，平常練習時打不出全壘打，那正式上場時更不可能，也算是我從這次考試學到的經驗，20%準備留給容錯，考APCS不可能不檢查，除非你有100%的自信，尤其測資都只給一兩個，zerojudge上的題目都還給多了，很多邊界、例外情況都會少處理。