# APCS 20221023 題解 ## [巴士站牌](https://zerojudge.tw/ShowProblem?problemid=i428) ### 想法 對於每個點找他其中一邊的鄰居看看距離，再比大小求最大最小值。 ### 時間複雜度 \$O(N)\$ ### Code ```cpp= #include <bits/stdc++.h> using namespace std; array<int, 104> X, Y; signed main(){ int n, ner = 1 << 30, far = 0; cin >> n >> X[1] >> Y[1]; for(int i = 2; i <= n; i++){ cin >> X[i] >> Y[i]; ner = min(ner, abs(X[i] - X[i - 1]) + abs(Y[i] - Y[i - 1])); far = max(far, abs(X[i] - X[i - 1]) + abs(Y[i] - Y[i - 1])); } cout << far << " " << ner << "\n"; return 0; } ``` ## [運貨站](https://zerojudge.tw/ShowProblem?problemid=j123) ### 想法 對於每個包裹先把他放在倉庫的最右邊，接著一步一步往內推直到碰上牆壁或是其他包裹。最後檢查包裹的右界是否露在倉庫外就完事了。 ### 時間複雜度 \$O((N + R)C)\$ ### Code ```cpp= #include <bits/stdc++.h> using namespace std; int r, c; array<int, 5> Ly = {3, 0, 1, 1, 2}, Lx = {0, 2, 1, 2, 1}; array<array<int, 34>, 54> D; int push(int x, int y, int t){ for(; x; x--){ if(t == 0 && (D[x][y] || D[x][y - 1] || D[x][y - 2] || D[x][y - 3])) break; else if(t == 1 && D[x][y]) break; else if(t == 2 && (D[x][y] || D[x][y - 1])) break; else if(t == 3 && (D[x][y] || D[x + 2][y - 1])) break; else if(t == 4 && (D[x][y] || D[x][y - 1] || D[x + 1][y - 2])) break; } x++; if(x + Lx[t] > c) return 1; if(t == 0) D[x][y] = D[x][y - 1] = D[x][y - 2] = D[x][y - 3] = 1; else if(t == 1) D[x][y] = D[x + 1][y] = D[x + 2][y] = 1; else if(t == 2) D[x][y] = D[x][y - 1] = D[x + 1][y] = D[x + 1][y - 1] = 1; else if(t == 3) D[x][y] = D[x + 1][y] = D[x + 2][y] = D[x + 2][y - 1] = 1; else D[x][y] = D[x][y - 1] = D[x + 1][y] = D[x + 1][y - 1] = D[x + 1][y - 2] = 1; return 0; } signed main(){ int n, y, up = 0, sum = 0; char t; cin >> r >> c >> n; for(int i = 1; i <= n; i++){ cin >> t >> y, y += 1 + Ly[t - 'A']; up += push(c, y, t - 'A'); } for(int i = 1; i <= c; i++){ for(int j = 1; j <= r; j++){ sum += !D[i][j]; } } cout << sum << " " << up << "\n"; return 0; } ``` ## [石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124) ### 想法 把題目給的序列直接拿去建樹，然後 DFS 求差值總和。 ### 時間複雜度 \$O(N)\$ ### Code ```cpp= #include <bits/stdc++.h> #define int long long #define pb push_back using namespace std; int p = 0, sum = 0; vector<int> V; int DFS(){ int u = V[p++], v; if(!u) return 0; for(int i = 0; i < 2 + (u & 1); i++){ v = DFS(); if(v) sum += abs(u - v); } return u; } signed main(){ int v; while(cin >> v) V.pb(v); DFS(); cout << sum << "\n"; return 0; } ``` ## [蓋步道](https://zerojudge.tw/ShowProblem?problemid=j125) ### 想法 對步道中出現的最大差值二分搜。二分搜中每次對於所有鄰點高度相差不超過當前二分搜的值建邊，檢查左上到右下是否連通，是的話則右界減小，反之左界增加。最後再跑一次最短路求路徑長就好了。 ### 時間複雜度 \$O(N^2logC)\$ ### Code ```cpp= #include <bits/stdc++.h> using namespace std; struct ufo{ int x, y, d; }; array<int, 4> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1}; array<array<int, 304>, 304> H, dis; int RUN(int n, int p){ queue<ufo> Q; for(array<int, 304> &D : dis) for(int &d : D) d = 0; Q.push({1, 1, 1}); while(!Q.empty()){ auto [x, y, d] = Q.front(); Q.pop(); if(dis[x][y] || !x || !y || x > n || y > n) continue; dis[x][y] = d; for(int i = 0; i < 4; i++){ if(abs(H[x][y] - H[x + dx[i]][y + dy[i]]) <= p) Q.push({x + dx[i], y + dy[i], d + 1}); } } return dis[n][n]; } int RFS(int n){ int p = 0; for(int i = 1 << 20; i; i >>= 1){ if(!RUN(n, p + i)) p += i; } RUN(n, p + 1); return p + 1; } signed main(){ int n; cin >> n; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cin >> H[i][j]; } } cout << RFS(n) << "\n" << dis[n][n] - 1 << "\n"; return 0; } ```