changed 2 years ago
Published Linked with GitHub

APCS 2023 10月 心得和簡易程式

觀念題心得

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

實作題

P1機械鼠

將輸入位置分成左邊和右邊,會求最大最小值就能拿分。

#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卡牌遊戲 二維陣列

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搬家 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投資遊戲 動態規劃

大概帶著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的話就是最大連續區間合了,可以參考這裡,我從中獲益許多。

後記

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

F 7 I
L X 7
I L J

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

心得和建議

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

Select a repo