# 10/23 APCS參考題解 難得我比較有把握的一次APCS 希望能撈個5級分 QQ ## pA: 巴士站牌 [題目連結](https://zerojudge.tw/ShowProblem?problemid=i428) 簡單題,用一個陣列維護資訊,再跑過一次就好 :::spoiler code ```cpp! #include <bits/stdc++.h> using namespace std; #define int long long const int INF=1e18; // 宣告 int mi=INF, ma=-INF; int n, a, b; vector<pair<int, int>> v; signed main(void){ // 輸入 cin >> n; for (int i=0 ; i<n ; i++){ cin >> a >> b; v.push_back({a, b}); } // 尋找最大 & 最小值 for (int i=0 ; i<n-1 ; i++){ mi=min(mi, abs(v[i].first-v[i+1].first)+abs(v[i].second-v[i+1].second)); ma=max(ma, abs(v[i].first-v[i+1].first)+abs(v[i].second-v[i+1].second)); } // 輸出 cout << ma << " " << mi << "\n"; return 0; } ``` ::: ## pB: 貨運站 [題目連結](https://zerojudge.tw/ShowProblem?problemid=j123) 一題正常的pB,簡單但複雜的實作題,感覺很像俄羅斯方塊 由於前兩題幾乎不用考慮時間複雜度,看到的時候我就打算模擬了 看到輸出,我是打算維護兩個變數:已經被塞入的空格(這點與題目的書初步一樣,但是我認為更好維護)以及不能被放入貨物數量 步驟大概是 1. 初始化版面,留下左邊邊界當作中止點 2. 確認是哪種貨物(一個一個手刻原始座標),並且在起點生成 3. 將方塊從慢慢把左邊邊界移動,**直到碰到邊界或是前面放的方塊** 4. 結束後,檢查是否可以放置,如果可以的話就將方塊設成**已經被放入的貨物**,否則增加第二個變數的值。 :::spoiler code ```cpp! #include <bits/stdc++.h> using namespace std; #define int long long // 宣告 int r, c, n, tmp; int op1=0, op2=0; // op1: 維護有多少格子被放置, op2: 維護有多少貨物放不進去 char type; vector<pair<char, int>> v; // 維護輸入 int arr[100][100]; // 貨櫃版面, 0: 空格,1: 正在放入的貨物,2: 邊界或是已經放入的貨物 signed main(void){ // 初始化版面 for (int i=0 ; i<100 ; i++){ arr[i][0]=2; } // 輸入 cin >> r >> c >> n; for (int i=0 ; i<n ; i++){ cin >> type >> tmp; v.push_back({type, tmp}); } // 放入貨物 for (int i=0 ; i<n ; i++){ pair<int, int> block[5]; // 貨物的每個方格座標 int block_cnt; // 貨物的大小 // 生成貨物 & 設定初始座標(x=60為起點) if (v[i].first=='A'){ block_cnt=4; block[0]={v[i].second, 60}; block[1]={v[i].second+1, 60}; block[2]={v[i].second+2, 60}; block[3]={v[i].second+3, 60}; } if (v[i].first=='B'){ block_cnt=3; block[0]={v[i].second, 60}; block[1]={v[i].second, 61}; block[2]={v[i].second, 62}; } if (v[i].first=='C'){ block_cnt=4; block[0]={v[i].second, 60}; block[1]={v[i].second+1, 60}; block[2]={v[i].second, 61}; block[3]={v[i].second+1, 61}; } if (v[i].first=='D'){ block_cnt=4; block[0]={v[i].second+1, 60}; block[1]={v[i].second+1, 61}; block[2]={v[i].second, 62}; block[3]={v[i].second+1, 62}; } if (v[i].first=='E'){ block_cnt=5; block[0]={v[i].second+1, 60}; block[1]={v[i].second+2, 60}; block[2]={v[i].second, 61}; block[3]={v[i].second+1, 61}; block[4]={v[i].second+2, 61}; } // 在初始地點放置貨物 for (int j=0 ; j<block_cnt ; j++){ arr[block[j].first][block[j].second]=1; } // 移動貨物直到不能移動 bool check=1; while (1){ for (int j=0 ; j<block_cnt ; j++){ if (arr[block[j].first][block[j].second-1]==2){ check=0; break; } } if (check){ // 每個方塊都可以被移動,更新版面 for (int j=0 ; j<block_cnt ; j++){ arr[block[j].first][block[j].second]=0; arr[block[j].first][block[j].second-1]=1; block[j].second--; } continue; }else{ // 不能被移動了,確認是否有超出範圍 check=1; for (int j=0 ; j<block_cnt ; j++){ if (block[j].second>c){ check=0; } } if (check){ // 可以被放置,更新op1以及目前版面 op1+=block_cnt; for (int j=0 ; j<block_cnt ; j++){ arr[block[j].first][block[j].second]=2; } }else{ // 不能被放置,更新op2以及清掉貨物 op2++; for (int j=0 ; j<block_cnt ; j++){ arr[block[j].first][block[j].second]=0; } } break; } } } // 輸出 cout << r*c-op1 << " " << op2 << "\n"; // 因為op1維護有多少格子被放置,記得要用貨物箱大小扣除 return 0; } ``` ::: ## pC: 石窟探險 [題目連結](https://zerojudge.tw/ShowProblem?problemid=j124) 我第一眼想到的是跟2019年2月[合成函數](https://judge.tcirc.tw/ShowProblem?problemid=d002)很像 大概的想法就是DFS一次,要回溯的時候只要不是根或是0再把答案給遞迴上去 :::spoiler code ```cpp! #include <bits/stdc++.h> using namespace std; #define int long long const int INF=1e18; // 宣告 int f(int x){ int n; cin >> n; if (n==0){ return 0; } int add=0; if (x!=-1){ add=abs(x-n); } if (n%2==0){ return add+f(n)+f(n); }else{ return add+f(n)+f(n)+f(n);; } } signed main(void){ // 輸入 cout << f(-1) << "\n"; return 0; } ``` ::: ## pD: 蓋步道 [題目連結](https://zerojudge.tw/ShowProblem?problemid=j125) 原本我想要用動態規劃的,但是想不出來狀態要怎麼轉移,剛好昨天才在寫[Reset K Edges](https://codeforces.com/contest/1739/problem/D),結構驚人的相似,發現**是否能在k的平緩度以下**具有單調性,稍微算一下時間複雜度是$O(300 \times 300 \times 4\times \log_2{10^6})$,感覺還不錯就開始寫了 另外,因為題目有要另外求最短距離,所以得用BFS而不是DFS,並且由於有可能會從四個方向轉移,因此vis紀錄需要多開一個維度 :::spoiler code ```cpp! #include <bits/stdc++.h> using namespace std; #define int long long // 宣告 int n, tmp; int arr[400][400], vis[4][400][400]; int op1, op2; // op1: 最小的相差值,op2: 最小的長度 const int mx[4]={1, 0, -1, 0}; const int my[4]={0, 1, 0, -1}; struct position{ int x; int y; int len; }; // check函式 bool check(int mid){ //初始化 memset(vis, 0, sizeof(vis)); queue<position> que; que.push({1, 1, 0}); // 記得紀錄vis vis[0][1][1]=1; vis[1][1][1]=1; vis[2][1][1]=1; vis[3][1][1]=1; // BFS 流程 while (que.size()){ position now=que.front(); que.pop(); // 確認是否抵達終點(因為BFS的特性,最先到終點的一定是答案) if (now.x==n && now.y==n){ op1=mid; op2=now.len; return 1; } // 繼續尋找周圍的點 for (int j=0 ; j<4 ; j++){ int next=arr[now.x+mx[j]][now.y+my[j]]; if (next!=-1 && vis[j][now.x+mx[j]][now.y+my[j]]==0 && abs(next-arr[now.x][now.y])<=mid){ que.push({now.x+mx[j], now.y+my[j], now.len+1}); vis[j][now.x+mx[j]][now.y+my[j]]=1; } } } return 0; } signed main(void){ // 輸入 cin >> n; for (int i=1 ; i<=n ; i++){ for (int j=1 ; j<=n ; j++){ // 使用based 1,待會邊界比較好寫 cin >> arr[i][j]; } } // 初始化邊界,用-1代表 for (int i=0 ; i<=n+1 ; i++){ arr[0][i]=-1; arr[n+1][i]=-1; arr[i][0]=-1; arr[i][n+1]=-1; } // 二分搜 (左閉右開寫法) int l=0, r=1e6+1, mid; while (l<r){ mid=l+(r-l)/2; if (check(mid)){ r=mid; }else{ l=mid+1; } } // 輸出 cout << op1 << " " << op2 << "\n"; return 0; } ``` :::