# APCS 20221023 題解 ## 第一題：巴士站牌 [（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=i428) * 此題只需邊輸入邊用abs取相鄰兩站之間的距離，然後找出最大值和最小值即可(Example 1) * 一開始我看成要找出每個站之間的距離才用以下的辦法(用pair <int, int> p[] 存座標) (Example 2) * #還以為第一題難度什麼時候(進步)那麼快 :::spoiler Example 1 ```cpp= #include <bits/stdc++.h> using namespace std; int main() { int n, x, y, px, py, Max = -INT_MAX, Min = INT_MAX; cin >> n >> px >> py; for(int i=0; i<n-1; i++){ cin >> x >> y; int dis = abs(x - px) + abs(y - py); Max = max(Max, dis); Min = min(Min, dis); px = x, py = y; } cout << Max << ' ' << Min; } ``` ::: :::spoiler Example 2 ```cpp= #include <bits/stdc++.h> using namespace std; int main() { pair <int, int> p[10000]; vector <int> save; int n; cin >> n; for(int i=0; i<n; i++){ cin >> p[i].first >> p[i].second; } for(int i=0; i<n-1; i++){ save.push_back(abs(p[i].first - p[i+1].first) + abs(p[i].second - p[i+1].second)); } cout << *max_element(save.begin(), save.end()) << ' ' << *min_element(save.begin(), save.end()); } ``` ::: ## 第二題：運貨站 [（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=j123) * now[] 用來記錄每一列當前的長度 :::spoiler Example ```cpp= #include <bits/stdc++.h> using namespace std; int now[35]; int r, c, n, place, ans1 = 0, ans2 = 0; //ans1:進倉庫的格子數 ans2:進倉庫貨物數量 char box; void A(int x){ int Max = -1; for(int i=x; i<=x+3; i++) Max = max(Max, now[i]); if(Max + 1 < c){ ans1 += 4; ans2++; for(int i=x; i<=x+3; i++) now[i] = Max + 1; } } void B(int x){ if(now[x] + 3 < c) { ans1 += 3; ans2++; now[x] += 3; } } void C(int x){ int Max = max(now[x], now[x+1]); if(Max + 2 < c){ ans1 += 4; ans2++; for(int i=x; i<=x+1; i++) now[i] = Max + 2; } } void D(int x){ if(now[x] + 1 < c && now[x+1] + 3 < c) { ans1 += 4; ans2++; if(now[x] + 1 >= now[x+1] + 3 ){ now[x]++; now[x+1] = now[x]; } else{ now[x+1] += 3; now[x] = now[x+1]; } } } void E(int x){ if(now[x] + 1 < c && now[x+1] + 2 < c && now[x+2] + 2 < c) { ans1 += 5; ans2++; if(now[x] + 1 >= now[x+1] + 2 && now[x] + 1 >= now[x+2] + 2){ now[x]++; now[x+1] = now[x]; now[x+2] = now[x]; } else if(now[x+1] + 2 >= now[x] + 1 && now[x+1] + 2 >= now[x+2] + 2){ now[x+1] += 2; now[x] = now[x+1]; now[x+2] = now[x+1]; } else{ now[x+2] += 2; now[x] = now[x+2]; now[x+1] = now[x+2]; } } } int main() { memset(now, -1, sizeof(now)); cin >> r >> c >> n; for(int i=0; i<n; i++){ cin >> box >> place; if(box == 'A') A(place); else if(box == 'B') B(place); else if(box == 'C') C(place); else if(box == 'D') D(place); else if(box == 'E') E(place); } cout << r*c - ans1 << ' ' << n - ans2; } ``` ::: ## 第三題：石窟探險[（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=j124) * 直接用題目已經跑完整個樹的節點來做DFS (Example 1) * * 先整理題目用stack做一個樹，再做DFS遍歷 (較為複雜) (Example 2) :::spoiler Example 1 ```cpp= #include <bits/stdc++.h> using namespace std; typedef long long ll; vector <ll> v; ll n, now = 0, ans = 0; ll DFS(){ ll next, t = v[now++]; if(t){ for(int i=0; i<2 + (t%2) ? 1 : 0; i++){ next = DFS(); if(next) ans += abs(t - next); } return t; } else return 0; } int main() { while(cin >> n) v.push_back(n); DFS(); cout << ans; } ``` ::: :::spoiler Example 2 ```cpp= #include <bits/stdc++.h> using namespace std; typedef long long ll; ll a, root = 0, ans = 0; stack <ll> pre; vector <ll> v[100005]; bool check(){ if(pre.top() % 2 && v[pre.top()].size() == 3) return true; else if(pre.top() % 2 == 0 && v[pre.top()].size() == 2) return true; else return false; } void dfs(ll x){ for(int i=0; i<v[x].size(); i++){ if(v[x][i] != 0){ ans += abs(x - v[x][i]); dfs(v[x][i]); } } } int main() { cin >> a; root = a; pre.push(a); while(cin >> a){ v[pre.top()].push_back(a); if(a != 0){ pre.push(a); } else{ while(check()){ pre.pop(); if(pre.size() == 0) break; } } } dfs(root); cout << ans; } ``` ::: ## 第四題： 蓋步道[（題目敘述）](https://zerojudge.tw/ShowProblem?problemid=j125) * 二分搜高度 * 用BFS來驗證是否能到終點以及到終點的最短距離 :::spoiler Example ```cpp= #include <bits/stdc++.h> using namespace std; int n, arr[350][350] , bfs[350][350]; int ans1 = 0, ans2 = 0; int BFS(int x){ int sx = 1, sy = 1, Max = -1; queue <pair<int, int>> q; q.push({sx, sy}); while(q.size()){ int a = q.front().first; int b = q.front().second; q.pop(); if(bfs[a+1][b] == 0 && abs(arr[a+1][b] - arr[a][b]) <= x){ Max = max(Max, abs(arr[a+1][b] - arr[a][b])); q.push({a+1, b}); bfs[a+1][b] = bfs[a][b] + 1; } if(bfs[a][b+1] == 0 && abs(arr[a][b+1] - arr[a][b]) <= x){ Max = max(Max, abs(arr[a][b+1] - arr[a][b])); q.push({a, b+1}); bfs[a][b+1] = bfs[a][b] + 1; } if(bfs[a-1][b] == 0 && abs(arr[a-1][b] - arr[a][b]) <= x){ Max = max(Max, abs(arr[a-1][b] - arr[a][b])); q.push({a-1, b}); bfs[a-1][b] = bfs[a][b] + 1; } if(bfs[a][b-1] == 0 && abs(arr[a][b-1] - arr[a][b]) <= x){ Max = max(Max, abs(arr[a][b-1] - arr[a][b])); q.push({a, b-1}); bfs[a][b-1] = bfs[a][b] + 1; } } if(bfs[n][n] != 0) { ans1 = Max; ans2 = bfs[n][n] - 1; return 1; } else return 0; } void reset(){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ bfs[i][j] = 0; } } } int main() { cin >> n; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ cin >> arr[i][j]; } } int L = 0, R = 1000000; while(L < R - 1){ memset(bfs, -1, sizeof(bfs)); reset(); bfs[1][1] = 1; int M = (L + R) / 2; if(BFS(M) == 0) L = M; else R = M; } cout << ans1 << '\n' << ans2; } ``` :::